Excel
Trattiamo in questa sezione i processi necessari a creare, partendo dai dati memorizzati all’interno delle nostre basi di dati, il file Excel da caricare sulla piattaforma NetSIC.
Prima di proseguire, ricordiamo con la Figura 2.2 del Capitolo 2, la struttura che dobbiamo rispettare affinchè sia possibile l’importazione del file.
Anche per realizzare questa fase ci affideremo al valido aiuto del software Kettle, di Pentaho. Studiandone la documentazione ci si accorge che tra i vari elementi di gestione del flusso disponibili ne sono presenti anche vari concepiti proprio per affrontare problematiche come la nostra.
Figura 5.10: Processo ETL di caricamento del file xls obiettivo L’elemento Microsoft Excel Writer fa al caso nostro poichè inserisce in un foglio excel un flusso di dati di input. Impostando come sorgenti di dati le tabelle delle nostre basi di dati e inserendo nelle specifiche dell’elemento il modello del file Excel da riempire possiamo creare il nostro report con un semplice click.
Nella Figura 5.10 sono illustrate le varie trasformazioni necessarie alla compilazione del file Excel, obiettivo finale dell’intero processo. Le trasfor- mazioni riguardano solo il caricamento dei dati dalla base di dati relativa al- l’acquedotto, ma per l’infrastruttura fognaria il procedimento è esattamente lo stesso.
Quanto detto fino ad ora però non è sufficiente per concludere il nostro lavoro. Abbiamo più volte ripetuto che l’interesse dell’autorità non è solo rivolto alle informazioni anagrafiche degli impianti, delle tubazioni e delle altre componenti dell’infrastruttura idrica, ma riguarda anche i rapporti che esistono proprio tra queste componenti. In altre parole AiT vuole sapere in che rete e in che impianti di trattamento finisce l’acqua captata da un determinato impianto di captazione, e lo vuole sapere per tutti gli impianti nella rete. L’unico modo per risolvere questo problema è analizzare la rete
idrica modellandola come un grafo in cui i vertici sono costituiti dagli impianti e gli archi dalle tubazioni. Analizzando questo grafo potremo ottenere le informazioni richieste memorizzandole all’interno di tabelli integrative facenti parte delle nostre basi di dati di appoggio. Da queste tabelle potremo infine caricare le informazioni mancanti nel file Excel seguendo la stessa procedura presentata in questa sezione e giungere cosi al completamento definivo del report obiettivo.
I metodi di analisi del grafo della rete saranno presentati nel successivo capitolo.
Capitolo 6
ESTRAZIONE DEL GRAFO
DELLA RETE IDRICA
In questo capitolo utilizzeremo il grafo della rete idrica memorizzato nel no- stro database MySql per ottenere l’ultima categoria di informazioni richieste da AiT, ovvero i rapporti tra gli impianti e tra questi e le reti di distribu- zione. Le informazioni sul percorso che effettua l’acqua da ogni captazione fino all’utenza finale sono di centrale importanza per l’autorità, soprattutto per poter capire quali impianti sono stati attraversati dall’acqua prima di giungere nelle case degli utenti finali.
Una volta ottenute si aggiungeranno a quelle già individuate sulle ca- ratteristiche anagrafiche dei componenti dell’infrastruttura e sarà possibile completare la redazione del file Excel da importare sulla piattaforma NetSic. Faremo ricorso alle principali tecniche di esplorazione di un grafo appli- cando i concetti degli algoritmi di visita per minimizzare l’utilizzo di memoria e il tempo di calcolo. Vedremo due soluzioni: una con l’utilizzo di procedu-
re (Pl-Sql) su un grafo memorizzato tramite modello relazionale e una con linguaggio a oggetti (Java) sfruttando le strutture dati che mette a dispo- sizione. Valuteremo i vantaggi e gli svantaggi di ognuna per effettuare una scelta ponderata.
Un grafo è un insieme di elementi detti nodi o vertici che possono essere collegati fra loro da archi. Più formalmente, si dice grafo una coppia G = (V, E) di insiemi , con V insieme dei nodi ed E insieme degli archi, tali che gli elementi di E siano coppie di elementi di V E ⊆ (V ∗ V ) [Cormen 05].
Il grado in uscita di un nodo v, δ(v) è il numero di nodi ad esso adiacenti, ovvero il numero di coppie di nodi per cui esiste un arco (u, v) ∈ E che li collega.
Esistono due tipi basilari di grafo, orientato, anche detto diretto, nel quale tutti gli archi sono direzionati e possono essere attraversati in un unica direzione e non orientato (indiretto) in cui ogni arco puo essere percorso allo stesso modo in entrambe le direzioni .
La somma dei gradi dei nodi di un grafo è pari, in caso di grafo non- orientato al doppio del numero degli archi 2E, mentre per un grafo orientato esattamente ad E. Cio è vero perchè un singolo arco (u, v) in un grafo non orientato rende adiacenti i due estremi in entrambe le direzioni, in un grafo orientato invece, lo stesso arco rende adiacente il nodo di origine al nodo di arrivo incrementando la somma dei gradi di tutti i vertici di una sola unità. Un grafo può essere memorizzato facendo ricorso a quattro tipi di strut- ture dati.
• Matrice di adiacenza • Matrice di incidenza • Liste di archi
In appendice sono presentate le caratteristiche di ognuna di queste strut- ture, con annessa una valutazione delle prestazioni che offrono per l’esecu- zione delle operazioni di base.
Non c’è un modo per memorizzare grafi che risulti migliore in assoluto: è la natura del problema da risolvere che determina la scelta della tecnica di rappresentazione del grafo più idonea alla soluzione [Cormen 05].
6.1
Presentazione del problema
Dopo questa introduzione sulle strutture più utilizzate, analizziamo come il grafo della rete idrica che abbiamo in possesso viene memorizzato.
Entrambe le basi di dati create, per l’acquedotto e per la rete fognaria, fanno ricorso ad un grafo orientato per mantenere i rapporti esistenti tra i vari impianti di trattamento delle acque.
Il Grafo è memorizzato con una struttura relazionale, in particolare al- l’interno della tabella tratte. La tabella tratte ha come chiave primaria il codice identificativo del tratto, varie informazioni sulle caratteristiche del tratto stesso e due campi che ne indicano rispettivamente il nodo di partenza (NUMNODI) e il nodo di arrivo(NUMNODF).
In base all’analisi fatta in precedenza vediamo che il nostro grafo viene rappresentato concettualmente come una lista di archi orientati, anche se si
utilizzano due attributi della tabella invece che una lista vera e propria. Con una semplice query di selezione ed ordinamento si evidenziano tutti gli archi ricalcando la struttura di due array paralleli indicizzati con un valore intero progressivo.
SELECT numnodi, numnodf FROM tratta Order BY ASC numnodi
Questa forma di rappresentazione non causa sprechi di memoria, lo spazio totale occupato sarà uguale al numero di archi.
Sia la nostra struttura, assimilabile ad una lista di archi sia le liste di adiacenza minimizzano la quantità di memoria necessaria.
In tale struttura sono conservate tutte le informazioni di cui abbiamo bisogno per completare la compilazine del file Excel, si tratta solo di estrarre quelle che ci interessano.
Ricordiamo tutte le tipologie di rapporti tra impianti che devono essere individuate (Tab. 6.1. Per ognuna di esse il modello di file Excel obiettivo contiene un foglio strutturato come una tabella a due attributi. Nel primo attributo si inseriranno i codici degli impianti di partenza, nel secondo si inseriranno i codici degli impianti o delle reti raggiungibili dagli impianti di partenza.
Per poter risolvere il problema dato, è necessario l’accesso sistematico a tutti i vertici, uno dopo l’altro, ossia la visita del grafo. Partendo da uno specifico vertice, detto vertice radice, e di solito identificato con s, si può desiderare di accedere a tutti i vertici che si trovano a una certa distanza da esso prima di accedere a quelli situati a distanza maggiore, e in questo caso si parla di visita in ampiezza (BFS, Breadth-first search); oppure si vuole
SORGENTE DESTINAZIONE Captazione da Fiumi Potabilizzatori Captazione da Fiumi Reti di distribuzione Captazione da Laghi Potabilizzatori Captazione da Laghi Reti di distribuzione Captazione da Pozzi Potabilizzatori Captazione da Pozzi Reti di distribuzione Captazione da Sorgenti Potabilizzatori Captazione da Sorgenti Reti di distribuzione
Potabilizzatori Reti di distribuzione
Serbatoi Reti di adduzione
Serbatoi Reti di distribuzione
Pompaggi Potabilizzatori
Pompaggi Serbatoi
Reti di adduzione Reti di distribuzione
Depuratori Collettori
Scaricatori Reti di raccolta
Tabella 6.1: I rapporti di raggiungibilità richiesti dall’Autorità idrica Toscana accedere ai vertici allontandosi sempre di più dal vertice di partenza finché è possibile, e in questo caso si parla di visita in profondità (DFS, depth-first search).
In appendice vengono descritti nel dettaglio i due algoritmi di visita con particolare attenzione alla loro complessita computazionale.
La visita in ampiezza è poco adatta a una implementazione ricorsiva e viene generalmente realizzata in modo iterativo con l’ausilio di una coda. Viceversa, la visita in profondità è molto adatta ad essere realizzata in modo ricorsivo ma può essere definita in modo iterativo con l’ausilio di una pila [Cormen 05].
Entrambi gli approcci, anche se affrontano la visita con ordine diverso, danno come risultato un albero di copertura minima di radice s dal qua-
le discendono tutti i nodi che da esso sono raggiungibili. L’individuazione dell’albero è proprio l’obiettivo che dobbiamo raggiungere per determinare i legami di connessione tra gli impianti della rete idrica. Ad esempio, per sapere in quale impianto di potabilizzazione confluisce l’acqua captata da un pozzo basterà impostare il nodo in cui questo è localizzato come nodo radice e tramite l’algoritmo scoprire tutti i nodi raggiungibili dalle tubazioni esistenti (gli archi del nostro grafo).
Alla luce di quanto detto, per ottenere una visita efficiente conviene uti- lizzare la struttura a liste di adiacenza, mentre il nostro grafo è memorizzato in una struttura relazionale assimilabile ad una lista di archi. Ci trovia- mo dunque di fronte ad una scelta, il guadagno di tempo di esecuzione con l’utilizzo di liste di adiacenza giustifica la modifica della struttura dati di me- morizzazione? Per sciogliere il dubbio percorreremo due strade distinte, in una manterremo la struttura relazionale effettuando la visita con linguaggio procedurale pl-sql, nell’altra inseriremo il grafo in delle liste di adiacenza e lo visiteremo con l’utilizzo del linguaggio java.