Java – prezentacja biblioteki JUNG

24.12.2009 - Michał Karpiński
TrudnośćTrudność

Rodzaje grafów

W poprzednim przykładzie użyliśmy klasy SparseGraph do reprezentacji grafu, jednak w bibliotece JUNG znajduje się więcej klas, których można użyć we własnych projektach. Na początek przyjrzyjmy się interfejsowi, który jest bazą dla wszystkich typów grafów znajdujących się w JUNG-u.

Interfejs Graph<V,E> znajduje się w pakiecie edu.uci.ics.jung.graph. Definiuje on podstawowe operacje na grafach między innymi:

  • Dodawanie i usuwanie wierzchołków i krawędzi w grafie
  • Uzyskanie zbioru wszystkich wierzchołków i krawędzi
  • Uzyskanie informacji o połączeniach pomiędzy wierzchołkami (np. stopień)

Istnieją dwa ważne interfejsy implementujące Graph<V,E>. Są to:

  • DirectedGraph
  • UndirectedGraph

Łatwo się domyśleć, że pierwszy z nich jest bazą dla wszystkich grafów skierowanych, natomiast drugi dla grafów nieskierowanych. Lista klas implementujących te interfejsy nie jest mała:

  • DelegateForest
  • DelegateTree
  • DirectedOrderedSparseMultigraph
  • DirectedSparseGraph
  • DirectedSparseMultigraph
  • OrderedKAryTree
  • UndirectedOrderedSparseMultigraph
  • UndirectedSparseGraph
  • UndirectedSparseMultigraph

Ponadto każda z powyższych klas ma kilka podklas, co pokazuje jak bardzo rozbudowana jest biblioteka JUNG. Nie będziemy się zajmowali każdą klasą z osobna, nie trzeba też wszystkich znać na pamięć. W razie potrzeby doradzam przestudiować dokumentację (link znajduje się na ostatniej stronie artykułu).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Graph<Integer, String> g = 
new UndirectedSparseMultigraph<Integer, String>();
g.addVertex((Integer)1);
g.addVertex((Integer)2);
g.addVertex((Integer)3);
g.addEdge("Edge-A", 1, 2);
g.addEdge("Edge-B", 2, 3);
System.out.println("g = " + g.toString());
 
Graph<Integer, String> g2 = 
new DirectedSparseMultigraph<Integer, String>();
g2.addVertex((Integer)1);
g2.addVertex((Integer)2);
g2.addVertex((Integer)3);
g2.addEdge("Edge-A", 1,3);
g2.addEdge("Edge-B", 2,3, EdgeType.DIRECTED);
g2.addEdge("Edge-C", 3, 2, EdgeType.DIRECTED);
g2.addEdge("Edge-P", 2,3);
System.out.println("g2 = " + g2.toString());

Powyższy kod da takie wyjście:

The graph g = Vertices:1,2,3
Edges:Edge-B[2,3] Edge-A[1,2]
The graph g2 = Vertices:1,2,3
Edges:Edge-P[2,3] Edge-C[3,2] Edge-B[2,3] Edge-A[1,3]

Ładowanie grafu z pliku

Małe grafy są dobre do celów edukacyjnych, ale w pewnym momencie możesz zapragnąć załączyć do swojej aplikacji graf o większych rozmiarach niż te w przykładach powyżej. Wyobraź sobie ile byłoby roboty, gdybyś musiał ręcznie dodawać wierzchołki i węzły w kodzie metodami addVertex() i addEdge(). Kod stałby się bardzo długi i nieczytelny. Ponadto przy każdej zmianie struktury grafu należałoby ponownie skompilować program. Na szczęście twórcy biblioteki przewidzieli taką sytuację.

Załóżmy, że chcemy załadować nieskierowany graf z poprzedniego przykładu. Graf ten zapisany jest na dysku w pliku tekstowym o nazwie „graf.txt” – dla wygody umieścimy go w katalogu z programem. Zawartość pliku „graf.txt”:

*vertices 3
1 1
2 2
3 3
*edges
1 2
1 3

Graf musi być zapisany w odpowiednim formacie. W linii pierwszej znajduje się informacja na temat liczby wierzchołków. Po tym następuje definicja wierzchołków jako pary „numer nazwa”. Wierzchołki trzeba numerowań od 1 do n (gdzie n to liczba wierzchołków). Potem definiujemy połączenia między wierzchołkami. W naszym przykładzie pierwszy wierzchołek łączy się z drugim i z trzecim.

Teraz zmodyfikujemy nasz program. Na początek należy zaimportować pakiet odpowiadający za operacje wejścia/wejścia:

1
import edu.uci.ics.jung.io.*;

Następnie dokonujemy zmian w funkcji getGraph():

1
2
3
4
5
6
7
8
public static Graph getGraph() throws IOException{
  PajekNetReader pnr = 
new PajekNetReader(FactoryUtils.instantiateFactory(Object.class));
  Graph<Integer, Integer> g =
new UndirectedSparseGraph<Integer, Integer>();
  pnr.load("graf.txt", g);
  return g;
}

Rezultat powinien być podobny do przykładu z poprzedniego rozdziału. Na koniec gdybyśmy chcieli wyświetlić ten graf w konsoli, to dostalibyśmy takie wyjście:

g = Vertices:1,2,3
Edges:java.lang.Object@6019d0a1[1,2] java.lang.Object@3ed02b51[2,3]

Pokazuje to, że przy ładowaniu grafu z pliku, nie możemy nazywać krawędzi.

4.666665
Twoja ocena: Brak Ocena: 4.7 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com