6.2 Progettazione e realizzazione di una visita sul grafo della rete
6.2.2 Utilizzo di una metodologia alternativa basata sulla
Illustreremo di seguito come implementare una classe Graph in cui definire sia un oggetto grafo sia un iteratore adibito ad effettuare una ricerca in
t jdbc t creazione grafo t BFS ES. 1 328ms 121ms 154ms ES. 2 300ms 119ms 150ms ES. 3 320ms 114ms 156ms ES. 4 314ms 115ms 152ms ES. 5 310ms 117ms 152ms Totale 1572ms 586ms 764ms Media 314ms 117,2ms 152,8ms
Tabella 6.2: Tempi di esecuzione multiBfs con JGraphT sui nodi e gli archi della rete acquedotto
t jdbc t creazione grafo t BFS ES. 1 315ms 93ms 138ms ES. 2 304ms 97ms 102ms ES. 3 312ms 101ms 129ms ES. 4 302ms 97ms 116ms ES. 5 308ms 103ms 113ms Totale 1541ms 491ms 598ms Media 308,2ms 98,2ms 119,6ms
Tabella 6.3: Tempi di esecuzione multiBfs con JGraphT sui nodi e gli archi della rete fognaria
ampiezza.
Chiariamo bene le ipotesi del nostro problema per evitare perdite di ef- ficienza. Dato il nostro obiettivo di trovare per ogni possibile nodo radice i nodi da esso raggiungibili, è sufficiente che l’oggetto grafo memorizzi gli archi dai quali è costituito. Di conseguenza possiamo creare il nostro grafo inse- rendo solamente i nodi che costituiscono i nodi sorgente di un arco evitando di destinare uno spazio apposito ai nodi che costituiscono solo ed esclusiva- mente delle destinazioni. Mentre gli oggetti grafo disponibili con JGraphT necessitano di un insieme di vertici e di un insieme di archi che li collegano, obbligando il creatore a inserire una struttura coerente, nel nostro caso un grafo potrà essere creato solamente dagli archi e estrapolando da essi i nodi presenti.
La struttura dati in java più conveniente a rappresentare una struttura a liste di adiacenza è un HashMap indicizzata da oggetti Integer e contenente delle LinkedList. L’HashMap è una struttura dati usata per l’implemen- tazione di array associativi , strutture impiegate per rappresentare tabelle bidimensionali che associano a delle chiavi dei valori. Utilizzano una fun- zione di Hash per creare un indice con il quale accedere velocemente alla posizione desiderata. Utilizzando metodi di ricerca nominati Hashing, invece di muoversi nella struttura in funzione dell’esito dei confronti tra chiavi, si può accedere agli elementi nella tabella in modo diretto tramite operazioni aritmetiche che trasformano le chiavi in indirizzi della tabella [Wikipedia 10]. Per quanto affermato, in una tabella di hashing ben dimensionata il costo medio di ricerca di ogni elemento è indipendente dal numero di elementi.
identificano un nodo e come valori le liste di adiacenza del nodo stesso. Le singole liste sono rappresentate da delle List e l’utilizzo congiunto di queste due strutture ottimizza da un lato l’accesso casuale ai vari nodi del grafo e dall’altro l’accesso sequenziale per scorrere dato un nodo, i suoi adiacenti.
Il Codice 6.4 viene utilizzato per l’impementazione della classe Graph. Codice 6.4: Classe Graph.
1 import java.util.*;
2 public class Graph {
3 // la variabile d’istanza HashMap contiene il grafo e data la sua natura ottimizza la scansione
4 private HashMap<Integer, List<Integer>> listeAdiacenza = new HashMap<Integer, List<Integer>>();
5 //metodo d’istanza per l’aggiunta di un nuovo arco al grafo
6 public void addEdge(Integer sorg,Integer dest) {//prende come input gli estremi di un arco
7 List<Integer> adiacenti = this.listeAdiacenza.get(sorg);//individua la lista di adiacenza del nodo sorgente
8 if (adiacenti == null) {
9 this.listeAdiacenza.put(sorg,
10 adiacenti = new ArrayList<Integer>());//se il nodo non esiste aggiungo al grafo una nuova lista
11 }
12 adiacenti.add(dest);//altrimenti aggiungo alla lista il nodo destinazione 13 }
Come si vede dal codice non esiste un metodo per l’aggiunta di un ver- tice, ma è dalla valutazione degli archi che, in caso di nodo sorgente non ancora memorizzato, viene aggiunta una nuova riga all’HashMap. Il grafo si costituisce semplicemente aggiungendo gli archi che si ottengono dalla scan- sione della tabella tratta del database. Nel Codice 6.5 inseriamo il codice che implementa il metodo statico responsabile della creazione del nostro grafo.
Grazie a queste due porzioni di codice siamo in grado di creare dalla lista di archi contenuta nella tabella tratta del DB acquedotto un grafo che ricalca la rete idrica.
Codice 6.5: Metodo per la creazione del grafo.
1 import java.sql.*;
2 public class utility {
3 public static Graph createGraph(String DbUrl){
4 Graph reteIdrica=new Graph();
5 //blocco per la cattura dell’eccezioni causate dalla connessione al DBMS
6 try{
7 Class.forName("com.mysql.jdbc.Driver");
8 Connection conn = DriverManager.getConnection(DbUrl);
9 Statement stmt = conn.createStatement();
10 ResultSet rs = stmt.executeQuery("select numnodi,numnodf from tratta order by numnodi");
11 //ciclo while per il riempimento del grafo 12 while (rs.next()){
13 Integer sorg= rs.getInt("numnodi");
14 Integer dest=rs.getInt("numnodf");
15 reteIdrica.addEdge(sorg, dest); 16 } 17 rs.close(); 18 return reteIdrica; 19 } 20 catch (Exception e) { 21 System.out.println(e.getMessage()); 22 return reteIdrica ; 23 } 24 } 25 }
possibilità di creare oggetti in grado di navigare in ampiezza il grafo. Chia- meremo questa classe “BredthFirstIterator” e la organizzeremo seguendo i principi dell’algoritmo di BFS. La classe ha al suo interno tre variabili d’i- stanza, una di tipo Graph che contiene il grafo da navigare, una di tipo HashSet per mantenere gli Integer dei nodi visitati e una LinkedList per rea- lizzare la struttura a coda necessaria all’esecuzione di una visita in ampiezza. Il costruttore per la creazione di questo iteratore necessita di una variabile grafo e di una variabile Integer che indica il nodo radice dal quale l’iteratore comincerà la sua visita. Il costruttore inizializzerà l’iteratore inserendo nella coda il nodo radice.
Il prossimo passaggio consiste nella creazione di un metodo d’istanza per la classe BreadthFirstIterator che ispezionando la lista di adiacenza dei nodi
estratti dalla coda inserisca nell’HashSet i nodi visitati mano a mano dal- l’iteratore. Questo metodo sfrutterà a sua volta un metodo d’istanza della classe graph chiamato getNeighbors(Integer n) che dato un nodo restituisce la lista dei suoi adiacenti.
In questo modo l’iteratore partirà dal nodo radice inserendolo nella coda, estrarrà il primo elemento dalla coda, che alla prima iterazione sarà proprio la radice, valuterà con il metodo getNeighbors() tutti gli adiacenti inserendoli sia nell’isieme di nodi visitati sia nella coda. Se un nodo è gia stato visitato ed è quindi già presente nella lista dei visitati l’iteratore lo salterà passando al successivo non ancora scoperto.
Quando la coda si svuota significa che l’iteratore ha concluso la sua visita e sarà dunque possibile ottenere tutto il set dei nodi visitati con un semplice metodo d’istanza che chiameremo getVisited().
Dopo aver descritto i singoli passaggi nel Codice 6.6 possiamo vedere il codice che implementa la classe BreadthFirstIterator.
Adesso possiamo creare un metodo main per visitare in ampiezza il grafo e, come nel caso dell’utilizzo di jgraphT, possiamo decidere se applicarlo ad un solo nodo radice oppure a tutti i vertici del grafo.
Per la visita da una singola radice sarà sufficiente creare un oggetto grafo e un oggetto iteratoreBreadthFirst con parametri il grafo da visitare e l’intero che riferisce al nodo radice e recuperare la lista di nodi creata dall’iteratore. Per eseguire il BFS su tutti i nodi sarà invece necessario recuperare tuuti i gli indici dell’HashMap che contiene il grafo, e creare tanti iteratori quanti sono gli indici. Ricordiamo che i nodi che costituiscono solo ed esclusiva- mente delle destinazioni, senza essere sorgenti per alcun arco non vengono
Codice 6.6: Classe BreadthFirstIterator
1 import java.util.*;
2 public class BreadthFirstIterator implements Iterator<Integer> {
3 //hashset per la conservazione dei nodi visitati 4 private Set<Integer> visited = new HashSet<Integer>();
5 //coda per l’implementazione classica del BFS
6 private Queue<Integer> queue = new LinkedList<Integer>();
7 //il grafo della classe Graph 8 private Graph graph;
9
10 //costruttore dell’iteratore per BFS
11 public BreadthFirstIterator(Graph g, Integer nodoPartenza) {
12 this.graph = g;
13 this.queue.add(nodoPartenza);//aggiunge la radice alla coda
14 this.visited.add(nodoPartenza);//inserisce la radice nel set di nodi visitati
15 }
16 @Override
17 public boolean hasNext() {//restituisce false con la coda vuota 18 return !this.queue.isEmpty();
19 }
20 @Override
21 public Integer next() {
22 Integer next = queue.remove(); //rimuove la testa della coda
23 for (Integer neighbor : this.graph.getNeighbors(next)) {//trova gli adiacenti all’elemento estratto dalla coda
24 //applica i principi dell’algoritmo di ricerca in ampiezza
25 if (!this.visited.contains(neighbor)) {//valuta se il nodo in fase di visita gia stato scoperto
26 this.queue.add(neighbor);//aggiunge il nodo alla coda
27 this.visited.add(neighbor);//inserisce il nodo nei nodi visitati
28 }
29 }
30 return next;
31 }
32 public Set<Integer> getVisited(){
33 return this.visited;
34 }
35 }
memorizzati come indici ma solo all’interno delle liste dei nodi a cui sono adiacenti. Questo significa che l’iteratore verrà creato solo per quei nodi che sono sorgenti di almeno un arco, i rimanenti non verranno mai considerati come radici poichè non hanno per ipotesi alcun nodo adiacente.
Nel Codice 6.7 viene mostrato il codice per l’esecuzione del BFS partendo da tutti i nodi del grafo. Rispetto all’applicazione singola la differenza sta solo nel ciclare tutti i nodi del grafo dichiarandoli di volta in volta come radice.
Codice 6.7: metodo main per BFS su tutti i nodi
1 import java.util.*;
2 class multiBfs {
3 public static void main(String[] args) {
4 Graph reteIdrica=utility.createGraph("jdbc:mysql://localhost:3306/Acquedotto");
5 Set<Integer> allVertex=reteIdrica.VertexSet();
6 for(Integer radice:allVertex){//ciclo per scorrere tutti i nodi del grafo 7 System.out.println("RADICE:"+radice);//stampo a video il nodo radice 8 //creo l’iteratore passandogli il grafo e una radice
9 BreadthFirstIterator bfsIter=new BreadthFirstIterator(reteIdrica,radice );
10 int i=0;//variabile contatore per vedere il numero dei nodi raggiungibili 11 //inserisco il ciclo per la progressione dell’iteratore creato
12 while (bfsIter.hasNext()){
13 Integer appoggio=bfsIter.next();
14 System.out.println(appoggio);//stampo a video il nodo scoperto
15 i=i+1; 16 } 17 System.out.println(i); 18 } 19 } 20 }
Come abbiamo fatto per JGraphT controlliamo il tempo di esecuzione dell’algoritmo. Utilizzando il metodo della classe System currentTimeMillis() valutiamo il tempo di calcolo per ogni fase del programma. Inseriamo nelle Tabelle 6.4 e 6.5 il tracciamento complessivo dei tempi in modo da effettuare il confronto con i dati ottenuti analizzando l’esecuzione con JGraphT.
Nella Tabella 6.6 inseriamo i tempi di esecuzione medi di ogni componente per le due tipologie di approccio adottate.
Confrontando i valori si nota una differenza apprezzabile tra l’utilizzo di JGraphT e l’utilizzo del metodo basato sull’HashMap, soprattutto per quanto riguarda la fase di creazione dell’oggetto grafo. Inoltre possiamo vedere che la differenza tra i due metodi, sempre per quanto riguarda la fase di crezione dell’oggetto grafo, è maggiore quando la visita viene effettuata sulla rete dell’acquedotto, costituita da un numero maggiore di nodi e archi rispetto a quella fognaria.
metodo basato sull’uso dell’HashMap è ancora più efficiente.
Pur non sapendo come viene implementata la classe JGraphT e le strut- ture dati che utilizza, la motivazione di questa differenza nei tempi di esecu- zione è da ricercare nella strategia di creazione dell’oggetto grafo. JGraphT richiede l’inserimento di tutti i nodi prima di poter inserire qualsiasi arco che li collega, l’HashMap al contrario viene creato solamente inserendo gli archi della rete e i nodi vengono memorizzati sottoforma di indici e non come oggetti.
Di contro il metodo che utilizza l’HashMap non effettua alcun controllo sulla coerenza del grafo, se inserissi un arco che collega nodi non presenti nella rete, l’HashMap risultante avrebbe come indici anche nodi non pre- senti e durante l’applicazione della ricerca in ampiezza potremmo ottenere informazioni sbagliate.
Nel nostro specifico caso, poichè i dati sul grafo provengono da una strut- tura relazionale con vincoli di integrità referenziale tra le tratte e i nodi non corriamo tale rischio, altrimenti si raccomanda l’utilizzo di JGraphT, o di una classe implementata appositamente per effettuare i controlli di integrità. Il risparmio che si ottiene sull’esecuzione del BFS è conseguenza del ri- sparmio sulla fase di creazione del grafo. Poichè la complessità della ricerca dipende dalla quantità di memoria utilizzata per conservare il grafo, accedere a tutti i dati presenti nell’HashMap richiede un tempo di calcolo inferiore a quello necessario per accedere al grafo creato tramite JGraphT.
Possiamo dunque concludere che l’utilizzo di una classe basata su Hash- Map è più efficiente per la risoluzione di problemi specifici. Nel caso in cui volessimo effettuare più operazioni sul grafo oppure volessimo sfruttare
t jdbc t creazione grafo t BFS ES. 1 326ms 40ms 98ms ES. 2 322ms 41ms 97ms ES. 3 325ms 39ms 96ms ES. 4 313ms 38ms 101ms ES. 5 315ms 39ms 96ms Totale 1601ms 197ms 488ms Media 320,2ms 39,4ms 97,6ms
Tabella 6.4: Tempi di esecuzione multiBfs con classe basata su HashMap sui nodi e gli archi della rete acquedotto
t jdbc t creazione grafo t BFS ES. 1 339ms 36ms 71ms ES. 2 312ms 35ms 67ms ES. 3 310ms 34ms 74ms ES. 4 309ms 35ms 74ms ES. 5 304ms 36ms 67ms Totale 1574ms 176ms 353ms Media 314,8ms 35,2ms 70,6ms
Tabella 6.5: Tempi di esecuzione multiBfs con classe basata su HashMap sui nodi e gli archi della rete fognaria
modellizzazioni più complesse sicuramente la completezza e la profondità di JGraphT giustificherebbe la perdita di efficienza. Ad ogni modo nel nostro particolare caso, limitato all’applicazione di un BreadthFirstSearch partendo da un grafo in cui ogni arco collega nodi esistenti, risulta piu conveniente l’utilizzo di una classe opportunamente implementata.
¯
t jdbc ¯t creaz. grafo t BFS¯ T totale
Acquedotto con JGraphT 314ms 117,2ms 152,8ms 584ms
Acquedotto con HashMap 320,2ms 39,4ms 97,6ms 457,2ms
Fognario con JGraphT 308,2ms 98,2ms 119,6ms 526ms
Fognario con HashMap 314,8ms 35,2ms 70,6ms 420,6ms
Arrivati a questo punto, a prescindere dal metodo adottato, possiamo riutilizzare il driver JDBC per inserire all’interno delle basi di dati una tabella a due attributi contenente tutte le coppie di nodi connessi. Effettuando dei join tra le tabelle relative agli impianti e la tabella risultante sarà semplice individuare le connessioni presenti sulla rete e ottenere le informazioni che l’autorità richiede.
Nella prossima sezione vedremo come raggiungere lo stesso risultato uti- lizzando il linguaggio procedurale che il DBMS MySql ci mette a disposizione.
6.3
Visita sul grafo della rete idrica con stored
procedure in Pl-Sql
Purtroppo il linguaggio SQL standard non è versatile per i problemi su grafi. Ma SQL è ovunque, ed è sempre più applicato a risolvere problemi su grafo. DB2, Oracle e SQL Server sono dotati di operatori per l’elaborazione di insiemi ricorsivi, anche se tutti funzionano in modo leggermente diverso. MySQL non ha questi strumenti speciali, anche se il gruppo Open Query sta sviluppando un software engine per i grafi [Brawley 11].
Prima però di entrare nello specifico delle procedure utilizzabili per pro- blemi su grafi è necessario chiarire alcuni aspetti delle strutture dati. La lista di archi è la struttura piu adatta a rappresentare un grafo nel modello relazionale ed è il metodo con il quale abbiamo memorizzato il grafo della infrastruttura idrica nel nostro DBMS.
Figura 6.2: Esempio di memorizzazione di un grafo con modello relazionale. utilizzando un modello relazionale.
La scelta sull’instaurare o meno tra le due tabelle dei vincoli di integrità referenziale dipende da quanto è importante mantenere coerenza nella strut- tura dati. I vincoli migliorano la fase di aggiornamento e modifica del grafo, la cancellazione di un nodo causa la cancellazione di tutti gli archi in cui tale nodo è presente. Nelle basi di dati sull’infrastruttura idrica abbiamo scelto di inserire i vincoli di integrità tra le due tabelle, nodi e tratte. Essendo entrambi mirati alla produzione di report per gli enti di vigilanza la coerenza dell’informazione diventa un aspetto di primaria importanza.
Vediamo ora come sia possibile creare una procedura che ci permetta di conoscere la raggiungibilità di un nodo. L’approccio più semplice, come già abbiamo chiarito in precedenza, consiste in una visita in ampiezza del grafo partendo da un nodo che chiameremo radice. Analizziamo i passaggi da compiere per giungere al risultato che vogliamo ottenere:
1. Creo una tabella ausiliaria.
3. Aggiungo alla tabella tutti i nodi collegati a quelli già presenti, senza duplicati.
4. Ripeto lo step 3 fino a che non ho più alcun nodo da aggiungere. Per evitare di aggiungere duplicati devo sia impostare l’attributo della tabella ausiliaria come chiave primaria, sia inserire nuovi elementi tramite il comando INSERT IGNORE [Brawley 11].
INSERT IGNORE è una sintassi specifica del comando insert, in caso di violazione di indice univoco non completa l’inserimento e non restituisce errore. Di fatto la riga viene saltata in maniera trasparente. Questo me- todo si rivela molto utile in un caso come il nostro, nel quale vogliamo che nuovi valori non sostituiscano quelli vecchi e che vengano inserite solo righe realmente mancanti.
Vediamo, nel Codice 6.8, una versione base di una ricerca in ampiez- za con l’utilizzo di Pl-Sql. Successivamente, seguendo gli stessi principi, modificheremo la procedura al nostro caso specifico.
La procedura BreadthFirstSearch è quindi in grado di identificare tutti i nodi che discendono dal nodo radice. Vediamo come modificarla per adattarla al nostro problema. Cercheremo di applicare tale ricerca a partire da tutti i nodi che contengono un impianto di una categoria specifica.
Come dovremmo comportarci se volessimo sapere per ogni impainto di captazione tutti gli impianti a cui esso è collegato? Un modo per risolvere il problema è eseguire tante ricerche in ampiezza quanti sono gli impianti di captazione. Per impostare il nodo radice sequenzialemente da una captazione ad un’altra dobbiamo ricorrere ad un cursore esplicito che ci permetta di
Codice 6.8: Procedura di ricerca in ampiezza
1 PROCEDURE ‘BreadthFirstSearch‘( IN root INT )
2 --prende in input il nodo radice e restituisce il set di nodi da esso raggiungibili con annessa la loro distanza
3 BEGIN
4 -- contatore per mantenere il numero di record della tabella ausiliaria 5 DECLARE rows SMALLINT DEFAULT 0;
6 -- contatore per mantenere i livelli di profondita della ricerca, quindi la distanza dei nodi scoperti dalla radice
7 DECLARE varLevel SMALLINT DEFAULT 0;
8
9 -- creazione della tabella ausiliaria 10 DROP TABLE IF EXISTS scoperti;
11 CREATE TABLE scoperti (
12 idNodo INT PRIMARY KEY
13 ) ENGINE=HEAP;
14
15 -- inizializzo l’algoritmo aggiungendo il nodo radice alla tabella ausiliaria 16 INSERT INTO scoperti VALUES (root,,varLevel );
17 SET rows = ROW_COUNT();
18 --ciclo while per effettuare la visita 19 WHILE rows > 0 DO
20 --aggiorniamo la il contatore del numero di iterazione effettuate dal ciclo 21 SET varLevel=varLevel+1;
22 --si inserisce in reached tutti i nodi adiacenti a quelli gia presenti in reached 23 INSERT IGNORE INTO scoperti
24 SELECT DISTINCT nodoIniziale
25 FROM archi AS a
26 INNER JOIN scoperti AS s ON a.nodoIniziale= s.idNodo;
27 --manteniamo il numero di risultati ottenuti dalla query 28 SET rows = ROW_COUNT();
29 END WHILE;
30 --il ciclo si conclude quando tutti i nodi in reached non hanno adiacenti non ancora scoperti
31 --Stampo a video tutti i nodi in reached, corrispondenti a tutti i nodi raggiungibili dalla redice
32 SELECT * FROM scoperti;
33 DROP TABLE scoperti;
34 END
scorrere i risultati di una selezione sulla tabella Impianti. Ad ogni passo del cursore avvieremo la procedura di ricerca.
Questo processo, come vedremo all’interno del codice, ci obbliga a mante- nere due distinte tabelle ausiliarie, una chiamata relazioni Impianti per man- tenere i risultati complessivi di tutte le ricerche e una chiamata reached per l’esecuzione di ogni singola breadthFirstSearch. Quando la procedura avrà terminato di riempire la tabella relazioniImpianti basterà eseguire una query
in grado di associare ad ogni nodo il codice dell’impianto che è localizzato al suo interno.
All’interno del Codice 6.9 inseriamo la procedura adattata alle nostre esigenze.
Grazie all’utilizzo del cursore possiamo eseguire le ricerche limitatamente alla tipologia di impianti alla quale siamo interessati, sarà sufficiente inserire un parametro alla chiamata della procedura.
Sfruttando in gran parte lo stesso codice creiamo anche una procedura