Projekt programu Inženýrská Informatika 2 Realizace grafu v jazyce Java
Ústav počítačové a řídicí techniky, VŠCHT Praha
Řešitel: Vedoucí:
Jan Hornof (ININ 258) doc. Ing. Jaromír Kukal, Ph.D.
1. Obsah 1.
Obsah ............................................................................................. 2
2.
Zadání ............................................................................................3
3.
Teorie grafů ................................................................................... 4 3.1. Neorientovaný graf ................................................................. 4 3.2. Orientovaný graf ..................................................................... 4 3.3. Souvislý graf ........................................................................... 5 3.4. Adjacenční matice ...................................................................5 3.5. Incidenční matice ....................................................................5 3.6. Úplný graf ............................................................................... 6 3.7. Eulerův cyklus ........................................................................ 6 3.8. Eulerova cesta ......................................................................... 6 3.9. Nejkratší cesta v grafu – Dijkstrův algoritmus ....................... 7
4.
Způsob řešení ................................................................................ 8 4.1. Reprezentace matic ................................................................. 8 4.2. Použití vlastních typů výjimek ............................................... 8 4.3. Třídy ........................................................................................9 4.4. Cache ...................................................................................... 10 4.5. 2D Vizualizace ........................................................................ 10
5.
Závěr ..............................................................................................13 5.1. Zhodnocení ............................................................................. 13 5.2. Zajímavá rozšíření .................................................................. 13
6.
Literatura ...................................................................................... 14
Přílohy 1. JavaDoc 2. Zdrojový kód
2 / 14
2. Zadání ●
Návrh datové struktury pro realizaci grafu
●
Vybrané operace s grafem
●
2D vizualizace grafu
●
Realizace knihovny v Javě
●
Testování knihovny
3 / 14
3. Teorie grafů Teorie grafů zkoumá vlastnosti struktur, zvaných grafy [3]. Ty jsou tvořeny vrcholy, které jsou vzájemně spojené hranami. Znázorňuje se obvykle jako množina bodů spojených čarami. Formálně je graf uspořádanou dvojicí množiny vrcholů V a množiny hran E:
G = (V, E) Pomocí grafů lze reprezentovat struktury a úlohy z nejrůznějších oborů. Taktéž mnoho problémů praktického života může být formulováno jako úloha teorie grafů - například železniční síť v Evropě je graf, kde vrcholy jsou jednotlivá nádraží a hrany jsou koleje mezi nimi. Struktura grafu může být rozšířena o ohodnocení hran (také označováno jako váha). Výsledkem je model reálné sítě. V našem příkladě je váha hrany např. počet kilometrů kolejí. Zde je vysvětlení vybraných pojmů z teorie grafů, které jsou v projektu použity a implementovány. Všechny zde použitá zobrazení grafu jsou vytvořena programem tohoto projektu.
3.1. Neorientovaný graf Neorientovaný graf G je uspořádaná dvojice G = (V, H), kde V je neprázdná konečná množina vrcholů grafu a H je množina neuspořádaných dvojic typu {u, v}, kde u ≠ v, nazývaných hrany grafu.
Obrázek 1: Neorientovaný graf
3.2. Orientovaný graf Neorientovaný graf G je uspořádaná dvojice G = (V, H), kde V je neprázdná konečná množina vrcholů grafu a H je množina neuspořádaných dvojic typu {u, v}, kde u ≠ v, nazývaných hrany grafu.
Obrázek 2: Orientovaný graf
4 / 14
3.3. Souvislý graf Souvislý graf je takový graf, kde je možné po hranách dojít z libovolného vrcholu do všech ostatních přes libovolné množství vrcholů.
3.4. Adjacenční matice Adjacenční matice je booleovská matice, jejíž sloupce i řádky jsou označeny vrcholy. Pokud je mezi dvěma danými vrcholy hrana, je na průsečiku tohoto sloupce a řádku jednička. Pro neorientovaný graf je tato matice symetrická.
0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0
Obrázek 3: Neorientovaný graf a jeho adjacenční matice
3.5. Incidenční matice Incidenční matice je booleovská matice, která reprezentuje graf, má pro každý vrchol jeden řádek a pro každou hranu jeded sloupec. Tvrzení, že (v, e) = 1 platí jen a pouze tehdy, když vrchol v je incidenční s hranou e. Z tohoto plyne, že v každém sloupci mohlou být nejvýše dvě jedničky.
1 0 0 1
Obrázek 4: Neorientovaný graf a jeho incidenční matice 5 / 14
0 1 0 1
0 0 1 1
3.6. Úplný graf Úplný graf je takový graf, kde se lze dostat jednou cestou z libovolného vrcholu do všech ostatních.
Obrázek 5: Úplný graf
3.7. Eulerův cyklus Eulerova cesta v grafu je cesta, která propojuje dva vrcholy a zároveň prochází všechny hrany právě jednou. V grafu existuje Eulerův cyklus právě tehdy, když je souvislý a všechny jeho uzly jsou sudého stupně (počet hran incidentních k danému uzlu se musí rovnat dvojnásobku počtu návštěv daného uzlu).
3.8. Eulerova cesta Eulerův cyklus je cesta, která prochází všechny hrany právě jednou a začíná i končí ve stejném vrcholu. V grafu existuje Eulerova cesta právě tehdy, když je souvislý a právě dva uzly jsou lichého stupně. Pro nalezení eulerovy cesty lze použít algoritmus rušení cyklů: Procházíme cyklickou 6 / 14
cestou, odstraňujeme navštívené hrany a koncové uzly těchto hran ukládáme do zásobníku. Pokud narazíme na uzel ze kterého už nelze jít dále, vracíme se zpět a odstraňujeme dané uzly ze zásobníku dokud nenarazíme na uzel ze kterého vedou další hrany. Odstraněné uzly ze zásobníku tvoří hledanou cestu. Dále pokračujeme hranou z daného uzlu. Časová složitost nalezení Eulerova cyklu pomocí algoritmu odstraňování cyklů je lineární.
3.9. Nejkratší cesta v grafu – Dijkstrův algoritmus Dijkstrův algoritmus [4] je algoritmus sloužící k nalezení nejkratší cesty v grafu. Je konečný (pro jakýkoliv konečný vstup algoritmus skončí), protože v každém průchodu cyklu se do množiny navštívených uzlů přidá právě jeden uzel, průchodů cyklem je tedy nejvýše tolik, kolik má graf vrcholů. Funguje nad hranově kladně ohodnoceným grafem (neohodnocený graf lze na ohodnocený snadno převést tak, že se každě hraně přiřadí váha 1). Algoritmus poprvé popsal nizozemský informatik Edsger Dijkstra. Mějme graf G, v němž hledáme nejkratší cestu. Řekněme, že V je množina všech vrcholů grafu G a množina E obsahuje všechny hrany grafu G. Algoritmus pracuje tak, že si pro každý vrchol v z V pamatuje délku nejkratší cesty, kterou se k němu dá dostat. Označme tuto hodnotu jako d[v]. Na začátku mají všechny vrcholy v hodnotu d[v] = ∞, kromě počátečního vrcholu s, který má d[s] = 0. Nekonečno symbolizuje, že neznáme cestu k vrcholu. Dále si algoritmus udržuje množiny Z a N, kde Z obsahuje už navštívené vrcholy a N dosud nenavštívené. Algoritmus pracuje v cyklu tak dlouho, dokud N není prázdná. V každém průchodu cyklu se přidá jeden vrchol vmin z N do Z, a to takový, který má nejmenší hodnotu d[v] ze všech vrcholů v z N. Pro každý vrchol u, do kterého vede hrana (označme její délku jako l(vmin, u)) z vmin, se provede následující operace: pokud (d[vmin] + l(vmin, u)) < d[u], pak do d[u] přiřaď hodnotu d[vmin] + l(vmin, u), jinak neprováděj nic. Až algoritmus skončí, potom pro každý vrchol v z V je délka jeho nejkratší cesty od počátečního vrcholu s uložena v d[v].
7 / 14
4. Způsob řešení Celý projekt byl realizován ve vývojovém prostředí NetBeans od firmy Sun MicrosystemsTM na platformě Java 1.6.
4.1. Reprezentace matic Pro reprezentaci matic byla použita knihovna JAMA: A Java Matrix Package [5]. Tento balík umožňuje jednoduché používání některých funkcí pro práci z maticemi, které jsou nativně implementovány např. v jazyce MATLAB. Před použitím knihovny je třeba jí naimportovat standardním způsobem (položka Libraries v IDE NetBeans): import Jama.Matrix; a poté se s ní dá pracovat následujícím způsobem: Matrix a, b; Matrix product = a.times(b); // násobení matic Matrix sum = a.plus(b); // sčítání matic
4.2. Použití vlastních typů výjimek V balíku graphs.exceptions jsou definovány prázdné třídy výjimek, jež dědí všechny metody z třídy Exception. Důvod pro použití těchto nových tříd je především přehlednost chybových hlášek v kódu. Samotný jazyk Java je navržen tak, aby uživatele nutil k jejich používání tímto způsobem. Použité objekty výjimek jsou následující (viz balík graph.exceptions): ●
EdgeAlreadyPresentException – hrana s danými koncovými vrcholy již v grafu existuje
●
EdgeNotFoundException – hrana nenalezena
●
GraphNotConnectedException – graf není souvislý
●
GraphNotEulerException – v grafu není eulerova cesta
●
GraphNotFullException – graf není úplný
●
LoopExcepion – počáteční a koncový vrchol hrany jsou totožné
●
MatrixNotAdjException – matice není adjacenční maticí
●
MatrixNotIncException – matice není incodenční maticí
●
PathsNotConnectedException – cesty neobsahují společný vrchol
●
VertexAlreadyPresentException – vrchol se zvoleným ID již v grafu existuje
●
VertexNotFoundException – vrchol nenalezen
8 / 14
4.3. Třídy Zde je stručný popis jednotlivých tříd s jejich základními vlastnostmi a metodami. Kompletní specifikace všech metod a vlastností naleznete v příloze 1. ●
class Constants – konstanty v projektu
●
●
●
●
DEBUG – pokud je true, vypisují se ladící informace
class Edge – reprezentuje hranu
start – počáteční vrchol hrany
end - koncový vrchol hrany
weight – váha hrany
incMatrixIndex – index hrany v incidenční matici
class Vertex – reprezentuje vrchol
degree – stupeň vrcholu
inDegree – počet hran směřujících do vrcholu
outDegree - počet hran vycházejících z vrcholu
neighbours – list sousedních vrcholů
matrixIndex - index vrcholu v adjacenční nebo incidenční matici
posX – pozice na ose X (pro vizualizaci)
posY – pozice na ose Y (pro vizualizaci)
class Path – reprezentuje cestu
addVertex() - přidání vrcholu
getCost() - cena cesty
mergeWithPath() - spojení dvou cest do jedné
clone() - klonování cesty (java interface Cloneable)
abstract class Graph – reprezentuje graf
addEdge() - přidá hranu
addVertex() - přidá vrchol
getConnectionMatrix() – matice souslednosti
getIncMatrix() - incidenční matice
getAdjMatrix() – adjacenční matice
isConnected() - je souvislý 9 / 14
toSvg() - generovani SVG
saveSvgToFile() - zapsani SVG do souboru
copy() – vytvoření kopie grafu
getShortestPath() – nejkratší cesta v grafu podle počtu vrcholů
getShortestPathFW() – nejkratší cesta v grafu podle váhy hran
●
class Ugraph extends Graph - reprezentuje neorientovaný graf
●
class DiGraph extends Graph - reprezentuje orientovaný graf
●
class GraphFactory – vytváří grafy z matic
●
diGraphFromAdjMatrix – vytvoří orientovaný graf z adjacenční matice
diGraphFromIncMatrix – vytvoří orientovaný graf z incidenční matice
uGraphFromAdjMatrix – vytvoří neorientovaný graf z adjacenční matice
uGraphFromIncMatrix – vytvoří neorientovaný graf z incidenční matice
class GraphTest – testovací třida s příklady
4.4. Cache Ve třídě Graph se používa cache, ve které je uložena incidenční, adjacenční matice a nejkratší cesta, aby se zamezio počítání těchto dat několikrát, když se matice nezmění. Pokud se graf změní, je třeba vyprázdnit cache metodou Graph.resetCache(), což se děje automaticky při změně struktury matice metodami addVertex() nebo addEdge(). Jakmile se potom zavolá některá z funkcí vracející chacheovatelná data, cache se naplní novými údaji.
4.5. 2D Vizualizace Pro 2D vizualizaci grafu byl použit formát Scalable Vector Graphics (SVG) [6]. Jedná se o v současné době nejrozšířenější formát pro vektorovou grafiku a lze zobrazovat například v jakémkoli moderním webovém prohlížeči. Tento formát je založen na specifikaci jazyka XML. Pro reprezentaci grafu byly použity následující elementy: ●
pro vrchol
●
pro hranu, váha hrany je vizualizována pomocí atributu stroke-width
●
pro názvy a popisky 10 / 14
Vlastní generování SVG kódu obstarává metoda Graph.toSvg() Graph.saveSvgToFile() jej ukládá do souboru (viz JavaDoc v příloze 1).
a
metoda
Příklad grafu v SVG:
Obrázek 6: Příklad vygenerovaného grafu s různými vahami hran
Zdrojový kód SVG: <svg width="100%" height="100%" version="1.1" xmlns="http://www.w3.org/2000/svg">
V1 V2 V3 V4
11 / 14
V5 V6 V7 V8
12 / 14
5. Závěr 5.1. Zhodnocení Pří řešení se ukázalo velmi výhodné použít již hotovou knihovnu JaMa. Vhodným rozdělením kódu projektu do tříd bylo docíleno přehlednosti a umožněno velmi pohodlné pracování s napsanými metodami v dalším kódu např. v testovací třídě. Projekt umožňuje kromě konstruování grafu také jeho 2D zobrazování a provádění některých operací výše popsanými algoritmy.
5.2. Zajímavá rozšíření Bylo by zajímavé z kódu vytvořit servlet a z něj interaktivní aplikaci pro generování a zobrazování grafů s importem některého z popsaných typů matic z CSV nebo XML; zjednodušeně řečeno WYSIWYG editor grafů. Ve všech moderních prohlížečích je již možné se SVG aktivně manipulovat pomocí JavaScriptu, takže by bylo možné, aby zobrazovací engine byl schopen obsluhovat události a dynamicky měnit vzhled SVG. Změny by se přenášely ve formátu JSON pomocí AJAX requestů na server, který by byl schopen vygenerovat zpět upravené SVG, popř. jiné XML nebo matici v CSV.
13 / 14
6. Literatura [1] [2] [3] [4] [5] [6] [7]
Reference Resources for Java. [online]. [cit. 2008-05-01].
. Wikipedia – Matrix. [online]. [cit. 2008-05-01]. . Wikipedia – Graph. [online]. [cit. 2008-05-01]. . Dijkstrův algoritmus. [online]. [cit. 2008-05-06] JAMA: A Java Matrix Package. [online]. [cit. 2008-03-01]. Scalable Vector Graphics. [online]. [cit. 2008-04-15] Graph Theory. [online]. [cit. 2008-05-01].
14 / 14
