6.2 Progettazione e realizzazione di una visita sul grafo della rete
6.2.1 Utilizzo della libreria JGraphT
JGraphT è una libreria open source di java che mette a disposizione oggetti e algoritmi derivati dalla teoria dei Grafi. Supporta l’utilizzo di varie tipologie di grafo tra cui:
• Grafi direzionati e non direzionati
• Grafi con archi pesati e non o sviluppati appositamente dall’utente • Grafi non modificabili, su cui è possibile effettuare operazioni di sola
lettura
• SottoGrafi che si aggiornano dinamicamente in base ai cambiamenti di altri grafi
• una qualsiasi composizione dei grafi precedenti
JGraphT è progettato per essere semplice e per garantire l’applicazione della teoria dei grafi a qualunque oggetto in nostro possesso. Ad esempio i vertici del nostro grafo potranno essere formati da tutti i tipi di oggetti, stringhe , interi , URL, documenti XML e altro ancora.
E’ composto da due librerie, che sono tra loro compatibili ma hanno ruoli diversi. La libreria JGraphT è incentrata sulle strutture dati e sugli algoritmi
tipici della teoria dei grafi mentre la libreria JGraph si focalizza sul rendering e sull’editing basato sulla Graphical Unity Iterface(GUI) [Naveh 14].
Le due librerie sono complementari e possono essere utilizzate insieme tramite il JGraphModelAdapter fornito da JGraphT, questo adattatore per- mette alle strutture create con JGraphT di essere usate come modello per la visualizzazione e il controllo di JGraph.
JGraphT impiega una combinatione di interfacce e classi astratte per garantire implementazioni complete e consistenti.
Gerarchia Interfacce in JGraphT • Graph.java
L’interfaccia radice nella gerarchia dei grafi. Fornisce l’oggetto Grafo G(V, E) contenente un set di V vertici e un set di E archi. Ogni arco e= (v1, v2) in E connette il vertice v1 a v2.
• UndirectedGraph.java
costituisce l’interfaccia radice per tutti i grafi i cui archi non sono direzionati.
• DirectedGraph.java
costituisce l’interfaccia radice per quei grafi in cui tutti gli archi sono direzionati.
• ListenableGraph.java
Interfaccia per grafi dipendenti da eventi di cambiamento della strut- tura.
• WeightedGraph.java
Interfaccia per grafi in cui ad ogni arco è associato un peso. Gerarchia di classi astratte in JGraphT
La Libreria di JGraphT fornisce anche una complessa gerarchia di classi astratte, tutte derivate da AbstractGraph. La gerarchia include:
• AbstractGraph.java
questa classe fornisce una implementazione base dell’interfaccia Graph ed è applicabile sia a grafi direzionati e non.
• AbstractBaseGraph.java
Questa classe fornisce una piu generale implementazione dell’interfaccia Graph. Le sottoclassi di AbstractBaseGraph aggiungono restrizioni per realizzare grafi più specifici.
AbstractGraph fornisce metodi di alto livello per effettuare operazioni su grafo come ad esempio la rimozione di tutti gli archi. Non è fatto alcun riferimento a come i vertici e gli archi vengono memorizzati [Naveh 14].
Tipi di grafi supportati in JGraphT • SimpleGraph.java
Un SimpleGraph è un grafo non direzionato nel quale tra due vertici puo esservi al massimo un singolo arco e i cicli non sono permessi. • SimpleDirectedGraph.java
Un SimpleDirectedGraph è un grafo è un grafo direzionato nel quale non sono consentiti ne multipli archi tra due vertici ne cicli.
• DefaultDirectedGraph.java
Un DefaultDirectedGraph è un grafo direzionato non semplice, ovvero permette la presenza di cicli ma non puo rappresentare la prsenza di piu archi tra due vertici.
• DefaultListenableGraph.java
Un DefaultListenableGraph è un grafo che puo essere collegato ad un’altro grafo. Le operazioni effettuate su questo grafo vengono ri- flesse sul grafo a cui è collegato. Ogni modifica effettuata si riflette simultaneamente sull’altra struttura.
Dopo questa introduzione sulla struttura, illustrata nello schema (Fig. 6.1), vediamo come utilizzare JGraphT per risolvere il nostro problema di ricerca in ampiezza.Partiamo inserendo il codice necessario all’esecuzione dell’algo- ritmo (Codice 6.1).
Grazie a questa piccola porzione di codice siamo in grado di effettuare una visita in ampiezza partendo dalla scelta di un nodo radice. il metodo statico createGraph(String DbUrl) (Codice 6.2) permette di creare il grafo passandogli la stringa di connessione al database memorizzato in MySql. Per effettuare la visita impostando come radice tutti i nodi del grafo, ottenendo quindi una foresta di alberi di copertura, basta inserire un ciclo prima di creare l’iteratore BreadthFirstIterator.
Il metodo d’istanza VertexSet() eseguito sul nostro grafo restituisce una collection di tutti i vertici, scorrendoli con un semplice ciclo for possiamo eseguire il BFS |V | volte. Chiameremo questo programma multiBFS. Al-
Figura 6.1: Gerarchia di classi della libreria JGraphT
Codice 6.1: Metodo main per esecuzione BFS.
1 import org.jgrapht.graph.DefaultEdge;
2 import org.jgrapht.traverse.*;//Classe contenente l’iteratore che esegue la visita 3 import org.jgrapht.*;
4 public class BFSwithJgraphT {
5 public static void main(String[] args ){
6 //creo il grafo con il metodo statico createGraph 7 DirectedGraph<Integer, DefaultEdge> reteIdrica=
createGraph("jdbc:mysql://localhost:3306/Acquedotto");
8 //creo un oggetto iterator per navigare in ampiezza il grafo
9 GraphIterator<Integer, DefaultEdge> iterator = new BreadthFirstIterator<Integer, DefaultEdge>(reteIdrica,nodoRadice);
10 //indice per mantenere il numero di nodi attraversati
11 int i=0;
12 //ciclo adibito a far procedere l’iteratore BreadthFirst 13 while (iterator.hasNext()) {
14 Integer appoggio=iterator.next();
15 //stampa a video l’insieme di nodi raggiungibili dal nodo radice 16 System.out.println(appoggio.intValue() );
17 i=i+1;
18 }
19 //stampo video il numero di nodi attraversati
20 System.out.println(i);
21 }
22 }
Codice 6.2: Metodo statico per creare un DirectedGraph di JGraphT.
1 import java.sql.*; //Classe utilizzata per collegamento a MySql
2 public static DirectedGraph<Integer,DefaultEdge> createGraph(String DbUrl){
3 DirectedGraph<Integer,DefaultEdge> reteIdrica=new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);
4 try{
5 Class.forName("com.mysql.jdbc.Driver");
6 //stabilisco una connessione con il DBMS
7 Connection conn = DriverManager.getConnection(DbUrl);
8 Statement stmt = conn.createStatement();
9 //eseguo la query
10 ResultSet rsNodi = stmt.executeQuery("select numnodo from nodo order by numnodo");
11 //inserisco i vertci nel grafo utilizzando i dati ottenuti dalla query 12 while (rsNodi.next()){
13 Integer vertex= rsNodi.getInt("numnodo");
14 reteIdrica.addVertex(vertex);
15 }
16 rsNodi.close();
17 ResultSet rsArchi=stmt.executeQuery("select numnodi,numnodf from tratta order by numnodi");
18 //inserisco gli archi nel grafo 19 while (rsArchi.next()){
20 Integer sorg= rsArchi.getInt("numnodi");
21 Integer dest=rsArchi.getInt("numnodf");
22 reteIdrica.addEdge(sorg, dest);
23 }
24 rsArchi.close();
25 //restituisco il grafo completo di nodi e archi 26 return reteIdrica; 27 } 28 catch (Exception e) { 29 System.out.println(e.getMessage()); 30 return reteIdrica ; 31 } 32 }
l’interno del Codice 6.3 si mostra il metodo main utilizzato per eseguire il multiBFS sul grafo prodotto dalla rete dell’acquedotto.
Non conoscendo come siano implementati internamente le classi di JGra- phT ci limitiamo a misurare le sue prestazioni inserendo dei timer per la verifica dei tempi di esecuzione.
Applichiamo il mutiBFS creato con la libreria JGraphT sulla porzione del- la rete fornitoci per la fase di testing. Inseriamo tre timer, uno per valutare il tempo di esecuzione del driver JDBC, uno per la fase di creazione dell’og- getto grafo e uno per l’applicazione dell’algoritmo di ricerca in ampiezza su
Codice 6.3: Metodo main per esecuzione multiBFS con JGraphT
1 public class multiBfs {
2 public static void main(String[] args ){
3 DirectedGraph<Integer, DefaultEdge> reteIdrica=
createGraph("jdbc:mysql://localhost:3306/Acquedotto");
4 //creo una collection dei vertici del grafo 5 Set<Integer> allVertex= reteIdrica.vertexSet();
6 //creo un iteratore BF per ogni nodo del grafo 7 for(Integer radice:allVertex){
8 System.out.println("RADICE:"+radice);
9 GraphIterator<Integer, DefaultEdge> iterator = new BreadthFirstIterator<Integer, DefaultEdge>(reteIdrica,radice); 10 int i=0; 11 while (iterator.hasNext()) { 12 Integer appoggio=iterator.next(); 13 System.out.println(appoggio); 14 i=i+1; 15 } 16 System.out.println(i); 17 } 18 } 19 }
tutti i nodi (multiBFS).
Nelle Tabelle 6.2 e 6.3 possiamo vedere il tracciamento dei tempi di ese- cuzione di ogni fase effettuato su cinque diverse applicazioni del multiBFS. La prima riguarda la rete dell’acquedotto, formata da 2303 nodi e 2360 archi, mentre la seconda riguarda la rete fognaria, costituita da 1880 nodi e1867 archi.
I valori ottenuti ci serviranno come riferimento per confrontare l’imple- mentazione con JGraphT con l’implementazione basata su hashMap presen- tata nella prossima sottosezione.