PŘÍRODOVĚDECKÁ FAKULTA UNIVERZITY PALACKÉHO KATEDRA INFORMATIKY
BAKALÁŘSKÁ PRÁCE
Vybrané grafové algoritmy
2014
Petr Pavelčík
Anotace V této práci se budeme zabývat vybranými kapitolami z teorie grafů. Z grafových algoritmů vybereme algoritmy hledání nejkratších cest v grafu, minimální kostra grafu, a vrcholové barvení grafů. Pro demonstraci jednotlivých algoritmů byla vytvořena aplikace přiložená k této práci.
Děkuji RNDr. Arnoštu Večerkovi za konzultace a trpělivé vedení při tvorbě této práce. Dále děkuji za podporu své rodině a přátelům, jmenovitě Petru Hrbkovi za neocenitelnou pomoc při tiskařských službách.
Obsah 1. Úvod
8
2. Definice užitých pojmů
9
3. Algoritmy 3.1. Dijskrův algoritmus . . . . . . . . . . . 3.1.1. Popis algoritmu . . . . . . . . . 3.1.2. Pseudokód . . . . . . . . . . . . 3.1.3. Shrnutí . . . . . . . . . . . . . . 3.2. Floyd-Warshallův algoritmus . . . . . . 3.2.1. Popis algoritmu . . . . . . . . . 3.2.2. Pseudokód . . . . . . . . . . . . 3.2.3. Shrnutí . . . . . . . . . . . . . . 3.3. Kruskalův algoritmus . . . . . . . . . . 3.3.1. Popis algoritmu . . . . . . . . . 3.3.2. Pseudokód, část I. . . . . . . . 3.3.3. Pseudokód, část II. . . . . . . . 3.3.4. Shrnutí . . . . . . . . . . . . . . 3.4. Algoritmy pro vrcholové barvení grafu 3.5. Sousedské barvení vrcholů . . . . . . . 3.5.1. Popis algoritmu . . . . . . . . . 3.5.2. Pseudokód . . . . . . . . . . . . 3.5.3. Shrnutí . . . . . . . . . . . . . . 3.6. Barvení pomocí nezávislých množin . . 3.6.1. Popis algoritmu, část I. . . . . . 3.6.2. Popis algoritmu, část II. . . . . 3.6.3. Pseudokód . . . . . . . . . . . . 3.6.4. Shrnutí . . . . . . . . . . . . . . 3.7. Barvení slepováním vrcholů . . . . . . 3.7.1. Popis algoritmu . . . . . . . . . 3.7.2. Pseudokód . . . . . . . . . . . . 3.7.3. Shrnutí . . . . . . . . . . . . . . 3.8. Exaktní barvení . . . . . . . . . . . . . 3.8.1. Popis algoritmu . . . . . . . . . 3.8.2. Pseudokód . . . . . . . . . . . . 3.8.3. Shrnutí . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 12 12 12 13 14 14 14 15 18 18 19 20 21 23 24 24 24 25 26 26 27 28 28 29 29 29 30 31 31 31 33
4. Uživatelská příručka 4.1. Spuštění . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Okno Aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1. Komponenta grafu . . . . . . . . . . . . . . . . . . . . . .
34 34 34 34
4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2. Menu Soubor . . . . . . . . 4.2.3. Menu Úpravy . . . . . . . . 4.2.4. Menu Nápověda . . . . . . . 4.2.5. Ovládací panel demonstrace 4.2.6. Možnosti sekce Zobrazit . . 4.2.7. Sekce Algoritmus . . . . . . 4.2.8. Ovládací tlačítka . . . . . . 4.2.9. Zpoždění . . . . . . . . . . . 4.2.10. Postup . . . . . . . . . . . . 4.3. Okno Editor . . . . . . . . . . . . . 4.3.1. Menu Soubor . . . . . . . . 4.3.2. Menu Úpravy . . . . . . . . 4.3.3. Ovládací panel editoru . . . 4.3.4. Informační panel editoru . . 4.3.5. Dialog Náhodný graf . . . . 4.4. Prográmatorská část . . . . . . . . 4.4.1. Tvorba aplikace . . . . . . . 4.4.2. Třídy . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
34 34 35 35 35 35 36 36 36 36 37 37 37 37 37 38 38 38
Závěr
40
Reference
41
A. Obsah přiloženého CD
42
5
Seznam obrázků 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
Hranově ohodnocený graf. . . . . . . . . . Nezávislá množina vrcholů. . . . . . . . . . Kořen stromu. . . . . . . . . . . . . . . . . Demonstrace Dijskrova algoritmu. . . . . . Informace v postupu. . . . . . . . . . . . . Demonstrace Floyd-Warshallova algoritmu. Nejkratší cesta z vrcholu 7 do vrcholu 8. . Tabulka nejkratších cest. . . . . . . . . . . Kruskalův algoritmus, výchozí graf. . . . . Kruskalův algoritmus, výpočet dokončen. . Vrcholově obarvený graf. . . . . . . . . . . Vrcholově barvený graf. . . . . . . . . . . . Barvení slepováním vrcholů, postup. . . . Okno aplikace, výpočet dokončen. . . . . . Okno editoru, úprava grafu. . . . . . . . .
6
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
9 10 11 13 13 16 17 17 21 22 23 26 30 35 36
Seznam tabulek
7
1.
Úvod
Cílem této práce je vytvořit aplikaci, která bude demonstrovat průběh vybraných algoritmů pracujících s daty ve formě grafů. Součástí je editor pro pro sestavení a editaci grafu splňující funkčnost pro potřeby vybraných algoritmů (například možnost změny ohodnocení hran pro Dijskrův, Kruskalův a Floyd-Warshallův algoritmus). Graf vytvořený v editoru bude možné uložit a zpětně načíst ve vhodném formátu. V aplikaci bude možné řešit vybrané úlohy s algoritmy s polynomiální složitostí (nalezení nejkratší cesty, hledání minimální kostry) i úlohy obtížnější (barvení grafu). Nejprve si zadefinujeme pojmy užívané v kapitolách věnujících se algoritmům. Následují konkrétní algoritmy, jejich využití, řešení a výsledky. V uživatelské příručce si popíšeme význam jednotlivých komponent aplikace a editoru. Prográmátorská část se věnuje užitým technologiím a popisům jednotlivých tříd.
8
2.
Definice užitých pojmů
Úvodem si zavedeme několik pojmů, které budeme používat v dalších částech této práce. V následujících kapitolách budeme pracovat s neorientovanými grafy. Definice vycházejí ze zdrojů [2] [3]. Definice 2.1. Vrchol v grafu označuje nějaký objekt. Například rodinný strom se dá převést do podoby grafu, kde jednotlivé vrcholy budou představovat rodinné příslušníky. Nejstarší členové rodiny (např. prarodiče) zakreslime do nejvyšší části grafu. Potomci se vždy zakreslují pod jejich rodiče (v našem případě budeme stromy takto kreslit). Vrcholy budeme v této práci zakreslovat pomocí kružnic. Definice 2.2. Hrana Vyjadřuje vztah mezi vrcholy. Pokud navážeme na příklad z předhozí definice, hrany mohou vyjadřovat vztah rodič - potomek. Když kreslíme hranu má začátek i konec v nějakém vrcholu. Definice 2.3. Graf G(V, E) je struktura ⟨V, E⟩ složená z konečné množiny vrcholů V = {v1 , v2 , . . . , vn } a konečné množiny hran E = {e1 , e2 ...en }. Každou hranu ei tvoří nějaké dva vrcholy u, v ∈ V . Definice 2.4. Hranově ohodnocený graf je dvojice (G, c), kde G je neorientovaný graf G(V, E) a c budeme chápat jako zobrazení c : E → R+ 9 5 10 2 5 6
Obrázek 1. Hranově ohodnocený graf. Definice 2.5. Sled v grafu G(V, E) je posloupnost v0 , e 1 , v 1 , e 2 , . . . , e n , v n vi ∈ V jsou vrcholy, ej ∈ E jsou hrany. Pro hrany platí: ei = {vi−1 , vi} pro i ∈ {1, . . . , n} 9
Definice 2.6. Cesta v grafu G(V, E) je sled, ve kterém se neopakuje žádný vrchol. Definice 2.7. Cena cesty P v hranově ohodnoceném grafu je ∑ c(e) e∈P
Definice 2.8. Nejkratší cesta. Je dán graf G(V, E). Víme, že u, v ∈ V . Nejkraší cesta P v grafu G z vrcholu v do vrcholu u je cesta s nejmenší cenou sumy hranového ohodnocení. Definice 2.9. Kružnice v grafu G(V, E) je cesta, která vede z vrcholu vi přes hranu ei taková, že existuje cesta do vrcholu vi přes hranu ej , přicemž ei ̸= ej . Definice 2.10. Podgraf grafu G(V, E) je graf G′ (V ′ , E ′ ):
V′ ⊆V E′ ⊆ E Graf G′ obsahuje jen hrany ei = {u, v} ∈ E, kde u, v ∈ V ′ . Definice 2.11. Souvislý graf G(V, E) označuje strukturu ve které platí, že ∀vi ∈ V existuje cesta P do ∀vj ∈ V, tak že vi ̸= vj . Definice 2.12. Úplný graf. Je dán graf G(V, E). Pokud existuje hrana {u, v} ∈ E pro ∀u, v ∈ V řekneme, že graf G je úplný (u ̸= v). Definice 2.13. Nezávislá množina vrcholů V ′ ∈ V v grafu G(V, E) je když platí ∀u, v ∈ V ′ , že hrana {u, v} ⊈ E
Obrázek 2. Nezávislá množina vrcholů. ′ ⊆V Definice 2.14. Maximální nezávislá množina je nezávislá množina Vmax ′ ze všech nezávislých množin V , které existují v množině vrcholů V největší. Maximální nezávislou množinu můžeme vidět na obrázku 2.
10
′ |Vmax | ≥ ∀|V ′ | ∈ V
Definice 2.15. Chromatické číslo grafu je číslo označující nejmenší počet barev potřebných k vrcholovému obarvení grafu. Definice 2.16. Strom je souvislý neorientovaný graf bez kružnic. Definice 2.17. Kořen stromu G(V, E) je vrchol r ∈ V , který má v grafu zvlaštní postavení. Nemá žádného předchůdce a nacházi se zde pouze jeden.
Obrázek 3. Kořen stromu. Definice 2.18. Kořenový strom je dvojice (G, r), kde G = (V, E) je strom a r ∈ V je kořen. Definice 2.19. Variace bez opakování z n prvků je uspořádaná k-tice složená z prvků n, kde se každý z těchto prvků vyskytuje nejvýše jednou. Definice 2.20. Variace s opakováním z n prvků je uspořádaná k-tice složená z prvků n, kde dovolujeme, aby se jeden prvek opakoval nejvýše k-krát. Definice 2.21. Výška stromu odpovídá počtům úrovní od kořene k listům. Úrovně ve stromu odpovídá postupu o jeden uzel níže ve stromové struktuře. Jako list označujeme vrchol, ze kterého nevede žádná hrana. Definice 2.22. Minimální kostra grafu souvislého grafu G(V, E) je podgraf G′ (V, E ′ ), kde množina vrcholů G′ a G je schodná. Pro množinu hran platí E ′ ⊆ E a |E ′ | = |V | − 1, tak že graf zůstane souvislý. Minimální kostra grafu má cenu cesty P ′ ze všech možných cest P v grafu G nejmenší. U vybraných algoritmů bude zmíněn pojem asymptotická složitost algoritmů. Znalost se u čtenáře předpokládá.
11
3.
Algoritmy V této sekci se budeme zabývat konkrétními algoritmy.
3.1.
Dijskrův algoritmus
Tento algoritmus vymyslel nizozemský informatik Edsger Dijkstra v roce 1956. Algorimus nalezne všechny nejkratší cesty z vybraného vrcholu v kladně hranově ohodnoceném grafu. [6] 3.1.1.
Popis algoritmu
Následující sekce čerpá ze zdroje [5]. Hranové ohodnocení grafu definujeme pomocí následujícího zobrazení f : E → R+ Na vstupu algoritmu je dán startovní uzel s ∈ V . Algoritmus pracuje s množinou A, která obsahuje doposud nenavštívené vrcholy a množinou N, do které přesouvá již navštívené vrcholy. Na výstupu máme ∀v ∈ V \{s} délku nejkratší cesty z s do v, značíme t(v). t(v) = minimum{t(u)|u ∈ A} 3.1.2.
Pseudokód
Jednotlivé kroky algoritmu můžeme shrnout do následujícího pseudokódu: 1. Přiraď do množiny A všechny vrcholy z množiny vrcholů V 2. t(s) = 0 3. pro v ∈ V \{s} proved d(v) = ∞ 4. pokud neexistuje žádný vrchol v ∈ V , tak že t(v) ̸= ∞ skonči 5. najdi nejmenší t(v) z vrcholů v ∈ A a ulož jej do m 6. N = {∀v ∈ A|t(v) = m}, odeber tyto vrcholy z A 7. ∀v ∈ N, ∀u ∈ A takové, že hrana {v, u} ∈ E provedeme:
jestliže t(v) + f (v, u) < t(u) potom: t(u) = t(v) + f (v, u), pokračuj bodem 4. 12
3.1.3.
Shrnutí
Pro daný vrchol s ∈ V jsem schopni nalézt nejkratší cesty do všech jeho vrcholů ∀v ∈ V \{s}. S použitím prioritní fronty vrcholů dosáhneme časové složitosti O(|V |2 ). Ke třídění můžeme použít třídící algoritmus quicksort s časovou složitostí v nejhorším případě O(n2 ), kde n = |V |.
Obrázek 4. Demonstrace Dijskrova algoritmu. Na obrázku je modrou hranicí zvýrazněn startovní vrchol. Doposud nenavštívené vrcholy mají hodnotu ∞.
Obrázek 5. Informace v postupu.
13
3.2.
Floyd-Warshallův algoritmus
Slouží k nalezení nejkratší cesty mezi libovolnými dvěma vrcholy grafu, tzv. „All shortesht path“ algoritmus. Budeme vycházet ze zdroje [4]. 3.2.1.
Popis algoritmu
Vstupen algoritmu je neorientovaný graf G(V, E) a hranové ohodnocení c: c:E→Q které je zobrazením přiřazující hranám grafu racionální hodnotu.1 Na začátku si vytvoříme dvě dvojrozměrné pole D, P o velikosti |V | × |V | Pro každé dva indexy vrcholů i, j ∈ {0 . . . |V | − 1} provedeme D[i, j] = ∞ P [i, j] = ∞ Pro ∀{i, j} ∈ E uložíme hranové ohodnocení c({i, j}) na pozici i, j v poli D uchovávajícím délku nejkratší cesty z vrcholu i do j. D[i, j] = c({i, j}) Při nalezení kratší cesty z vrcholu i do j přes nějaký vrchol h ∈ E ukládáme hodnotu nejkratší cesty na pozici i, j v poli D. D[i, j] = D[i, h] + D[h, j] Zároveň si ukládáme do pole P informaci, přes který vrchol vede aktuální nejkratší cesta z vrcholu i do j. P [i, j] = h 3.2.2.
Pseudokód
Průběh algoritmu shrnuje následující pseudokód.
1
Algoritmus nefunguje pro grafy se zápornými cykly. Záporný cyklus v grafu poznáme podle záporné sumy hranového ohodnocení.
14
Algorithm 3.1. Floyd-Warshallův algoritmus, hledaní nejkratší cesty mezi libovolnými dvěma vrcholy 1: procedure FloydWarshall(G(V, E), c) 2: Vytvoř dvojrozměrné pole D, P o velikosti n × n, kde n = |V | 3: ∀i, j ∈ {0...n − 1} proveď D[i, j] = ∞, P [i, j] = ∞ 4: for all {u, v} ∈ E do 5: D[i, j] ← c({i, j}) 6: end for 7: for k ← 0 to n − 1 do 8: for i ← 0 to n − 1 do 9: for j ← 0 to n − 1 do 10: x ← D[i, k] + D[k, j] 11: if x < D[i, j] then 12: D[i, j] ← x 13: P [i, j] ← k 14: end if 15: end for 16: end for 17: end forreturn 18: ⟨D, P ⟩ 19: end procedure K sestavení nejkratší cesty mezi libovolnými dvěma vrcholy potřebujeme pomocnou rekurzivní funkci: Algorithm 3.2. Procedura F indP ath z pole P zřetězí vrcholy vi , . . . , vj přes které vede nejkratší cesta z u do v 1: procedure FindPath(P, i, j) 2: conn = P [i, j] ▷ spojující vrchol přes který povede cesta 3: if conn = ∞ then ▷ pokud cesta neexistuje 4: return [] 5: else 6: return F indP ath(P, i, conn) + ⟨conn⟩ + F indP ath(P, conn, j) 7: end if 8: end procedure
3.2.3.
Shrnutí
Algoritmus ve třech vnořených cyklech porovná délku všech cest mezi každými dvěma vrcholy grafu. Postupným zkoušením všech cest přes různé vrcholy dochází ke zlepšování výsledků doposud nejkratší nalezené cesty. 15
Pro ukládání informací o nějlepší nalazené cestě (s nejmenší cenou hran) využíváme dvě dvojrozměrná pole P, D. Jejich velikost je |V |2 . Paměťová složivost algoritmu je O(|V |2 ). Ze třech vnořených cyklů algoritmu 3.1 můžeme odvodit konečnou složitost O(|V |3 ). Algoritmus je výhodné použít pro malé vstupy (řádově tisíce).
Obrázek 6. Demonstrace Floyd-Warshallova algoritmu. Na obrázku jsou zeleně vrcholy, mezi kterými se hledá cesta. Oranžově je vybarven spojující vrchol, přes který cestu hledáme.
16
Obrázek 7. Nejkratší cesta z vrcholu 7 do vrcholu 8. Jiný příklad. V tabulce na diagonále porujeme červeně zvýrazněná pole se zápornými hodnotami. Tyto vrcholy jsou v záporném cyklu (zjistíme podle sloupce nebo řádku). Pokud přes ně povede cesta, procedura FindPath nedokáže skončit (cena cesty se opětovným průchodem přes vrchol neustále zlepšuje).
Obrázek 8. Tabulka nejkratších cest.
17
3.3.
Kruskalův algoritmus
Nalezne minimální kostru hranově ohodnoceného grafu jak je definovaná v části 2.22. Budeme vycházet ze zdroje [4]. 3.3.1.
Popis algoritmu
Vstupem algoritmu je ohodnocený neorientovaný graf G(V, E). Je dáno hranové ohodnocení c : E → R+ . Na výstupu je graf G′ (V, E ′ ), který má množinu vrcholů stejnou jako graf G. Suma ohodnocení hran E ′ ⊆ E, odpovídá požadavkům na minimální kostru grafu. V každém iteraci algoritmu tedy budeme do množiny E ′ přidávat hranu s nejmenším ohodnocením c(e) a zároveň bude platit, že přidání této hrany do množiny E ′ nevytvoří kružnici. 2.9. Před spuštěním samotného algoritmu je vhodné provést následující: • hrany nejprve setřídíme vzestupně2 • zvolíme efektivní způsob hledání k ružnice v grafu vytvořením tzv. disjoint set structure.3 Kolekci disjunktních množin označíme S = {S1 , S2 . . . Sn }, kde S1 , S2 . . . Sn jsou disjunktní množiny jednoznačně rozpoznatelné (nějakým) vybraným zástupcem. Jednotlivé množiny tvoří kořenové stromy. 2.18. Každý uzel uchovává ukazatel na svého předka (parent) ve stromu. Kořenový uzel stromu odkazuje sám na sebe. Hodnotou rank označujeme horní výšku podstromu generovaného daným vrcholem. Nad disjoint set structure provádíme následující operace4 : M akeSet(x) přidá do kolekce novou množinu, jejímž prvkem je x U nion(x, y) v kolekci množin sjednotí množunu obsahující prvek x a množinu obsahující prvek y. Původní množiny obsahující prvky x, y jsou z kolekce množin osatraněny. F indSet(x) vrací zástupce množiny obsahující prvek x z kolekce množin. 2 Kvůli efektivitě můžeme zvolíme algoritmus s časovou složitostí O(n log n) např. Quicksort, Mergesort. 3 Označuje kolekci disjunktních množin, z nichž je každou možné jednoznačně určit dle vybraného zástupce (prvku) z této množiny. V případě Kruskalova algoritmu je můžeme zvolit libovolný prvek. Volba zástupce je vždy jednoznačná, pokud jej nějaká operace nad disjoint set structure nezmění. 4 Argumenty operací označují vrcholy stromu.
18
Pseudokódem bychom mohli procedury zapsat takto: 3.3.2.
Pseudokód, část I.
V této části si představíme práci se strukturou pro ukládání disjunktních množin. Algorithm 3.3. Procedury pracující se strukturou disjoint set 1: procedure makeSet(x) 2: x.parent ← x 3: x.rank ← 0 4: end procedure 5: procedure findSet(x) 6: if x ̸= x.parent then 7: x.parent ← f indSet(x.parent) 8: end if 9: return x.parent 10: end procedure 11: procedure union(x,z) 12: rx ← f indSet(x) 13: ry ← f indSet(y) 14: if rx .rank > ry .rank then 15: ry .parent ← rx 16: else 17: rx .parent ← ry 18: if ry .rank = rx .rank then 19: ry .rank ← ry .rank + 1 20: end if 21: end if 22: end procedure
V proceduře findSet hledáme kořen směřem od vrcholu ke kořenu. Její šložitost je tedy v nejhorším případě O(n), kde n označuje velikost množiny vrcholů procházeného stromu. Procedura findSet je nejsložitější operací, která bude nad strukturou disjoint set structure prováděna. V jednotlivých procedurách provádíme operace, které zajistí, že strom nebude příliš vysoký. Procedura findSet nalezne kořen stromu do kterého patří prvek x, který jej jejím argumentem. Zároveň procedura findSet sníží výšku stromu změnou rodiče všech procházených vrcholů na nalezený kořen stromu.
19
Procedura union sjednotí dvě množiny připojením nižšího stromu jako potomka vyššího stromu. Procedura mění rank stromu pouze tehdy, když mají stromy stejnou výšku. Můžeme pozorovat, že po připojení takového stromu pod kořen stromu se stejnou výškou bude výška nově vzniklého stromu o jedna větší. Na začátku Kruskalova algoritmu vytvoříme kolekci jednoprvkových množin, kde prvky představují vrcholy grafu. Přidání hrany do řešení, v průběhu algoritmu znamená sjednocení dvou množin obsahující vrcholy, které tvoří vybranou hranu.K testování vzniku kružnice voláme proceduru findSet na oba vrcholy tvořící hranu. Pokud se kořenové vrcholy vrácené procedurou findSet liší, hrana patří do řešení. 3.3.3.
Pseudokód, část II.
Popíšeme si kroky algoritmu. 1. Vytvoříme prioritní frontu hran Q. Frontu můžeme reprezentovat jako setřízené pole. Hrany jsou podle jejich ohodnocení c(e) setříděny vzestupně. 2. Vytvoříme si pole A jehož velikost je rovna |V |. Každý prvek pole obsahuje položky rank a parent. Položka rank v sobě nese informaci o maximální hloubce podstromu vrcholu. Položka parent nese odkaz na předchůdce (vrcholu ve stromové struktuře). Prvek A[i] odpovídá vrcholu i. 3. Inicializujeme jednoprvkové komponenty grafu zavoláním makeSet(A[i]) pro i ∈ {0, 1...|V − 1|} 4. Vytvoříme prázdnou množinu E ′ . 5. Dokud nemáme kostru grafu, tedy |E ′ | < |V | − 1 provedeme v cyklu: odebrat z Q hranu {u, v} pokud f indSet(A[u]) ̸= f indSet(A[v]) potom sjednotit E ′ ∪ {{u, v}} provést union(A[u], A[v]) 6. konec cyklu 7. vrátit minimální kostru grafu (V, E ′ )
20
3.3.4.
Shrnutí
Složitost setřídění množiny hran je O(|E| log |E|), vytvoření pole A má složitost O(|V |). Počet operací prováděných nad disjoint set structure je v nejhorším případě lineární vzhledem k |E|. Operace představují činnost procedury makeSet jsou zanedbatelné. Algoritmus vyžaduje souvislý graf, pro který platí |E| >= |V | − 1. Výsledná složitost algoritmu je O(|E|log|E|). Před spuštěním vypadá graf v sekci demonstrace následovně:
Obrázek 9. Kruskalův algoritmus, výchozí graf. Po skončení výpočtu Kruskalova algoritmu dostáváme minimální kostru grafu.
21
Obrázek 10. Kruskalův algoritmus, výpočet dokončen.
22
3.4.
Algoritmy pro vrcholové barvení grafu
Barvení vrcholů grafu se používá při přidělování omezeného množství prostředků. V informatice vrcholové barvení můžeme využít k řešení problému vyhýbání se uváznutí (deadlock). Jiným příkladem je přidělování vzdušného prostoru při dodržení pravidel letového provozu aerolinií. Barvení grafu lze také využít k řešení hry Sudoku. V následujících kapitoly čerpají ze zdrojů [3][2]. Vrcholové barvení pro graf G(V, E) můžeme zavést jako následující zobrazení: col : V → C takové, že pro všechny hrany {v, u} ∈ E platí col(v) ̸= col(u) kde množina C představuje kolekci barev.
Obrázek 11. Vrcholově obarvený graf. Vrcholové baverní je NP-úplný problém.2 V praxi se k barvení grafu použivají heuristické algoritmy, které nemusejí ve všech připadech vracet optimalní řešení. Představíme si rovněž exaktní algoritmus pro barvení grafu v kapitole 3.8.
2
NP označuje třídu problému, jejichž časová složitost není polynom (např. n!). Další třídou problému je P, která označuje prakticky řešitelné problémy s polynominální složitostí.
23
3.5.
Sousedské barvení vrcholů
Představíme si první heuristický algoritmus barvení vrcholů grafu. Tento algoritmus obarvuje vrcholy na základě informací o počtu a aktuálním obarvení sousedů. 3.5.1.
Popis algoritmu
Na počátku nastavíme aktuální použitou barvu na nula color = 0. Následující kroky provádíme v cyklu:
Vytvoříme množinu doposud neobarvených vrcholů. Pokud tato množina obsahuje více než jeden uzel, provedeme následující filtraci: 1. Vytvoříme množinu vrcholů, pro které platí, že mají množinu sousedních vrcholů obarvenou co největším počtem různých barev (toto číslo označme r). Pokud není množina jednoprvková, tedy více vrcholů je obarveno různým početem barev r, pokračujeme ve filtraci 2. 2. Vytvoříme množinu vrcholů, které mají největší počet neobarvených sousedů (označme jako číslo w). Pokud tato množina není jednoprvková, zvolíme libovolný vrchol. Předchozími kriterii prošel jen jeden uzel, označíme jej u. V další části algoritmu najdeme nejnižší barvu c, kterou obarvíme vrchol u. Barvou c nesmí být obarven žádný ze sousedů vrcholu u. Vrchol u obarvíme: col(u) = c. Pokud jseme vybrali doposud nepoužitou barvu, aktualizujeme hodnotu color = c. Pokračujeme v cyklu, dokud neobarvíme všechny vrcholy grafu. Hodnota color je po skončení algoritmu rovna početu barev, kterými je graf obarven. 3.5.2.
Pseudokód
24
Algorithm 3.4. Sousedské barvení grafu 1: procedure neighbourColoring(graph) 2: color = 0 3: while uncoloredV ertices(graph) > 0 do ▷ dokud není obarven graf 4: H ← getU ncoloredV ertices(graph) ▷ vybereme neobarvené vrcholy 5: u ← f ilterU ncoloredV ertices(H) ▷ vyfiltrujeme uzel pro barvení 6: c = selectColor(color) ▷ vybereme nejmenší možnou barvu 7: col(u) = c ▷ obarvíme uzel 8: if c > color then 9: color ← c ▷ nová barva, aktualizujeme hodnotu color 10: end if 11: end while 12: end procedure 3.5.3.
Shrnutí
Z popisu filtrace vyplývá, že způsob jakým vybírame vrcholy u povede na vrcholové obarvení grafu jak je uvedeno v kapitole 3.4. Část algoritmu zodpovědná za výběr nejmenší barvy pro vrchol u (snaží se vrchol obarvit nějakou již použitou barvou, pokud jí není obarvený žádný ze sousedních vrcholů u) obarvý „úsporně“ vrcholy grafu. Testy algoritmů ukázaly, že z uvedených heuristických algoritmů v této práci, se vždy nejvíce přiblížil chromatickému číslu vybraného grafu.
25
Obrázek 12. Vrcholově barvený graf.
3.6.
Barvení pomocí nezávislých množin
Zde si rozebereme další heuristický algoritmus pro vrcholové barvení. Víme, že množina vrcholů, které mohou být obarveny stejnou barvou tvoří nezávislou množinu vrcholů. 2.13. V algoritmu budeme používat heuristiku pro hledání maximální nezávislé množiny.3 3.6.1.
Popis algoritmu, část I.
Heuristický algoritmus pro nalezení maximální nezávislé množiny. Víme, že můžeme sestavit „velkou“ nezávislou množinu vrcholů z vrcholů, které mají málo sousedů.[3] Přidáním vrcholu do nezávislé podmnožiny vrcholů zajistíme, že zde nemohou být jeho sousedé. V každé iteraci tedy bereme vrchol s nejmenším počtem sousedů (zároveň i všechny vrcholy se kterými je spojen hranou). 3
Hledání maximální nezávislé množiny v grafu je NP-uplný problém.
26
Následuje postup pro hledání maximální nezávislé množiny vrcholů. Maximální nezávislou množinu si označíme N = {}. Podgraf G′ grafu G bude obsahovat vrcholy, které můžeme do množiny N přidat. V cyklu provedeme: 1. Nalezneme u ∈ G′ s nejmenším počtem sousedních vrcholů. (Pro více takových vrcholů vybereme náhodný) 2. Provedeme N ∪ {u} 3. Označíme si množinu K = {u a všechny jeho sousední vrcholy} 4. Odstraníme z G′ vrcholy z K. 5. Pokračujeme v cyklu dokud G′ není prázdný. 3.6.2.
Popis algoritmu, část II.
Na začátku barvení nastavíme první užitou barvu color = 0. Dále budeme pracovat s podgrafem G′ grafu G, v tomto momentě shodným s G. V cyklu provedeme: 1. Najdeme v G′ maximání nezávislou množinu vrcholů viz. 3.6.1. 2. Provedeme col(v) = color, pro všechny nalezené vrcholy maximální nezávislé množiny, odstraníme je z G′ . 3. Pokračujeme v cyklu krokem 1. dokud pro V ∈ G′ platí V ̸= ∅. Při každé iteraci zvyšujeme počet užitých barev color = color + 1
27
3.6.3.
Pseudokód
Algorithm 3.5. Barvení pomocí nezávislých množin 1: procedure independentSetColoring(graph) 2: color = 0 3: G′ = copyof (graph) 4: while V ∈ G′ (V, E) ̸= ∅ do 5: L ← f indM axIndependentSet(G′ ) 6: for all v ∈ L do 7: col(v) = color 8: removeV ertexF romGraph(v, G′ ) 9: end for 10: color = color + 1 11: end while 12: end procedure
3.6.4.
Shrnutí
Z výše popsaného víme, že nezávislé množiny jsou skupiny nesousedních vrcholů (netvoří v grafu hranu). Opět dostáváme vrcholové obarvení grafu podle definice v předchozí kapitole 3.4. Hledáním maximálních nezávislých množin povede rozvěž na řešení vrcholové obarvení grafu s možností užití menšího počtu barev.
28
3.7.
Barvení slepováním vrcholů
Poslední heurictický algoritmus provádí „slepování“ vrcholů, které nejsou sousední. Slepením můžeme chápat například uložení vrcholů do seznamu. 3.7.1.
Popis algoritmu
Na začátku algoritmu vytvoříme úplný graf G podle definice 2.12.: • Začneme spojováním libovolných dvou nesousedních vrcholů u a v v grafu G. • Tyto vrcholy slepíme dohromady, budou tvořit jeden uzel uv. • Uzel uv spojíme hranami se všemi sousedy vrcholů u a v. Vybrané vrcholy budou z grafu odstraněny. Slepujeme tak dlouho, dokud je možné spojovat nějaké dvojice vrcholů. Pro výsledný úplný graf obarvýme každý vrchol jinou barvou. Poté vrcholy rozbalíme do původního grafu. 3.7.2.
Pseudokód
Algorithm 3.6. Barvení slepováním vrcholů 1: procedure glueVertexColoring(graph) 2: G′ ← copyof (graph) 3: while canGlueSomeV ertices(G′ ) do 4: {u, v} ← selectSomeV ertices(G′ ) ▷ u, v nesousední vrcholy 5: d = glueV ertices(u, v) ▷ spojí vrcholy u, v 6: addT oGraph(d, G′ ) ▷ vloží d do hran namísto u, v 7: removeF romGraph({u, v}, G′ ) ▷ odebere vrcholy u, v z grafu 8: end while 9: return G′ ▷ úplný graf 10: end procedure
29
1: procedure colorGlueVertices(G′ ) 2: vybereme množinu vrcholů V z G′ 3: color = 0 ▷ aktuální index použité barvy 4: for all v ∈ V do 5: col(v) = color ▷ obarvíme všechny vrchol obsažené ve v 6: color = color + 1 7: end for 8: return splitT oOriginalGraph(G′ ) ▷ původní již obarvený graf 9: end procedure
3.7.3.
Shrnutí
Výběrem vrcholů jak je popsán v části 1. splňujeme definici na vrcholové obarvení grafu z kapitoly 3.4. Počet barev, kterým bude možné graf obarvit je jasně určen výběrem slepovaných vrcholů. Výběr je náhodný, pro stejný graf G budeme při opakovaném užití algoritmu dostávat různé vysledky. Obrázek níže popisuje průběh výpočtu algoritmu.
Obrázek 13. Barvení slepováním vrcholů, postup.
30
3.8.
Exaktní barvení
V poslední části sekce algoritmů si posíšeme exaktní (přesné) vrcholové barvení grafu. Nejlepší řešení vrcholového barvení grafu bude nalezeno vyzkoušením všech možností obarvení vrcholů grafu. 3.8.1.
Popis algoritmu
Činnost algoritmu můžeme rozdělit do tří částí (pracujeme se souvislým grafem G(V, E)):
I. Vygenerujeme si množinu všech možných skupinek vrcholů. Budeme tedy vytvářet n-tice, kde součet jejich prvků bude roveni n (n představuje velikost množiny vrcholů V ∈ G(V, E)). N-tice tedy budou složené s čísel 1 − |V |. (Variace s opakováním délky 1 − |V | o součtu prvků rovno |V |) II. Vygenerujeme si množinu vrcholů. Vytváříme variace bez opakování z vrcholů v ∈ V dle definice 2.19. III. Hledáme vrcholové obarvení grafu G s nejmenším počtem použitých barev c. Počáteční nejlepší řešení Solbest na počátku algoritmu představuje řešení s množství použitých barev c = |V |. Pro nalezení vrcholového obarvení grafu G s nějnižším počtem barev můžeme postupovat následovně: 1. V cyklu pro každou n-tici (představující rozdělení vrcholů do množin) z I. kroku a pro každou množinu vrcholů z II. kroku. 2. Zjistíme jestli se jedná o vrcholové barvení grafu G. 3. Pokud se jedná o vrcholové barvení, porovnáme jej s doposud nejlepším nalezeným řešením Solbest . 4. Pokud současné řešení Sol dokáže obarvit graf G menším počtem barev než Solbest , potom Solbest = Sol. 3.8.2.
Pseudokód
31
Algorithm 3.7. Exaktní vrcholové bavení grafu 1: procedure doExactColoring(graph) 2: tupleList ← generateT uples() ▷ množina n-tic, rozdělení do skupin 3: verticeListSet ← generateV erticeLists() ▷ množina seznamů vrcholů 4: minColorCount ← getV erticeCount() 5: Solbest ← ∅ 6: for all tuple ∈ tupleList do 7: for all verticeList ∈ verticeListSet do 8: if isIndependentSet(verticeList, tuple) then 9: nowColors ← getColorsCount(verticeList, tuple) 10: if nowColors < minColorCount then 11: Solbest ← solution(verticeList, tuple) 12: minColorCount ← nowColors 13: end if 14: end if 15: end for 16: end for 17: return Solbest 18: end procedure
Přístup užitý pro generování, t ∈ {1, . . . , |V |} 1: procedure generateTuples(size, resultList) 2: if size = getV erticeCount() then 3: return resultList 4: else 5: validT uples ← f ilterBigger(size) ▷ odebere čísla {t|t + size > |V |} 6: moreT uples ← ∅ 7: for all tuple ∈ validT uples do 8: newList ← copyOf (resultList) 9: moreT uples ∪ generateT uples(size + tuple, newList) 10: end for 11: return moreT uples 12: end if 13: end procedure=0
32
3.8.3.
Shrnutí
Na začátku si vygenerovali množinu n-tic tupleList, které budou reprezentovat libovolné uspořádání vrcholů v ∈ V do množin. 4 Součet prvků každé n-tice je roven počtu vrcholů, tedy |V |. Složitost tohoto výpočtu je O(2n−1 ), kde n = |V |. Množinu verticeListSet tvoří variace bez opakování z vrcholů v ∈ V . Ze n! vzorce (n−k)! , po úpravě dostáváme složitost O(n!).5 Pro každou z těchto variací ∪ jsme rozdělovali do podmnožin vrcholů V1 , V2 . . . Vn tak, že ni=1 Vi = V . Pro každou takto rozdělenou množinu vrcholů z verticeListSet jsme ověřili, že každá z podmnožin vrcholů V1 , V2 . . . Vn je nezávislá podle definice 2.13. Každou z podmnožin V1 , V2 . . . Vn jsme obarvili jednou barvou a hledali jsme tu nejmenší možnou.6 Hledání tohoto řešení má složitost O(n!×2n−1 ). Výsledkem je číslo χ, chromatické číslo grafu G podle definice 2.15. Z praktických důvodů jsou tupleList a verticeListSet v aplikaci reprezentovány jako seznamy čísel, ve kterých se jednotlivé n-tice (nebo seznamy vrcholů) rozlišují podle indexů.
4
Sjednocením těchto množin dostáváme původní množinu vrcholů V . Víme, že n = k, kde k představuje délku variace bez opakování (vždy pracujeme se všemi vrcholy grafu). 6 Obarvením je zde myšlen počet podmnožin V1 , V2 . . . Vn . 5
33
4.
Uživatelská příručka Následující část shrnuje použití aplikace přiložené k této práci.
4.1.
Spuštění
Aplikace je k dispozici ve spustitelném balíku JAR ve kterém jsou přiloženy i potřebné knihovny. Spuštění aplikace provedeme příkazem: java -jar graphAlgorithms.jar Pro přidělení větší paměťového prostoru, pro potřeby exaktního barvení můžeme rozšířit příkazem: java -Xmx2048M -jar graphAlgorithms.jar V tomto případě přepínač -Xmx2048M dovolí aplikaci využít prostor nejvýše 2048MB.
4.2.
Okno Aplikace
Po spuštení souboru se mám zobrazí hlavní okno aplikace. Podstatnou část okna vyplňuje komponenta pro vykreslení grafu. Nad ní se nachází menu umožňující přechod do editoru, otevření souboru grafu a dodatečné informace k ovládání . Vpravo se nachází ovládací panel, kterým uživatel kontroluje vybranou demonstraci grafového algoritmu. 4.2.1.
Komponenta grafu
Zobrazuje graf vytvořený ze třídy mxGraph z knihovny JgraphT. Stará se o změny během během demonstrace vybraného algoritmu. 4.2.2.
Menu Soubor
Obsahuje základní ovládací prvky pro načtení grafu ve formátu XML a ukončení aplikace. 4.2.3.
Menu Úpravy
Položka „upravit graf“ spustí v editoru aktuálně otevřený graf v hlavním okně aplikace. Položka „oteřít editor“ spustí okno editoru nezávisle na tom, jestli máme otevřený soubor grafu.
34
Obrázek 14. Okno aplikace, výpočet dokončen. 4.2.4.
Menu Nápověda
Poskytuje informace k zakladnímu ovládání této aplikace, včetně klávesových zkratek. 4.2.5.
Ovládací panel demonstrace
Obsahuje ovládací a informační prvky pro demonstaci grafových algoritmů v této aplikaci. 4.2.6.
Možnosti sekce Zobrazit
V ovládacím panelu aplikace můžeme pomocí komponent JRadioButton volit obsah, který se nám zobrazí v komponentě grafu.Volba Demonstrace předá komponentě graf, na kterém probíhá demonstrace vybraného algoritmu. Volba Původní graf předá komponentě graf ve stavu v jakém byl před spuštěním demonstrace. 4.2.7.
Sekce Algoritmus
V této části si volíme algoritmus, jehož demonstraci spustíme. Po přepnutí se nám v dolní části aplikace zobrazí stručný popis algoritmu. Pří výběru Dijskrova algoritmu volíme ještě dodatečtě startovní vrchol, odkud budeme hledat nejkratší cesty.
35
4.2.8.
Ovládací tlačítka
Tlačítko Start spustí demonstraci vybraného algoritmu. Tlačítko Stop pozastaví (v nejužšímožný okamžik) průběh algoritmu. Tlačítko Pokračovat naváže na následující krok algoritmu před jeho pozastavením. Tlačítko Ukončit Zastaví výpočet a demonstraci algoritmu. 4.2.9.
Zpoždění
Komponenta třídy JSlider, umožňuje změnit rychlost průběhu animace. 4.2.10.
Postup
Zobrazuje komentáře k auktuálnímu stavu průběhu algoritmu. V případě vrcholového bravení grafu je možné po kliknutí na barvu otevřít dialog pro změnu barvy vrcholu.
4.3.
Okno Editor
Při spuštění editoru se nám zobrazí okno s ovladácími prvky pro manipulaci s grafem. Hlavní část okna vyplňujě komponenta grafu (mxGraphComponent). Třídy udalostí v balíku editor ve spolupráci s komponentou grafu umožňují pohodlnou tvorbu a úpravy grafu ve vizuální podobě. Spodní část tvoři ovládací a informační panel.
Obrázek 15. Okno editoru, úprava grafu.
36
4.3.1.
Menu Soubor
Obsahuje základní ovládací prvky načtení, uložení grafu, vytvoření nového grafu. Grafy se ukládají ve formátu XML, které zajišťuje třída mxXmlUtils z knihovny JgraphT a ukončení aplikace. 4.3.2.
Menu Úpravy
Volba Přidávání vrcholů přepne editor do režimu, ve kterém je možné do okna editoru (komponenty grafu) vkládat vrcholy. Volba Přidávání hran přepne editor do řežimu, ve kterém se po kliknutí na dva vrcholy grafu vytvoří hrana (pokud již neexistuje). Informace o tvorbě hrany se objevuji ve spodní části editoru. Volba Zrušit výběr vrcholu zruší vybraný vrchol v režimu přidávání hran. Volba Vytvořit náhodný graf vygeneruje graf na základě vybraných parametrů. 4.3.3.
Ovládací panel editoru
Tlačítko Přidat vrchol přepne editor do režimu přídávání vrcholů, stejně jako volba v menu Úpravy. Aktuální režim editoru zvýrazní tlačítko modře. Tlačítko Přidat hranu přepne editor do režimu přidávání hran. Tlačítko Pozicování přepne editor do režimu, ve kterém je možné pohybovat s vrcholy grafu (případně celým grafem pomocí výběru všech vrcholů zkratkou Ctrl+A). V tomto režimu je možné ohodnocovat hrany po kliknutí myší na hranu a stisknutím klávesy ENTER. Tlačítko Ohodnocování hran umožňuje rychlejší ohodnocení hran grafu - pouhým kliknutím na hranu. Potvrdit úpravy předá upravený graf hlavnímu oknu aplikace. Po tomto kroku je možné spustit demonstaci (v případě validního grafu). Zahodit změny zavře editor grafů, žádné provedené změny nebudou uloženy. 4.3.4.
Informační panel editoru
Ve spodní části editoru se nám zobrazují informace o aktuální grafu. V pravé části počet vrcholů, počet hran. V levé části se nám budou zobrazovat informace při tvorbě hran. 4.3.5.
Dialog Náhodný graf
Vygeneruje náhodný graf o počtu vrcholů v uzavřeném intervalu 1 − 75. Můžeme si zvolit hranově ohodnocený graf nebo graf bez ohodnocení pro potřeby algoritmů pro vrcholové barvení.
37
4.4.
Prográmatorská část
Nyní si představíme řešení přiložené aplikace. Začtene s jazykem, vývojovým prostředím a skončíme detaily použitých tříd. 4.4.1.
Tvorba aplikace
Pro napsání aplikace byl použit jakyk Java, verze 7. Uživatelské prostředí aplikace je vytvořeno pomocí knihovny Java Swing, vybrané části knihovnou JgraphT. Vývoj aplikace probíhal na operačním systému Windows 7 a Linux (distribuce Fedora) ve vyvojovém prostředí Eclipse (Kepler, Luna). 4.4.2.
Třídy
Hlavní třídou aplikace je třída Application, která užívá všechny třídy a poskytuje ovládací prvky uživatelského rozhraní. Uživatelské rozhraní je realizováno pomocí knihovny Swing. Z této knihovny byla použita třída GroupLayout pro uspořádání jednotlivých komponent uživatelského prostření do okna aplikace. Aplikace pro realizaci výpočtu algoritmů využívá třídy z balíku algorithms. Jednotlivé výpočty poté probíhají v samostatném vlákně GraphWorkThread dědící z třídy SwingWorker7 . Další třídou pro práci s vlákny, kterou jsem využil je RecursiveAction, která je určená pro výpočet rekurzivních algoritmů ve více vláknech. Třídu používám ke generování variací bez opakování v kapitole 3.8. V balíku editor jsou třídy pro grafickou manipulaci s grafem, umožňující vytvořit, editovat ohodnotit a uložit graf ve formátu XML. Aplikace využívá pro ukládání, vizuální reprezentaci grafu a jeho součástí některých tříd z knihovny JGraphT. Application Kombinuje dohramody všechny třídy, dává uživateli pomocí grafického rozhraní kontrolu na probíhajícím výpočtem. Algorithm Obsahuje jména a popisy užitých algoritmů. CellManager vytváří indexy pro objekty grafu z knihovny JGraphT, které využívá aplikace. GUIManager usnadňuje práci s uživatelským rozhraním mezi třídami. VisualGraph rozšiřuje třídu mxGraph z knihovny JgraphT o nové metody. FileUtils rozšiřuje třídu z knihovny JgraphT, zajištuje ukládání a načtení souboru grafu ve formátu XML. PlainEdge třída obsahující základní informace o hraně grafu. PlainVertex třída obsahující základní informace o vrcholu grafu. 7
Třída která provádí náročný výpočet na pozadí aplikace s uživatelským rozhraním.
38
PlainGraph třída tvořící graf ze tříd PlainVertex a PlainEdge. SimpleColorChooser třída poskytující uživatelské rozhraní pro změnu barvy vrcholu grafu třídy mxGraph z knihovny JGraphT. MatrixViewer třída pro zobrazení dat z Floyd-Warshallova algoritmu. Editor třída kompletující uživatelské rozhraní pro práci z vizuální podobou grafu. EditorCellValueDialog rozhraní pro změnu hodnoty hrany grafu. EditorKeyBoardManager třída pro zpracování událostí z klávesnice. EditorMouseAction třída pro zpracování událostí z myši. EditorRandomGraphDialog generátor náhodných grafů. DijskraAlgorithm Třída pro výpočet Dijskrova algoritmu. ExactColoring Třída řešící problém barvení grafu hrubou silou. FloydWarshall Třída vykonavající výpočet Floyd–Warshallova algoritmu. KruskalAlgorithm Třída vykonavající výpočet Kruskalova algoritmu. NeighbourColoring Třída řešící problém barvení grafu pomocí informace o aktuálním obarvení sousedních vrcholů daného vrcholu. GlueColoring Třída řešící problém barvení grafu pomocí slepování vrcholů. IndependentSetColoring Třída řešící problém barvení grafu hledáním maximálních nezávislých množin.
39
Závěr Cílém bakalářské práce bylo vytvořit aplikaci demonstrující grafové algoritmy: úlohy nalezení nejkratší cesty, hledání minimální kostry grafu a úlohy barvení grafu. Zárověň měla aplikace obsahovat i editor grafů pro splnění těchto úloh. Přiložená aplikace tyto požadavky splňuje. Při vytváření této aplikace jsem využíval knihovny JGraphT. Někdy jsem narazil na překážky (např. způsob jakým knihovna indexuje části grafu), ale podařilo se mi je vyřešit. Získal jsem zkušenosti s používáním externí knihovny. Do budoucna plánuji aplikaci rozšířit o nové funkce a více algoritmů.
40
Reference [1] Bělohlávek, Radim; Vychodil Vilém. Diskrétní matematika pro informatiky II Elektronická publikace, 2006. [2] Even, Shimon; Even Guy. Graph Algorithms, 2nd Edition. Cambridge University Press, 2012. 189s. ISBN 978-0-521-51718-8. [3] Večerka, Arnošt. Grafy a grafové algoritmy Elektronická publikace, 2007. [4] Osička, Petr. Algoritmická matematika 3 Elektronická publikace, 2014. [5] Sedgewick, Robert. Algorithms in C: Part 5, graph algorithms. AddisonWesley, 2001. ISBN: 0201361183. [6] Wikipedia Edsger W. Dijkstra Elektronická encyklopedie
41
A.
Obsah přiloženého CD
bin/ Obsahuje kompletní aplikaci ve formátu JAR s přibalenou knihovnou pro spuštění přímo z CD. doc/ Dokumentace práce ve formátu PDF, zdrojový text dokumentace ve formátu TEX, vložené obrázky. src/ Kompletní zdrojové texty programu se všemi potřebnými (převzatými) zdrojovými texty, knihovnami. readme.txt Instrukce pro instalaci a spuštění programu včetně požadavků pro jeho provoz. data/ Ukázková a testovací data použitá v práci a pro potřeby obhajoby práce.
42
