BAKALÁŘSKÁ PRÁCE. Jakub Kratochvíl. Kreslení grafů

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Jakub Kratochvíl Kreslení grafů Katedra Aplikované Matematiky Vedoucí práce: RNDr. Martin Pergel Studijní program: Informatika, programování

2008

2

Děkuji svoji rodině, že mě podporovala ve studiu. Děkuji také svému vedoucímu Martinu Perglovi za podněty při vypracování práce.

Prohlašuji, že jsem svou bakalářskou práci napsal samostatně a výhradně s použitím citovaných pramenů. Souhlasím se zapůjčováním práce a jejím zveřejňováním. v Praze dne

Jakub Kratochvíl

Obsah 1 Teoretický úvod

6

1.1

Úvod do kreslení grafů . . . . . . . . . . . . . . . . . . . . .

6

1.2

Teorie grafů . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.3

Lineární algebra . . . . . . . . . . . . . . . . . . . . . . . . .

10

2 Ortogonální kreslení ve 3D

12

2.1

Definice problému . . . . . . . . . . . . . . . . . . . . . . . .

12

2.2

Kompaktní algoritmus . . . . . . . . . . . . . . . . . . . . .

14

2.3

Kubický algoritmus . . . . . . . . . . . . . . . . . . . . . . .

20

2.4

Přehled dalších výsledků . . . . . . . . . . . . . . . . . . . .

23

2.5

Implementace . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3 Fyzikální metody

27

3.1

Základní algoritmus . . . . . . . . . . . . . . . . . . . . . . .

27

3.2

Barycentrová metoda . . . . . . . . . . . . . . . . . . . . . .

29

3.3

Algoritmus Kamada-Kawai . . . . . . . . . . . . . . . . . . .

31

3.4

Zhodnocení . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3

4

OBSAH 4 Algebraické metody

35

4.1

Problém k-center . . . . . . . . . . . . . . . . . . . . . . . .

35

4.2

PCA (Principal Component Analysis) . . . . . . . . . . . . .

38

4.3

Laplacian Preserving Projection - LPP . . . . . . . . . . . .

41

5 Uživatelská dokumentace

57

5.1

Menu - File . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

5.2

Generování grafů . . . . . . . . . . . . . . . . . . . . . . . .

60

5.3

Draw2D – Kreslení grafů ve 2D . . . . . . . . . . . . . . . .

62

5.4

Draw3D – Kreslení grafů ve 3D . . . . . . . . . . . . . . . .

67

5.5

Ovládání kamery a volba vykreslovacího režimu . . . . . . .

73

5.6

Editace grafu . . . . . . . . . . . . . . . . . . . . . . . . . .

73

5.7

Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

6 Programová dokumentace

77

6.1

Základní popis programu . . . . . . . . . . . . . . . . . . . .

77

6.2

Dokumentace API . . . . . . . . . . . . . . . . . . . . . . .

81

6.3

Formát grafových a konfiguračních souborů . . . . . . . . . .

81

6.4

Použité knihovny . . . . . . . . . . . . . . . . . . . . . . . .

88

6.5

Kompilace pod MS Visual Studio . . . . . . . . . . . . . . .

89

6.6

Kompilace pod Dev-Cpp . . . . . . . . . . . . . . . . . . . .

90

7 Závěr

92

OBSAH

5

Název práce: Vizualizace grafů Autor: Jakub Kratochvíl Katedra (ústav) : Katedra Aplikované Matematiky Vedoucí bakalářské práce: RNDr. Martin Pergel e-mail vedoucího: [email protected] Abstrakt: V předložené práci studujeme metody pro kreslení grafů ve 3D. V první části shrneme výsledky o ortogonálních nakresleních grafů s maximálním stupněm nižším než 6. Rozebereme použití fyzikálních principů pro kreslení ve 3D. V závěrečné části ukážeme, jak kreslit grafy za použití high dimensional embedding (HDE), a předložíme nový algoritmus založený na vzorkování HDE. Vytvořili jsme aplikaci pro Win32, která umožňuje využít výhody třídimenzionálního nakreslení grafu. Klíčová slova: Kreslení grafů ve 3D, high dimensional embedding, vlastní čísla Title: Graph visualisation Author: Jakub Kratochvíl Department: Department of Applied Mathematics Supervisor: RNDr. Martin Pergel Supervisor’s e-mail address: [email protected] Abstract: This thesis concentrates on drawing graphs in 3D. In the first part of the text, we concentrate on orthogonal layouts of graphs with maximum degree 6. We show how to draw graphs using high dimensional embedding (HDE) and propose a new fast algorithm based upon sampling of the HDE. Further, we developed an application for Win32 that allows the user to translate, zoom and rotate the graph drawing, thus taking full advantage of the 3D layout. Keywords: graph drawing, high dimensional embedding, eigenvalues

Kapitola 1 Teoretický úvod 1.1

Úvod do kreslení grafů

Kreslení grafů je prostředkem pro vizualizaci komplexních struktur a jejich následnou prezentaci uživateli. První metody kreslení grafů vycházely z fyzikálních metod viz např. [24]. Centrem zájmu dlouhou dobu bylo zejména kreslení rovinných grafů a stromů. V 80. letech se objevily první algoritmy založené na hledání vlastních čísel spektra grafu. Fyzikální metody však postačovaly pro většinu aplikací, dokud se neobjevila potřeba kreslit rozsáhlé grafy s mnoha tisíci vrcholy. Prvním krokem, který umožnil kreslení takto velkých grafů, byla implementace shlukování do fyzikálních algoritmů, která značně redukovala jejich asymptotickou složitost viz [28]. Zhruba ve stejné době se do středu zájmu dostaly metody založené na výpočtu vlastních čísel, které využívají shlukování. Ukazálo se totiž, že vlastní čísla grafu lze aproximovat pomocí vhodně zvoleného malého grafu s konstantní velikostí. Stranou zájmu dlouhou dobu zůstavalo kreslení grafů ve 3D, přestože nabízí řadu výhod z uživatelského pohledu – jako zásadní se jeví možnost libovolně 6

KAPITOLA 1. TEORETICKÝ ÚVOD

7

rotovat a přibližovat kameru. Takto lze získat mnohem detailnější přehled o výsledném nakreslení, a navíc odpadá potřeba minimalizovat počet křížení hran, jak bude ukázáno ve druhé kapitole. Dodejme, že minimalizace křížení ve 2D je N P-úplná úloha. V první části práce shrneme výsledky o ortogonálních nakresleních grafů s maximálním stupněm nižším než 6. Ukážeme, jak nalézt takové nakreslení s nejvýše 8 segmenty pomocí kompaktního algoritmu a demonstrujeme, jak nalézt nakreslení s nejvýše 4 segmenty kubickým algoritmem. V druhé části rozebereme použití fyzikálních principů pro kreslení v 2D a 3D. Ve třetí části ukážeme, jak kreslit grafy za použití high dimensional embedding (HDE), a předložíme nový algoritmus založený na vzorkování HDE s lineární složitostí. Podrobně bude dokázána složitost našeho algoritmu a výsledky budou porovnány s algoritmem založeným na PCA-projekci [12]. Dále jsme vytvořili aplikaci pro Windows, která umožňuje využít výhody třídimenzionálního nakreslení grafu.

1.2

Teorie grafů

Definice 1.1 Graf G je uspořádaná dvojice (V, E), kde V je neprázdná množina a E množina dvojic prvků V . Je-li E množina uspořádaných dvojic, pak hovoříme o orientovaném grafu. Je-li E množina neuspořádaných dvojic, pak výsledný graf nazýváme neorientovaný. Pokud budeme v dalším textu hovořit o grafu, budeme tím rozumět graf neorientovaný, pokud nebude blíže specifikováno. Definice 1.2 Množinu V označujeme jako množinu vrcholů, její prvky vrcholy. Definice 1.3 Množinu E nazveme množinou hran, její prvky hrany.


8

Definice 1.4 Buď H = (V, E), pak G = (VG , EG ) nazýváme podgrafem H, pokud VG ⊆ V, a zároveň EG ⊆ E. Definice 1.5 G = (VG , EG ) nazýváme indukovaným podgrafem H = (V, E), pokud VG = V, a zároveň EG ⊆ E. Definice 1.6 Hrana e = {v, w} je incidentní s vrcholem u, pokud u = v

nebo u = w.

Definice 1.7 Buď G = (V, E). Vrcholy v, w nazýváme sousedy, pokud ∃e = {v, w} ∈ E.

Definice 1.8 Stupeň vrcholu v je počet sousedů vrcholu v. Značíme ho deg(v). Definice 1.9 Buď G orientovaný graf a v jeho vrchol. Pak výstupní stupeň vrcholu v definujeme následovně degout (v) = |{w|{v, w} ∈ E}| . Vstupní

stupeň vrcholu v definujeme obdobně tedy jako degin (v) = |{u|{u, v} ∈ E}| .

Definice 1.10 Neorientovaný graf G na n vrcholech nazveme úplným grafem, platí-li |E| =

|V | 2

Takový graf značíme Kn .

Definice 1.11 Graf G nazveme bipartitní, pokud existuje rozklad množiny vrcholů V = X ∪ Y , a navíc |{u, v} ∩ X| = |{u, v} ∩ Y | = 1. Je-li navíc

|E| = |X|×|Y |, nazýváme takový graf úplný bipartitní. Takový graf značíme

Kn,m , kde m = |X| a n = |Y |.

Definice 1.12 Buď G graf, v1 a vn jeho vrcholy. Cestou mezi vrcholy v1 a vn rozumíme posloupnost vrcholů p = v1 . . . vn , kde ∀i{vi , vi+1 } ∈ E. Na p se nesmí opakovat ani vrcholy ani hrany.


9

Definice 1.13 Buď G graf. Pak G je souvislý, pokud pro každé dva vrcholy u, v existuje cesta mezi vrcholy u, v. Definice 1.14 Graf G nazýváme kružnicí, pokud je souvislý a všechny jeho vrcholy mají stupeň 2. Kružnici na n vrcholech značíme Cn . Definice 1.15 Graf G označujeme jako strom, pokud je souvislý a |E| = |V | − 1.

Definice 1.16 Posloupnost hran nazýváme tah, pokud se na ní neopakují hrany. Definice 1.17 Eulerovský tah je tah, který prochází všechny hrany grafu. Definice 1.18 Eulerovská kružnice je eulerovský tah, který začíná a končí ve stejném vrcholu. Věta 1.1 (O existenci eulerovské kružnice) Graf má eulerovskou kružnici tehdy a jen tehdy, když všechny jeho vrcholy mají sudý stupeň. Důkaz: viz [1] Definice 1.19 Nakreslením grafu G = (V, E) na plochu S rovnými čarami rozumíme zobrazení φ : v → S, kde hrany kreslíme úsečkami mezi jednotlivými vrcholy.

10


1.3

Lineární algebra

Definice 1.20 Buď m, n ∈ N . Maticí A tvaru m × n nazveme funkci A :

{1 . . . m} × {1 . . . n} → S , kde S je libovolná množina. M zde označuje

počet řádků matice A, n počet sloupců matice A.

Definice 1.21 Buď A matice tvaru m × n. A nazýváme čtvercovou, pokud

m = n.

Definice 1.22 Buď A matice tvaru m × n , zápisem ai,j rozumíme prvek v i-tém řádku a j-tém sloupci.

Definice 1.23 Transpozicí matice A tvaru m×n rozumíme matici AT tvaru n × m, kde aTi,j = aj,i . Definice 1.24 Matice A je symetrická, pokud A = AT . Definice 1.25 Buď A tvaru m × n a B matice tvaru n × r, pak součinem matic A a B rozumíme matici C = AB tvaru m × r , kde ci,j =

Pn

q=0

ai,q bq,j .

Definice 1.26 Matici tvaru m × 1 nazýváme sloupcový vektor. Definice 1.27 Matici tvaru 1 × n nazýváme řádkový vektor. Definice 1.28 Lineární kombinací vektorů x1 . . . xn rozumíme vektor y takový, že ∃w1 . . . wn ∈ < a y =

Pn

i=1

wi ∗ xi , přičemž ∃i : wi 6= 0

Definice 1.29 Buď A čtvercová matice nad reálnými popř. komplexními čísly. Pak λ je její vlastní číslo, pokud existuje nenulový vektor x takový, že Ax = λx. Vektor x pak nazýváme vlastním vektorem matice A příslušným λ.


11

Definice 1.30 Symetrická čtvercová matice je pozitivně definitní, pokud ∀x 6= ~0 : xAxT > 0. Definice 1.31 Symetrická čtvercová matice je pozitivně semidefinitní, pokud ∀x 6= ~0 : xAxT ≥ 0. Věta 1.2 Matice je pozitivně definitní tehdy a jen tehdy, když má všechna vlastní čísla kladná. Důkaz: viz [2]. Věta 1.3 Reálná symetrická matice má všechna vlastní čísla reálná. Důkaz: viz [2].

Kapitola 2 Ortogonální kreslení ve 3D Kapitola je zpracována na základě [3], metodu zde pouze implementujeme, nejedná se o vlastní výsledky autora.

2.1

Definice problému

Definice 2.1 Graf G = (V, E) nazveme k-regulárním, pokud mají všechny jeho vrcholy stupeň rovný k. Definice 2.2 Buď G graf, pak F je k-faktorem G, pokud F je k-regulární indukovaný podgraf grafu G. 1-faktor nazýváme perfektní párování. Definice 2.3 Graf G=(V,E) je k-faktorizovatelný, pokud existují hranově disjunktní k-faktory F1 . . . Fn , G takové, že G = F1 ∪ . . . ∪ Fn . Věta 2.1 Buď G = (V, E) graf s maximálním stupněm nejvýše 6. Pak lze G přidáváním hran a smyček rozšířit na 6-regulární graf.

12

KAPITOLA 2. ORTOGONÁLNÍ KRESLENÍ VE 3D

13

Důkaz: Z principu sudosti dostáváme, že počet vrcholů s lichým stupněm je vždy sudý. Spojíme tedy vždy libovolné dva vrcholy s lichým stupněm hranou. Vrcholy sudého stupně nižšího než 6 doplníme na požadovaný stupeň přidáním smyček. Věta 2.2 Každý souvislý 6-regulární graf je 2-faktorizovatelný. Důkaz: Viz [3]. Buď G = (V, E) 6-regulární graf. G má všechny stupně sudé, a tedy existuje eulerovská kružnice v grafu G. Orientací hran v G podle této kružnice dostáváme orientovaný graf H = (VH , EH ). Pro vrcholy H zjevně platí, že degout (v) = degin (v). Rozdělíme každý vrchol H na vin a vout . Do vrcholu vin budou směřovat hrany, které vstupují do v v H. Z vrcholu vout budou směřovat hrany, které opouští v v H. Z H nyní zkonstruujeme neorientovaný bipartitní graf I následujícím způsobem: I = (VI , EI ), kde VI = Vin ∪ Vout a EI = {{uin ∈ Vin , vout ∈ Vout }|{u, v} ∈ EH } Všechny vrcholy grafu I mají stupeň 3, a proto dle Hallovy věty [4] existuje v grafu I perfektní párování P1 . Hrany příslušné P1 obarvíme barvou 1. Odebráním P1 z I dostáváme dle Hallovy věty perfektní párování P2 a P3 . Hrany příslušné těmto párováním obarvíme barvou 2 respektive 3. Hranu {u, v} z EH obarvíme barvou příslušnou hraně {uin , vout } z I. Pro každý

vrchol tedy existuje právě jedna vstupní a právě jedna výstupní hrana každé

barvy incidentní s v. Dostáváme tedy rozklad grafu H = C1 ∪ C2 ∪ C3 . C1 ∪C2 ∪C3 jsou 2-regulární indukované podgrafy H generované jednotlivými

barvami. Tedy H i G jsou 2-faktorizovatelné. K nalezení párování v grafu H je v naší implementaci použito Edmondsova algoritmu [6], jehož složitost je O(6 ∗ n2 ∗ Acker−1 (n, 6n)), kde Acker−1 je inverzní Ackermannova funkce.


14

Existují i algoritmy schopné nalézt perfektní párování v bipartitním grafu rychleji viz například [7]. Definice 2.4 Buď (x, y, z) bod na celočíselné mřížce. Pak úsečku mezi (x + 1, y, z) a (x, y, z) nazveme portem +Xbodu (x, y, z). Analogicky definujeme porty −X, +Y, −Y, +Za −Z. Definice 2.5 Třídimenzionální ortogonální nakreslení na celočíselnou mřížku (3DMNO) definujeme následovně: Vrcholy umístíme na 3-dimenzionální celočíselnou mřížku. Hrany nakreslíme kolmými lomenými čarami spojujícími jednotlivé mřížkové body. Žádné dvě hrany se přitom nesmí protínat nebo překrývat. Hrany opouští vrcholy pouze ve směru výše definovaných portů. Všechny algoritmy pro nalezení 3DMNO vychází ze základního algoritmu pro nalezení 3DMNO.

Základní algoritmus pro nalezení 3DMNO Vstup: Graf G – maximální stupeň G nejvýše 6 1. Najdi 2-faktorizaci G = C1 ∪ C2 ∪ C3 viz věta 2.2 2. Umísti vrcholy G na mřížku 3. Umísti hrany

2.2

Kompaktní algoritmus

Nejprve uvedeme algoritmus pro nalezení 3DMNO, kde každá hrana je reprezentována lomenou čarou s nejvýše 8 segmenty.


15

1. Najdi 2-faktorizaci G = C1 ∪ C2 ∪ C3 viz věta 2.2 2. Umísti vrcholy G do roviny Z = 0 3. Umísti hrany faktoru C − 1 v rovině Z = 0 4. Umísti hrany faktoru C2 v poloprostoru Z >= 0 5. Umísti hrany faktoru C3 v poloprostoru Z <= 0

Umístění vrcholů Nechť G = C1 ∪ C2 ∪ C3 . Buď C1 = c1 . . . cn , kde c1 . . . cn jsou vrcholově dis-

junktní kružnice. Očíslujme nyní vrcholy G = (V, E) následovně: začneme

libovolným vrcholem c1 a zbylé vrcholy očíslujeme v pořadí, kterým procházíme kružnicí c1 . Obdobně očíslujeme i vrcholy dalších kružnic. Toto očíslování označíme ord . Platí, že v ∈ ci , w ∈ cj , i < j ⇒ ord(v) < ord(w). l q

m

Mřížka bude mít délku hrany 5 |V | . Vrcholy umístíme na mřížkové body

podle jejich pořadí. Vrcholy umísťujeme řetězovitě za sebou tak, jak je znázorněno na ilustraci 2.1. Každému vrcholu přísluší čtverec 5 × 5.

Vedení hran faktoru C1 Definice 2.6 Dopřednou hranou rozumíme hranu tvaru {vi , vi+1 }. Zpětnou

hranou hranu tvaru vj , vi , i < j.

Hrany faktoru jsou vedeny v rovině Z = 0 a využívají porty +X a −X.

Zajímavé jsou pouze zpětné hrany, které uzavírající cyklus – ostatní jsou vedeny triviálně. Ilustrace 2.1 znázorňuje, jak vést smyčky – viz v25 . Na příkladu hrany {v3 , v1 } je demonstrována trasa zpětné hrany, kde oba vrcholy mají shodnou souřadnici x. Hrana {v9 , v4 } ukazuje, jak vést zpětnou hranu,


16

Obrázek 2.1: Vedení hran ve faktoru C1 zdroj viz [3]. pokud se x-ové souřadnice obou vrcholů liší o 1. Konečně hrana {v21 , v10 } je

příkladem vedení zpětné hrany za předpokladu, že x-ové souřadnice konco-

vých vrcholů se liší o více než 1. Vidíme, že hrany faktoru nevyužívají porty +Y ani −Y žádného vrcholu. Věta 2.3 Žádné dvě hrany z C1 se neprotínají. Důkaz: Dopředné hrany se zjevně neprotínají. Žádná dopředná hrana neprotíná zpětnou hranu, neboť dopředné hrany nejsou v žádném ze čtverců vedeny pomocí bodů označených X v tabulce 2.2. Navíc nevyužívají bodů

KAPITOLA 2. ORTOGONÁLNÍ KRESLENÍ VE 3D X 1

1

1

2

17

X 2

2

v

2

2

2

X 1

1

1

X

Tabulka 2.1: Body mřížky, které nevyužívají dopředné hrany. označených 2 u vrcholů ležících při levém respektive pravém okraji mřížky a bodů označených 1 u vrcholů, které leží uvnitř mřížky. Naopak zpětné hrany jsou vedeny právě body mřížky označenými 1, 2, X kromě čtverců, které naleží koncovým vrcholů zpětných hran. B

B

B

B B

F

F

v

B

Tabulka 2.2: Body mřížky využité hranami C1 u vrcholu uprostřed mřížky příslušného zpětné hraně. V rámci koncového vrcholu využívá zpětná hrana jen body označené B a dopředná hrana jen body označené F a tedy žádná zpětná hrana neprotíná dopřednou viz 2.3 a 2.2. Hrany příslušné kružnici jsou vedeny pouze čtverci příslušnými vrcholům, a tak se ani žádné dvě zpětné hrany nemohou protínat.

Vedení hran faktoru C2 Tabulka 2.4 popisuje trasování hran faktoru C2 . Dodejme, že hrany faktoru C2 využívají porty +Y a +Z. Hrany faktoru C3 vedeme stejným způsobem,

KAPITOLA 2. ORTOGONÁLNÍ KRESLENÍ VE 3D B

B

B

18

B

B

B

B

F

B

F

B

F

V B

Tabulka 2.3: Body mřížky využité hranami C1 u vrcholu na okraji mřížky příslušného zpětné hraně. Segment

Začátek

Konec

1

(xi , yi , 0)

(xi , yi + 1, 0)

2

(xi , yi + 1, 0)

(xi , yi + 1, zi,j )

3

(xi , yi + 1, zi,j )

(xi , yi + 2, zi,j )

4

(xi , yi + 2, zi,j )

(xj + 1, yi + 2, zi,j )

5

(xj + 1, yi + 2, zi)

(xj + 1, yi + 2, zi,j + 1)

6

(xj + 1, yi + 2, zi,j + 1)

(xj + 1, yj , zi,j + 1)

7

(xj + 1, yj , zi,j + 1)

(xj , yj , zi,j + 1)

8

(xj , yj , zi,j + 1)

(xj , yj , 0)

Tabulka 2.4: Vedení hran faktoru C2 viz [3]. využíváme však porty −Y a −Z. Ilustrace 2.2 graficky znázorňuje vedení

hrany ve faktoru C2 .

Popíšeme nyní, jak získat zi,j . Sestrojíme graf Q, jehož vrcholy jsou hrany faktoru C2 . Hrany v grafu Q položíme mezi hranami C2 , pokud mají jejich počáteční vrcholy stejnou souřadnici x nebo jejich koncové vrcholy shodnou souřadnici y. lq

Graf Q má maximální stupeň 2( může křížit nejvýše s

lq

m

m

|V | − 1) - každá hrana faktoru C2 se

|V | − 1 hranami se shodnou x-ovou souřadnicí. Q lq

lze tedy obarvit hladovým algoritmem 2(

m

3

|V | ) − 1 barvami v čase O(n 2 ).


19

Obrázek 2.2: Vedení hran faktoru C2 viz [3]. Označíme toto obarvení Clr(Q) a barvu příslušnou hraně {i, j} jako Clri,j .

Položme nyní zi,j = 2Clri,j − 1.

Věta 2.4 Žádné dvě hrany faktoru se neprotínají. Důkaz: viz [3]. Žádné dva segmenty typu 2 a 8 se zjevně neprotínají — první typ využívá port +Y, druhý +Z. Segmenty typu 4 a 6 jsou vedeny v rovnoběžných rovinách. Segmenty typu 4 jsou vedeny v rovinách s lichými z-ovými souřadnicemi a segmenty typu 6 v rovinách se sudými z-ovými souřadnicemi, a proto žádný segment typu 4 neprotíná úsek typu 6 jiné hrany. Segmenty typu 4 využívají body Y = 5k + 4 a segmenty typu 6 využívají body X = 5l + 3, kde 0 < l, k ≤

lq

m

|V | . Segmenty typu 2 využívají body

X = 5l + 2 a Y = 5k + 3. Segmenty typu 8 využívají body Y = X = 5k + 2.

Dostáváme tedy, že segmenty typu 4 a 6 neprotínají segmenty typu 2 a 8.


20

Ilustrace 2.2 dokládá, že dva segmenty 4 hran e a f se mohou protínat jen tehdy, když mají počáteční vrcholy e a f shodnou x-ovou souřadnici. Dva segmenty 6 hran e a f se mohou protínat jen tehdy, když mají koncové vrcholy e a f shodnou y-ovou souřadnici. Obarvení Clr(H) tedy zajišťuje, že se žádné dvě hrany faktoru C2 neprotínají. Obdobně pro C3 . Věta 2.5 Pro každý souvislý graf s maximálním stupněm nejvýše 6 existuje 3DMNO. Každá hrana má nejvýše 8 segmentů. Takové nakreslení má objem √ √ √ O( n) ∗ O( n) ∗ O( n) a v dalším textu ho budeme nazývat kompaktním. Důkaz: viz [3]. Hrany faktoru C1 neprotínají hrany faktoru C2 ani C3 , neboť jediné body roviny Z = 0 používané hranami faktorů C2 a C3 jsou porty +Y a −Y. Hrany C3 leží v opačném poloprostoru než hrany C2 zjevně

se tedy neprotínají. Z 2.3 a 2.4 plyne, že žádné dvě hrany ve stejném faktoru se neprotínají. q

q

q

Mřížka má velikost 5 |V | × 5 |V | × (8 |V | − 3). Na vedení hran C2 je lq

potřeba 4(

m

|V | ) − 2 rovin rovnoběžných s rovinou Z = 0. Stejný počet

rovin je třeba pro vedení C3 . Navíc je nutno připočíst rovinu Z = 0.

2.3

Kubický algoritmus

V této části ukážeme, jak nalézt 3DMNO tak, aby se každá hrana sestávala maximálně z 4 segmentů. Definice 2.7 Buď G graf s očíslovanými vrcholy. Buď C kružnice na n vrcholech. Dále ať C je podgrafem G. Pak pořadím vrcholu v na kružnici C rozumíme číslo v mod n a značíme ord(v, C) = v mod n. Definice 2.8 Buď C = v1 . . . vn kružnice. Vrchol vi nazveme lokálním maximem vzhledem k C, pokud ord(vi , C) > ord(vi+1 , C)∧ord(vi−1 , C) < ord(vi , C).


21

Vrchol vi nazveme lokálním minimem vzhledem k C, pokud ord(vi , C) < ord(vi+1 , C) ∧ ord(vi−1 , C) > ord(vi , C). Vrchol, který není ani maximem ani minimem, nazveme normálním.

Definice 2.9 Buď C kružnice a její hrana e = {u, v}. Hranu e nazveme rostoucí, pokud ord(u, C) < ord(v, C).

Hranu nazveme klesající, pokud ord(u, C) > ord(v, C).

Umístění vrcholů Buď G = (V, E).Vrcholy umístíme libovolně na body (3i, 3i, 3i), kde 0 ≤

i < |V |.

Vedení hran Postupně vedeme hrany náležící faktorům C1 ,C2 a C3 . Přitom rozlišujeme hrany vstupující do lokálního minima respektive maxima. Tyto hrany jsou vedeny pomocí 4 segmentů. Hrany směřující do normálních vrcholů rozdělujeme na rostoucí respektive klesající a vedeme je pomocí 3 segmentů. Případné smyčky jsou vedeny pomocí 4 segmentů. Tabulka 2.3 popisuje trasování hran faktoru C1 . Hrany faktoru C2 jsou vedeny obdobným způsobem, ale využívají porty +Y a −X, hrany faktoru C3 pak využívají porty −Y a Z. Věta 2.6 Výše uvedený postup dává korektní 3DMNO s nejvýše 4 segmenty pro libovolný souvislý graf s maximálním stupněm nejvýše 6. Takové nakreslení má objem nejvýše O(n) ∗ O(n) ∗ O(n). Tento algoritmus budeme dále nazývat kubický. Důkaz: viz [3]


Rostoucí hrana {i, j} faktoru C1

22

Úsek

Začátek

Konec

1

(xi , yi, zi )

(xj , yi, zi )

2

(xj , yi, zi )

(xj , yj , zi )

3

(xj , yj , zi )

(xj , yj , zj )

Úsek

Začátek

Konec

1

(xi , yi, zi )

(xj , yi, zj )

2

(xi , yi, zj )

(xi , yj , zj )

3

(xi , yj , zj )

(xj , yj , zj )

Úsek

Začátek

Konec

1

(xi , yi, zi )

2

(xi , yi , zj − 1)

(xi , yi , zj − 1)

Klesající hrana {i, j} faktoru C1

Hrana {i, j} vstupující do lokálního minima

3

(xi , yj, zj − 1)

(xi , yj, zj − 1)

(xj , yj, zj − 1)

Úsek

Začátek

Konec

1

(xi , yi, zi )

(xj + 1, yi , zi )

2

(xj + 1, yi, zi )

(xj + 1, yj , zi )

3

(xj + 1, yj , zi )

(xj + 1, yj , zj )

4

(xj + 1, yj , zj )

(xj , yj , zj )

4 Hrana {i, j} vstupující do lokálního maxima

(xj , yj, zj − 1)

Obrázek 2.3: Vedení hran faktoru C2 viz [3].

(xj , yj, zj )


2.4

23

Přehled dalších výsledků

Následující věta demonstruje hlavní rozdíl mezi kreslením v rovině a kreslením ve 3D. Ve třírozměrném prostoru se totiž přímky nemusí protínat, i když nejsou rovnoběžné, a proto nemá smysl optimalizovat počet křížení jako při rovinném kreslením. Věta 2.7 Každý graf s n vrcholy lze nakreslit bez křížení hran na mřížku O(2n) × O(2n) × O(n). Hrany kreslíme rovnými čarami. Důkaz: viz [8] Věta 2.8 3DMNO lze získat v lineárním čase pro libovolný souvislý graf s maximálním stupněm nejvýše 6. Každá hrana takového nakreslení se skládá nejvýše ze 4 segmentů. Navíc vrcholy lze přidávat v konstantním čase. Hovoříme o inkrementálním 3DMNO. Důkaz: viz [9] Věta 2.9 Pro každý souvislý graf s maximálním stupněm 6 existuje 3DMNO. √ √ Nakreslení má objem nejvýše O( n) ∗ O( n) ∗ O(n) a každá hrana má nej-

výše 6 segmentů. Důkaz: viz [3]

Věta 2.10 Pro každý souvislý graf s maximálním stupněm 4 existuje 3DMNO. Každá hrana má nejvýše 3 segmenty a nakreslení má objem nejvýše O(n) ∗ O(n) ∗ O(1).

Důkaz: viz [3]


24

Obrázek 2.4: Graf K7 nakreslený kompaktním algoritmem.

2.5

Implementace

Implementován byl kompaktní a kubický algoritmus. Kompaktní algoritmus sice umísťuje vrcholy do roviny Z = 0, ale ilustrace 2.4 dokumentuje, že tento algoritmus neprodukuje přehledná nakreslení. Hrany skládající se z 8 segmentů je velmi obtížné rozeznat a podobně jako u inkrementálního algoritmu nevykazuje kresba žádnou symetrii. Kubický algoritmus produkuje relativně symetrická a přehledná nakreslení. Důvodem je, že většina hran je typicky nakreslena jako rostoucí popř. klesající a skládají se tedy pouze ze 3 segmentů. Navíc jsou hrany soustředěny kolem hlavní diagonály, na které jsou umístěny vrcholy. Tato pozorování jsou založena na ilustraci 2.5. Inkrementální algoritmus věty je velmi komplikovaný a jím vytvořená na-


25

Obrázek 2.5: Graf K7 nakreslený kubickým algoritmem. kreslení jsou podstatně méně přehledná než nakreslení generovaná kubickým algoritmem z věty 6. Příklad takového nakreslení demonstruje ilustrace 2.6. Hlavní příčinou je fakt, že předcházející algoritmy umísťují vrcholy do roviny, naopak inkrementální algoritmus vrcholy chaoticky rozmísťuje po celém prostoru. Ortogonální kreslení má význam spíše teoretický, výsledná nakreslení nejsou příliš vhodná pro prezentaci grafu uživateli. Jsou totiž asymetrická, a tudíž špatně čitelná. Využít by se naopak dala, pokud je tohoto nakreslení využito k následnému algoritmickému řešení jiného problému.


26

Obrázek 2.6: Graf K7 nakreslený inkrementálním algoritmem, zdroj: [9].

Kapitola 3 Fyzikální metody Fyzikální metody graf reprezentují jako fyzikální model a pomocí diskrétní simulace fyzikálního procesu se snaží nalézt vhodné nakreslení.

3.1

Základní algoritmus

První fyzikální model pro kreslení grafů pochází z [31]. Vychází se zde z představy, že graf je dobře nakreslen, pokud je délka hran minimalizována, a zároveň je maximalizována vzdálenost mezi vrcholy. Tento problém lze aproximovat následujícím fyzikálním modelem. Vrcholy budeme reprezentovat vzájemně se odpuzujícími náboji a pružiny budou simulovat přitažlivou sílu hran. Pro hrany dle Hookova zákona [32], dostáváme přitažlivou sílu: Fi,j = k dist i, j, kde k je váha dané pružiny. Pro vrcholy z Coulombova zákona [33], dostáváme odpudivou sílu: Fi,j =

Qi ∗ Qj , dist i, j 2 27

KAPITOLA 3. FYZIKÁLNÍ METODY

28

kde Qi , Qj jsou náboje příslušné vrcholům i, j. Pro každý vrchol v každé iteraci algoritmu spočítáme vektor síly působící na daný vrchol. Tímto vrcholem pak pohybujeme ve směru této síly. Rychlost vrcholu ivi v následujícím kroku dostáváme jako: vi = (F ∗ t + vi ) ∗ d, kde F je celková síla působící na vrchol i, t je čas, který uplynul mezi iteracemi a d je odpor prostředí, který zajišťuje konvergenci algoritmu. Výslednou pozici vrcholu iposi obdržíme následovně: posi = posi + vi ∗ t. Algoritmus končí, když dojde ke stabilizaci systému – tedy pokud je celková kinetická energie systému nízká. Kinetickou energii systému spočítáme jako P

i∈V

vi2 . Existuje celá řada modifikací tohoto základního algoritmu. Jednou

ze stěžejních technik je tzv. simulované žíhání viz [35], které se snaží předejít předčasné konvergenci ke špatnému lokálnímu minimu.

Simulované žíhání Simulované žíhání je obecný postup pro hledání globálního minima nekonvexní funkce. Vychází se zde z modelu ochlazování oceli. Je-li teplota vysoká, pohybují se částice rychleji a v konfiguraci tak může docházet k větším změnám. Je-li naopak teplota nízká, konfigurace se mění jen málo. V našem případě bylo po vzoru [35] použito lineárního ochlazování, nicméně ochlazovací schéma lze zvolit v podstatě libovolně. Jako zajímavá volba se jeví adaptivní schéma, které při rychlé konvergenci teplotu prudce snižuje, naopak při pomalé konvergenci je teplota zvyšována. V našem případě se vrchol v každé iteraci může posunout v každé souřadnici maximálně o T , kde T je právě teplota systému.


29

Shrnutí Fyzikální algoritmus 1. Rozmísti vrcholy náhodně 2. T :=konst 3. Dokud je kinetická energie systému dostatečně vysoká 4. Spočítej přitažlivé síly mezi hranami podle Hookova zákona 5. Spočítej odpudivé síly mezi vrcholy podle Coulombova zákona 6. Spočítej rychlost daného vrcholu 7. Posuň vrcholy ve směru na ně působící síly s maximálním posunem rovným T 8. Ochlaď systém T := T −konst; 9. Spočítej celkovou kinetickou energii systému 10. Vrať se na 3

3.2

Barycentrová metoda viz [24]

Barycentrová metoda rozděluje vrcholy grafu na pevné (V1 ) a pohyblivé (V2 ). Pevné vrcholy jsou umístěny na konvexní mnohoúhelník a pozice pohyblivých vrcholů je vyjádřena jako lineární kombinace pevných vrcholů. Pohyblivé body budeme umísťovat do barycentra neboli těžiště, tedy tam, kde se vyrovnávají síly působící na daný vrchol. V Tutteho modelu jsou jedinou silou působící na vrcholy pružiny mezi jednotlivými hranami. Umístění

30

KAPITOLA 3. FYZIKÁLNÍ METODY pohyblivých vrcholů tedy získáme řešením následující soustavy: X

wi,j xj = xi

i ∈ V2

X

wi,j yj = yi

i ∈ V2

i,j∈E

i,j∈E

xi = bxi

i ∈ V1

yi = byi

i ∈ V1

Definice 3.1 Nakreslení Q grafu nazveme rovinným, pokud jsou vrcholy umístěny v rovině a žádné dvě hrany se neprotínají. Graf je rovinný, pokud má alespoň jedno nakreslení. Definice 3.2 Nechť A je nějaká podmnožina roviny R. Nazveme ji souvislou, pokud pro ∀x, y ∈ A platí, že existuje oblouk o s koncovými body x

a y takový, že o ⊂ A. Oblouky příslušné hranám nakreslení grafu pak podle

této relace souvislosti rozdělují rovinu na třídy ekvivalence, které se nazývají stěny nakreslení grafu.[1]1 Definice 3.3 Graf je vrcholově k-souvislý, pokud zůstane po odebrání libovolných k − 1 vrcholů souvislým. Následující věta je jedním z velmi mála znamých tvrzení, která garantují charakter nakreslení získaného pomocí fyzikálních metod: Věta 3.1 (Tutteho) Buď G 3-souvislý rovinný graf a F jeho stěna v libovolném rovinném nakreslení. Položme nyní V1 = F. Pak barycentrová metoda nalezne rovinné nakreslení G s vnější stěnou F . 1

Autor této práce nemá rovinná nakreslení rád . . . této definici se opravdu chtěl vy-

hnout . . .


31

Důkaz: viz [24] Nicméně barycentrová metoda negarantuje rozměry nakreslení a výsledná nakreslení vykazují velmi malé úhlové rozlišení. Dochází i ke shlukování vrcholů. Uveďme tedy alespoň jedno tvrzení o rozměrech nakreslení získaného barycentrovou metodou. Věta 3.2 ∀n > 1 : ∃G rovinný takový, že nakreslení nalezené barycentrovou

metodou má exponenciálně velkou plochu vzhledem k n. Důkaz: viz [25]

3.3

Algoritmus Kamada-Kawai viz [26]

Na rozdíl od prvního modelu vychází tento algoritmus z odlišné definice dobrého nakreslení. Graf je dobře nakreslen, pokud je minimalizován následující výraz E=

X

i,j∈V

1 ki,j (||xi − xj || − di,j )2 , 2

kde di,j je délka nejkratší cesty v grafu mezi vrcholy i, j, ||xi − xj || označuje geometrickou vzdálenost mezi vrcholy i, j v nalezeném nakreslení, konečně pak ki,j =

K d2i,j

udává sílu pružiny mezi vrcholy i, j, kde K je konstanta určená na začátku algoritmu. Vrcholy zde nenesou tedy žádný náboj. Na začátku algoritmu je třeba nalézt nejkratší cesty mezi všemi vrcholy pomocí Floyd-Warschalova algoritmu viz [27] a náhodně rozmístit vrcholy. Cílem algoritmu je nalezení lokálního minima E - tedy takového bodu, kde

32


se anulují všechny parciální derivace E. V každé iteraci je vybrán vrchol vmax , pro který je ∆v =

v u u t

∂E ∂x

!2

∂E + ∂y

!2

maximální, kde x a y jsou souřadnice daného vrcholu. V tomto kroku je E považováno za funkci proměnné vmax a pomocí Newtonovy metody viz [29] hledáme řešení (δx , δy ) následujícího systému rovnic: ∂2E ∂2E ∂E ∗ δ + ∗ δy = − x 2 ∂ xmax ∂xmax ymax ∂xmax ∂2E ∂E ∂2E ∗ δ + ∗ δ = − . y x ∂ 2 ymax ∂xmax ymax ∂ymax Následně upravíme pozici vm ax následovně: xmax = xm ax + δx ymax = ym ax + δy . Takto pokračujeme, dokud není dosaženo požadované přesnosti.

Shrnutí Algoritmus Kamada-Kawai Vstup: souvislý ohodnocený graf G Výstup: Nakreslení grafu G 1. Nalezni teoretické grafové vzdálenosti v G pomocí Floyd-Warschallova algoritmu 2. Náhodně rozmísti vrcholy G 3. Pokud nebylo dosaženo požadované přesnosti, nalezni vrchol vm ax, jehož ∆ je maximální.


33

4. Urči (δx , δy ) vyřešením výše uvedené soustavy 5. Posuň vmax 6. Vrať se na 3

3.4

Zhodnocení

Hlavní výhodou fyzikálních metod je ve srovnání s dále popsanými algebraickými metodami, možnost jejich využití pro doladění nalezeného nakreslení. Algoritmus založený na odpudivých silách mezi vrcholy je navíc vhodný ve chvíli, kdy byly některé hrany z původního grafu odebrány a následně vedeny náhodně jako např. u grafů typu small world viz část 5.2 a následující obrázek 3.1 Dodejme, že žádný z algoritmů v následující kapitole nedokáže ani zdaleka nalézt podobně rozumné nakreslení. Naopak nevýhodou fyzikálních algoritmů je až na Tutteho větu absence garancí pro charakterizaci výsledného nakreslení. Problémem jsou zde zejména grafy s nízkým počtem hran jako kružnice. Žádná fyzikální metoda není schopna konzistentně nalézt konvexní nakreslení pro dlouhé kružnice. Na obrázku 3.2 vidíte kružnici na 1 000 vrcholech nakreslenou pomocí algoritmu na bázi Fruchterman-Reingoldova postupu. Fyzikální postupy negarantují dosažení globálního minima a jsou často závislé na vhodné iniciální konfiguraci. Lze je snadno přenést do 3D, ale na rozdíl od algoritmů z následující kapitoly, jim není 3D nakreslení vlastní.


34

Obrázek 3.1: Graf typu small world (100,4,5) nakreslený fyzikálním algoritmem

Obrázek 3.2: Kružnice na 1000 vrcholech nakreslená fyzikálním algoritmem

Kapitola 4 Algebraické metody V této části popíšeme algoritmus PCA projekce pocházející z [12] a porovnáme ho s námi navrhovaným novým algoritmem.

4.1

Problém k-center

Definice 4.1 Problém Q nazveme problémem třídy NP , pokud lze jeho

řešení ověřit v polynomiálním čase.

Definice 4.2 Problém Q nazveme NP -úplným, pokud lze každý problém

třídy NP, převést v polynomiálním čase na problém Q a Q ∈ N P.

Definice 4.3 (Problém k-center) Problém k-center definujeme následovně: Buď S množina n bodů v prostoru s mírou dist . Najdi množínu C velikosti k takovou, že

max min dist(c, s) je minimální. s∈S

c∈C

Věta 4.1 Problém k-center je NP -těžký. 35

KAPITOLA 4. ALGEBRAICKÉ METODY

36

Důkaz: viz [16]. Definice 4.4 Buď I množina všech instancí NP -úplného problému Q. Polynomiální algoritmus A nazveme -aproximací NP -úplné úlohy Q, jestliže C C∗ max , I C∗ C (

)

≤ ,

kde C je cena řešení nalezená A a C ∗ je optimální řešení Q.

2-Aproximace problému k-center hladovým algoritmem Vstup: Množina S 1. Vyber s ∈ S libovolně, polož S = S\{x} a S = {c}. 2. Najdi bod x ∈ S takový, že min dist(x, c) je maximální. c∈C

3. Polož S = S\{x} a C = C∪{x}. 4. Pokud |C| < k , vrať se na 2. Definice 4.5 Alternativně lze problém k-center definovat takto: Buď S mno-

žina. Rozhodni, zda existuje k hyperkoulí s poloměrem r,které pokrývají množinu S. Věta 4.2 Výše uvedený algoritmus je 2-aproximací problému k-center. Důkaz: viz [17]. Buď r ∗ optimální řešení problému k-center. Označme r řešení nalezené aproximačním algoritmem. Pro spor buď r > 2r ∗ . Existuje tedy bod x, který je vzdálen alespoň r od k center nalezených aproximačním algortimem. Pak ovšem body nalezené aproximačním algoritmem a tento bod mají vzájemnou vzdálenost alespoň r. Ovšem v žádné hyperkouli o poloměru


37

r ∗ nemohou být dva body se vzdáleností větší než 2r ∗ . Tudíž k pokrytí množiny by bylo třeba alespoň k+1 hyperkoulí, což je spor s faktem, že existuje pokrytí množiny k hyperkoulemi. Hladový algoritmus není pouze 2-aproximací problému k-center, ale dokonce platí i následující tvrzení. Věta 4.3 Pokud P 6= NP, pak je uvedený hladový algoritmus nejlepší mož-

nou polynomiální aproximací problému k-center. Důkaz: viz [16]

Problém k-center jsme zde definovali obecně, budeme ho však aplikovat na grafy. Množinou S bude tedy množina vrcholů. Metrikou dist v našem případě bude teoretická grafová vzdálenost - tedy cena nejkratší cesty mezi vrcholy i, j. V případě, že graf bude mít kladně ohodnocené hrany, využijeme k nalezení nejvzdálenějšího vrcholu v kroku 3 Dijkstrova algoritmu. Pokud budou mít hrany jednotkovou délku, aplikujeme průchod do šířky(BFS). Použitím hladového algoritmu pro řešení problému k-center získáme nakreslení grafu v k dimenzích. Toto nakreslení nazveme high-dimensional embedding(HDE). Jako optimální počet center se jeví m = k = 50 bez ohledu na velikost a strukturu grafu.


4.2

38

PCA (Principal Component Analysis)

V předcházející části jsme ukázali, jak získat HDE. HDE však nelze přímo zobrazit na monitoru. Je tedy třeba nalézt reprezentaci HDE v 2D nebo 3D, která odhalí strukturu HDE daného grafu. Jako vhodná metrika pro nalezení vhodné reprezentace HDE se jeví maximalizace vzdálenosti mezi jednotlivými vrcholy G tak, aby bylo možné vrcholy jednoznačně odlišit. Je však nutné nalézt vhodné omezení pro možná zobrazení tak, abychom zabránili divergenci vrcholů do nekonečna. [12] V této části tedy ukážeme, jak věrně zobrazit více-dimenzionální data ve 2D a 3D. Tyto zobrazovací techniky souhrnně nazýváme metodami pro redukci dimenze(RD). V praxi je využívaná celá řada těchto technik viz [19]. V našem případě však bude hlavním kritériem pro volbu metody její časová složitost - Jak bude ukázáno v 4.5 lze graf nakreslit za využití Hallovy energie s kvadratickou složitostí. Toto dává rozumnou rychlost pro grafy se zhruba 5 000 uzly, ale je velmi pomalé pro velmi velké grafy. Jednou ze základních metod pro redukci dimenze je právě PCA. Buď X tvaru m × n matice pozorování. X se skládá z n m-dimenzionálních cen-

tralizovaných pozorování. PCA hledá navzájem kolmé lineární kombinace w1 . . . wp

1

vektorů x1 ....xn takové, že si = wi x má maximální rozptyl. Tedy

w1 = w1,1 . . . w1,m jsou koeficienty lineární kombinace vektorů x1 . . . xn takové, že vektor s1 = w1 x má největší rozptyl. Zjevně by však pro x → ∞

rozptyl divergoval, a tedy zavedeme omezení |wi| = 1. Koeficienty w2 =

w2,1 . . . w2,m přísluší lineární kombinaci, která je kolmá na w1 a navíc vektor s2 = w2 x má největší rozptyl ∀w w ⊥ w1 . 1

p je dimenze finálního prostoru, do kterého budeme pozorování zobrazovat - typicky

tedy 2 nebo 3

39


Algoritmus pro nalezení PCA Vstup: matice X tvaru m × n - reprezentující HDE grafu G = (V, E) 1. Centralizuj jednotlivá pozorování - xi,j = xi,j −

Pn

k=1

xi,k

n

2. Spočítej kovariační matici Cov = XX T - Kovariační matice je tvaru m×m 3. Nalezni dominantní/největší/ vlastní čísla λ1 ≥ . . . ≥ λp > 0 a jím příslušné vlastní vektory U = u1 . . . up matice Cov

4. Vypočítej projekci X T U - toto je hledané zobrazení HDE v p dimenzích. Věta 4.4 Výše uvedený algoritmus nalezne projekci, která maximalizuje X

dist(i, j) = uT XX T u

i,j∈V

na množině |v| = 1 – tuto projekci nazýváme PCA-projekcí. Hledat tedy

budeme především vlastní vektory příslušné největším vlastním číslům kovariační matice. Důkaz: viz [12] a [20] Zbývá ukázat, jak nalézt vlastní čísla kovariační matice. Tato matice je symetrická, a má tedy všechna vlastní čísla reálná. K nalezení dominantních vlastních čísel použijeme mocninné metody. Mocninná metoda vychází z pozorování, že pokud je matice A pozitivně semidefinitní a u1 vlastní vektor příslušný dominantnímu vlastnímu číslu A , pak pro libovolný vektor x, pro který u1 x 6= 0, konverguje řada Ax, A2 x . . . An x k u1 .


Mocninná metoda viz[12] Vstup: Pozitivně definitní matice A 1. uî := náhodný normovaný vektor 2. ui := uî 3. Ortogonalizuj ui vůči předchozím vlastním vektorům: for j := 1 to i − 1 ui := ui − (uiuj ) 4. uî := Auî 5. normalizuj uî 6. pokud ui uî > 1 − :

i := i + 1, jdi na 1

7. pokud ui uî ≤ 1 − :

jdi na 2

Shrnutí a složitost Algoritmus PCA pro kreslení grafů 1. Získej matici HDE X 2. Spočítej kovariační matici XX T 3. Nalezni dominantní vlastní vektory kovariační matice 4. Projekce HDE podle získaných vlastních vektorů

40


41

K získání HDE je třeba času O(m∗(|V |+|E|)) pro graf s jednotkovým ohodnocením hran, kde m je počet pivotů. Pro většinu grafů se jeví volba m = 50

jako optimální pro kvalitu výsledného nakreslení. Výpočet kovariační matice lze provést v čase O(m2 ∗ |V |). Tento algoritmus produkuje nejlepší výsledky

pro relativně řídké grafy. Pro řídké grafy je tedy nejvýznamnější výpočet kovariační matice. Pro husté grafy naopak převládá výpočet HDE.

Projekce mezi 2D a 3D nakreslením Dalším využitím algoritmu PCA je nalezení vhodné projekce třídimenzionálního nakreslení grafu do 2D. Jak bylo dokázáno v 4.4 maximalizuje PCA projekce vzájemné vzdálenosti mezi jednotlivými vrcholy. Pokud nás tedy bude zajímat nakreslení grafu ve 2D a máme již jeho nakreslení ve 3D, stačí matici tohoto nakreslení vynásobit její transpozicí. Tak získáme nakreslení ve 3D.

4.3

Laplacian Preserving Projection - LPP

Hallova energie Definice 4.6 Buďte A, B čtvercové matice. Zobecněným vlastním číslem matice A vůči matici B nazveme číslo λ, pokud existuje vektor x 6= ~0 : Ax =

λBx. Vektor x pak nazýváme zobecněným vlastním vektorem.

Definice 4.7 Buď G = (V, E) graf a wG : E → <+ ohodnocení jeho hran.

Pak Laplacián L grafu G je matice tvaru |V | × |V | definovaná následovně: li,j =

          

−wG (i, j), pokud i, j ∈ E P

wG (i, k), pokud i = j

{i,k}∈E

0 jinak

42

KAPITOLA 4. ALGEBRAICKÉ METODY Definice 4.8 Matice vah W grafu G je definována následovně:     

wG (i, j), pokud i, j ∈ E

wi,j =  0 pokud i=j - smyčky jsou zakázány    0 jinak

Definice 4.9 Diagonální maticí D grafu G rozumíme matici D = W − L. Definice 4.10 (Hallova energie) Hallovou energií EH (G, Φ) nakreslení Φ grafu G rozumíme EH (G, Φ) =

1 X wi,j (Φ(i) − Φ(j))2 . 2 {i,j}∈E

Předchozí definice odpovídá intuitivní představě, že čím je váha hrany e významnější, tím blíže by měli ve výsledném nakreslení být její vrcholy. Označme nyní Φ(i) = xi a X = {x1 . . . xn }. V optimálním nakreslení by tedy měla být minimalizována délka hran. Je zjevné, že umístění všech vrcholů v počátku však není vhodným minimem, a proto je třeba definovat množinu, na které budeme Hallovu energii optimalizovat. Logickou volbou se jeví xxt = 1 - tedy množina vektorů s normou 1. Věta 4.5 Platí, že EH (G, Φ) = XLX T a min XLX T . Důkaz: viz [10]. Roznásobením dostáváme: EH (G, Φ) =

n n n n X 1 X 1 X 1 X wi,j xi xj wi,j (xi −xj )2 = wi,j x2i + wi,j x2j − 2 i,j=1 2 i,j=1 2 i,j=1 i,j=1

Protože je W symetrická, a tedy

n P

i,j=1

wi,j x2i =

n P

i,j=1

wi,j x2j , platí:

n n n n n X X X 1 X 1 X 2 2 2 wi,j xi + wi,j xj − wi,j xi xj = wi,j xi − wi,j xi xj 2 i,j=1 2 i,j=1 i,j=1 i,j=1 i,j=1

43

KAPITOLA 4. ALGEBRAICKÉ METODY Analýzou první sumy dostáváme: n X

wi,j x2i

=

i,j=1

n X i=1

n X

!

wi,j x2i =

j=1

n X

li,i x2i

i=1

Z druhé sumy dostáváme,neboť ∀i : wi,i = 0 : n X

wi,j xi xj =

i,j=1

n X

i,j=1; i6=j

wi,j xi xj = −

n X

li,j xi xj

i,j=1; i6=j

Dohromady tedy dostávame: EH (G, Φ) =

n X 2 wi,j wi,j xi − i,j=1 i,j=1 n X

xi xj =

n X

li,j xi xj +

i,j=1; i6=j

n X

li,i x2i = XLX T

i=1

Věta 4.6 Extrémy Hallovy energie získáme jako vlastní vektory Laplaciánu, příslušná vlastní čísla pak odpovídají hodnotě Hallovy energie v daném extrému. Důkaz: viz [10].

Odvození algoritmu Naše metoda vychází z myšlenky, že zejména u symetrických grafů je graf indukovaný pivoty Gp dobrou aproximací původního grafu, a stačí tedy minimalizovat jeho Hallovu energii. Takto vytvořené nakreslení dává pro řadu grafů velmi přesnou aproximaci optimálního nakreslení původního grafu. Ohodnocení hran W p grafu Gp definujeme následovně: p wi,j = di,j , kde di,j je délka nejkratší cesty mezi pivoty i, j v grafu G.

Laplacián a diagonální matici Gp označíme Lp a D p . Je třeba nalézt obdobné omezení jako u původního grafu. Jako vhodná norma pro graf Gp se jeví xDxT = 1. Tato norma rozmisťuje vrcholy do n-dimenzionálního elipsoidu,


44

kde vrcholy s větší vahou leží blíže počátku. Naopak vrcholy s nižší vahou budou umístěny dále od počátku. Názornou analogií je zde model atomu – hmotné protony a neutrony se nachází v jádru, naopak lehké elektrony obíhají po eliptických drahách v elektronovém obalu. Nahradíme tedy problém minimalizace Hallovy energie původního grafu následujícím minimalizačním problémem pro graf Gp : min xLp xT .

xD p xT =1

Definice 4.11 Prostor spojitě diferencovatelných funkcí značíme C. Definice 4.12 Buď f (x) z C skalární funkcí vektoru x. Gradient f definujeme jako n-dimenzionální vektor parciálních derivací, značíme f racdfdx. Věta 4.7 Buď S symetrická matice a f (x) = xT Sx Důkaz: viz [10] Ukážeme nyní, že námi definovaný problém minimalizuje Hallovu energii grafu Gp . Věta 4.8 Extrémy předchozího minimalizačního problému získáme jako vlastní vektory následujícího zobecněného problému vlastních čísel, příslušná vlastní čísla pak odpovídají hodnotě Hallovy energie v daném bodě. Důkaz: Vyjdeme z věty o Lagrangeových multiplikátorech pro nalezení vázaného extrému. Minimalizujeme tedy xLp xT vůči vazbě xD p xT − 1 = 0.

Dostáváme tedy následující minimalizační problém xLp xT − λ(xD p xT − 1),

kde λ je hledaný Lagrangeův multiplikátor. Derivací podle x viz 4.7 obržíme: Lp x − λD p x = 0


45

Lp x = λD p x, a navíc pro Hallovu energii Gp platí: EH (Gp , Φ) = xLp xT = xD p xT . Z výše uvedeného tedy vyplývá, že na rozdíl od PCA-projekce, zde budeme hledat nejmenší vlastní čísla. Nejmenší vlastní číslo λ1 je ovšem rovno 0 1 1 a výsledný vlastní vektor odpovídá degenerovanému řešení x = ( d1,1 ), . . . dn,n

proto budeme hledat vlastní vektory λ2 . . . λ4 viz[5]. Je ovšem vhodné spočítat i další vlastní vektory, neboť nakreslení získané na základě těchto vektorů má vyšší estetickou kvalitu než to získané pomocí λ2 . . . λ4 .

Výpočet zobecněných vlastních čísel V této části ukážeme, jak převést problém nalezení zobecněných vlastních vektorů na problém nalezení klasických vlastních vektorů. Proces je velmi zjednodušen faktem, že D je diagonální, a vyhneme se tak definici pseudoinverzní matice. V případě, že D není diagonální, lze postupovat obdobně a transformační algoritmus pro tento případ je popsán a vysvětlen v [18]. K vyřešení výsledného problému využíváme algoritmus QR implementovaný v knihovně ALGLIB viz[22]. Detailní přehled algoritmů po nalezení vlastních lze nalézt v EIG001. Lze také použít mocninné metody, zde je však třeba nejprve převést výše uvedený problém nalezení nejmenších vlastních čísel na problém nalezení největších vlastních čísel za pomoci odhadu největšího vlastního čísla pomocí Geršgorinových kruhů viz[11]. 1

Definice 4.13 Buď A pozitivně definitní čtvercová matice. Pak existuje A 2 1

1

horní trojúhelníková taková, že A = A 2 A 2 T . Tento rozklad matice A nazýváme Choleského dekompozicí.

46


Mějme tedy Lx = λDx, kde D je diagonální matice a L je symetrická. Pak Choleského dekompozicí D dostáváme: 1

1

Lx = λD 2 D 2 x. Inverzní matici D

−1 2

1

1

k D 2 získáme invertováním prvků na diagonále v D 2 . A

tak dostáváme: Lx = λDx 1

1

Lx = λD 2 D 2 x LD D

−1 2

−1 2

1

1

1

D 2 x = λD 2 D 2 x

LD

−1 2

1

1

D 2 x = λD 2 x

1

Položme nyní y = D 2 x a získáme standardní problém zobecněných vlastních vektorů tvaru: D

−1 2

LD

−1 2

y = λy

Vlastní vektory původní úlohy získáme jako x = D

−1 2

y.

Shrnutí algoritmu LPP Algoritmus LPP pro kreslení grafů Vstup: graf G 1. Nalezni matici X příslušenou k HDE grafu G 2. Vytvoř Laplacián a Diagonální matici pivotového grafu Gp 3. Nalezni vlastní čísla λ2 . . . λ4 a vlastní vektory u2 . . . u4 zobecněného problému vlastních čísel Lp x = λD p x 4. Spočítej projekci xi = Xui


47

Složitost a srovnání s jinými metodami V [11] je uvedena podobná metoda SSO (Subspace optimalization), avšak k získání Laplaciánu grafu Gp je použito relativně zdlouhavé násobení matic, které využívá Laplaciánu původního nekontrahovaného grafu. Složitost se tedy zvyšuje velmi rychle s růstem počtu hran grafu G. Naše metoda k získání Laplaciánu využívá pouze pivotových vrcholů, a je tedy zřetelně rychlejší než SSO, a dokonce rychlejší než PCA. Nejnáročnějším krokem PCA-projekce je u řídkých grafů právě výpočet XX T . Na rozdíl od SSO není potřeba násobit matice XLX T , což ušetří O(m|E| + m2 n) času. Oproti PCA odpadá násobení XX T , které je u řídkých grafů komputačně náročnější než BFS. Upozorněme na nesrovnalost ve výsledcích v [12]. Zbývá tedy jen zpětná projekce, kterou lze ve 3D provést v čase O(3∗m∗n). Asymptotická složitost našeho algoritmu je tedy O(m∗BFS +3∗ m ∗ n + QR(m)) = O(m ∗ BFS +3 ∗ m ∗ n) = O(m ∗ (n + E)) pro grafy s jednotkovým ohodnocením hran a O(m ∗ Dijkstra +3 ∗ m ∗ n + QR(m)) = O(m∗Dijkstra) = O(m∗(log |V |V +E)) pro grafy s nezáporně ohodnocenými

hranami za použití Dijkstrova algoritmu viz [14] a Fibonacciho haldy viz [13].

Metoda ACE [10] provádí shlukování grafu ve více krocích. Při každé iteraci se počet vrcholů grafu zmenší zhruba na polovinu. Hlavním rozdílem oproti našemu algoritmu však je fakt, že velikost finálního Laplaciánu u ACE závisí na velikosti původního grafu, což vede k relativně komplikovanému a pomalému výpočtu vlastních čísel potenciálně velké matice. Zejména při zobrazení grafu ve 3D je toto obzvláště citelné - je totiž třeba spočítat 3 vlastní vektory pomocí mocninné metody oproti 2 ve 2D. Na druhou stranu ACE nevyužívá HDE a může se tak vyhnout některým nedostatkům této metody - jako např. problémy u grafů s malým poloměrem. Naše metoda je tedy rychlejší než ACE,PCA i HDL. U těchto metod v praxi nejvíce času trvá právě násobení matic viz [11] a [12], které u naší metody

48

KAPITOLA 4. ALGEBRAICKÉ METODY odpadá.

Poté, co jsme algoritmus implementovali, objevili jsme podobnou myšlenku v [15] se shodnou složitostí. V tomto algoritmu je k definici Laplaciánu navíc využito vzorkování řádek a sloupců matice X. Výsledný minimalizační problém využívá jinou metriku kontrahovaného prostoru - xW xT . Kvůli této definici je zde zapotřebí výpočet pseudoinverzní matice, což vede k určité numerické nestabilitě, která je sice odstranitelná, ale jak ukazuje naše metoda, lze se jí zcela vyhnout. V naší metodě je totiž D diagonální a Choleského rozklad je tedy triviální. Problém zobecněných vlastních čísel lze tedy přímo redukovat na klasický problém vlastních čísel, jak bylo ukázáno výše. Rozhodně by bylo zajímavé provést detailní srovnání obou metod. Příklady uvedené v [15] se zdají být velmi podobné našim výsledkům.

2

Porovnání PCA a LPP Algoritmy jsme porovnávali na počítači s procesorem AMD64 3500 běžícím ns taktovací frekvenci 2.21 GHz s 1GB RAM. Počet pivotů pro vytvoření HDE matice byl ponechán na 50. Nejprve prakticky demonstrujeme, že algoritmus LPP skutečně pracuje v lineárním čase vůči počtu vrcholů. Pro demonstraci použijeme čtvercové mřížky o velikosti 100×100, 200×200 a 400×400. Vidíme, že pro čtyřnásobně veliký vstup je doba běhu programu zhruba čtyřikrát tak dlouhá. Bohužel se zdá, že námi využívaná knihovna Boost::Graph je málo výkonná ve srovnání s optimalizovanými ad hoc řešeními, a proto je i naše implementace relativně pomalá. Na druhou stranu je aplikace i tak dostatečně rychlá pro vykreslení grafů s velikostí řádově 100 000 vrcholů v rozumném čase, a to pro praktickou demonstraci vlastností LPP zcela postačuje. 2

Školitel sice byl v roce 2006 na prezentaci výše uvedené práce, ale vzhledem k nevol-

nosti si na tuto práci nepamatoval.

49

KAPITOLA 4. ALGEBRAICKÉ METODY Graf

|V |

LPP v sekundách

HDE

Zpětná projekce

10 000

0.844

0.687

0.125

40 000

4.282

3.832

0.657

Grid 400 × 400 160 000

17.28

15.22

1.86

Grid 100 × 100 Grid 200 × 200

Tabulka 4.1: Doba běhu algoritmu LPP pro čtvercové mřížky. Graf

|V |

PCA v sekundách

HDE

Kovariční matice

10 000

2.593

0.843

1.719

40 000

13.13

4.745

8.464

Grid 400 × 400 160 000

36.12

13.11

22.59

Grid 100 × 100 Grid 200 × 200

Tabulka 4.2: Doba běhu algoritmu PCA pro čtvercové mřížky. Pro srovnání uveďme dobu běhu algoritmu PCA pro výše zmíněné grafy. Vidíme, že doba běhu algoritmu PCA je zhruba dvojnásobná oproti LPP. Většina času je dle očekávaní využita pro výpočet kovariační matice. Dodejme, že obě metody naleznou správné nakreslení mřížky. Po lehké rozcvičce je na čase demonstrovat jednu velmi příjemnou vlastnost algoritmů založených na HDE. Z grafu lze náhodně odebírat hrany a výsledné nakreslení zůstane nadále kvalitní. Na rozdíl od fyzikálních algoritmů, kde se odebíráním hran narušuje konvergence, zde zůstavají nejkratší cesty v podstatě nezměněny. Tím pádem je i výsledné nakreslení kvalitní. Na obrázku 4.3 vidíte krychlovou mřížku o hraně velikosti 11, ze které bylo náhodně odebráno 20% hran. Tato mřížka byla vykreslena algoritmem LPP vlastními čísli 2, 3, 4. Tento graf také demonstruje, že ne vždy jsou vlastní čísla 1, 2, 3 ta nejlepší. Další úvaha nás vede k tomu, že ne vždy je hladový algoritmus pro výběr pivotů zcela vhodný. Uvažujme například mřížku, ke které bylo přidáno 50 izolovaných vrcholů. Hladový výběr bude brát izolované vrcholy jeden po druhém a výsledek bude pochopitelně zhoubný. Naopak náhodným výběrem můžeme v takovém případě získat rozumné nakres-


50

lení. Naopak u grafů, kde jsou náhodné hrany přidávány, vzniká problém. Hrany, které spojují jinak odlehlé části grafu, poruší i celé HDE. Je třeba si uvědomit, že v případě, že existují hrany, které spojují odlehlé části grafu, je metrika indukovaná nejkratšími cestami značně divoká a obtížně představiltená. Jako zajímavý problém se nabízí otázka charakterizace prostorů generovaných metrikou nejkratších cest. Dále platí, že metodami založenými na HDE nelze kreslit stromy. Koren se domnívá, že je to způsobeno tím, že prostor generovaný HDE stromů má vysokou dimenzi.[12] Dalšími grafy, které nelze pomocí HDE věrně nakreslit, jsou husté grafy. Například HDE úplného grafu je matice se samými jedničkami, jen pivotové vrcholy mají jednu nulu. Jakákoliv projekce HDE zjevně musí mapovat všechny nepivotové vrcholy do jednoho bodu. Na obrázku 4.3 vidíte Sierpinského fraktál hloubky 9 nakreslený algoritmem LPP. Velmi zajímavé je perfektní 3D nakreslení grafu finap512 4.3 na více než 70 000 vrcholech a s 200 000 hranami ve 3D s využitím vlastních čísel 0, 1 a 2. Tento graf demonstruje, že LPP přesně zobrazí globální kruhovou topologii, a zároveň věrně zobrazí i detailní věžovité struktury na obvodu. LPP je velmi přesná, pokud jde o nalezení věrného globálního nakreslení, jak demonstruje globální zobrazení grafu 4elt2 4.3. Oproti stejnému nakreslení metodou PCA 4.3 jsou hrany nakreslení raketoplánu zaoblené. Zde je vhodné dodat, že Hallova energie žádným způsobem nebrání shlukování vrcholů, a proto jsou vrcholy ve 2D nakreslení metodou LPP rozmístěny nerovnoměrně. Naopak PCA rozmísťuje vrcholy lokálně symetricky. Lokální symetrie však zde není tak významná, podstatný je především globální tvar křídla. Algebraické metody jsou velmi vhodné pro využití ke 3D zobrazení, jak ukazuje velmi pěkné nakreslení téhož grafu na obrázku 4.3. Na rozdíl od fyzikálních metod, které vznikly primárně pro 2D, vychází algebraické metody z prostorů vyšší dimenze. Zobrazení ve 3D odstraní nedostatky obou porov-


51

návaných metod. Nedochází zde k žádnému shlukování vrcholů. Důvodem je, že třetí vlastní číslo zde podává dodatečnou informaci právě o okrajových částech grafu. Předchozí pozorování platí nejen pro graf 4elt2, ale i řadu dalších. Oblíbeným grafem testerů3 je graf s názvem crack, jehož nakreslení algoritmem LPP opět vykazuje vysokou míru symetrie (obrázek 4.3). Ilustrace 4.3 a 4.3 kontrastují nakreslení grafu big pomocí LPP a PCA ve 3D. Nakreslení pomocí LPP zde přesně identifikuje globální strukturu a zejména centrální část je velmi estetická. PCA zachovává lokální symetrii, celkový tvar kresby je však nepřesný zejména v centrální části. Konečně ilustrace 4.3 a 4.3 porovnávají nakreslení grafu 3elt oběma metodami. Zde je naopak zřejmým vítězem PCA projekce, která zobrazí lokální symetrii přesněji nežli LPP. Lze tedy říci, že LPP produkuje globálně symetrická nakreslení. Při zobrazení ve 2D dimenzi vykazují však tendenci ke shlukování vrcholů, která vyplývá z definice Hallovy energie. Naopak PCA projekce částečně obětuje globální symetrii ve prospěch symetrie lokální a je na srovnatelných datech pomalejší než LPP. V tabulce4.3 vidíte srovnání doby běhu obou algoritmů na některých zde uvedených grafech. Je vidět, že ve většině případů je LPP až o polovinu rychlejší než PCA projekce, neboť nehledá kovariační matici. Prezentované grafy byly získany z [46] a [47].

3

Jednomu z laických testerů připomínalo nakreslení dámské spodní prádlo.

52


Graf

Tabulka 4.3: Porovnání běhu algoritmů |V | |E| PCA v sekundách LPP v sekundách

4elt2

11143

65636

3.047

2.000

big

15606

45878

5.751

2.062

finap512 74752 261120

30.67

11.96

3elt

4720

27444

1.204

0.656

crack

10240

30380

2.875

1.360

Tabulka 4.4: Doba běhu algoritmu PCA pro čtvercové mřížky.

Obrázek 4.1: Globální nakreslení grafu 4elt2 pomocí LPP.

Obrázek 4.2: Globální nakreslení grafu 4elt2 pomocí PCA.


Obrázek 4.3: Nakreslení grafu 4elt2 pomocí LPP ve 3D.

Obrázek 4.4: Nakreslení grafu big metodou PCA.

Obrázek 4.5: Nakreslení grafu big metodou LPP.

53


Obrázek 4.6: Nakreslení grafu 3elt metodou PCA.

Obrázek 4.7: Nakreslení grafu 3elt metodou LPP.

Obrázek 4.8: Sierpinského hvězda hloubky 9 metodou LPP.

54


55

Obrázek 4.9: Graf airfoildual nakreslený metodou LPP.

Obrázek 4.10: Graf Finap512 metodou LPP – pomocí vlastních čísel 0, 1 a 2.

Obrázek 4.11: Graf crack nakreslený metodou LPP ve 3D.


56

Obrázek 4.12: Mřížka 100 × 100 3D LPP-projekce.

Obrázek 4.13: Pohled do centra grafu sphere, LPP projekce ve 3D.

Obrázek 4.14: Krychle 11 × 11 × 11 pomocí vlastních čísel 2, 3 a 4 metodou LPP.

4

Kapitola 5 Uživatelská dokumentace Program GraphDraw slouží k editaci a vizualizaci grafů jak ve 2D tak ve 3D. Umožňuje dále ukládat grafy včetně jejich nakreslení ve formátu GRAPHML. Aplikace je psána pro operační systém Windows.

5.1

Instalace

Vložte CD do mechaniky. Otevřte mechaniku a dvakrát klikněte na ikonu setup.exe. Postupujte podle instrukcí instalátoru a vyberte adresář, kam chcete GraphDraw uložit.

5.2

Spuštění programu

Program můžete po instalaci spustit dvojitým kliknutím na ikonu graphd rawpmozP lochy.P oppaddv

57

KAPITOLA 5. UŽIVATELSKÁ DOKUMENTACE

5.3

58

Menu - File

Menu File obsahuje následující položky:

Položka New Nahradí aktuální graf prázdným grafem.

Položka Load GML Po vybrání této položky se objeví okno, které vidíte na obrázku 5.1. Horní část dialogu zobrazuje absolutní cestu do aktuálního adresáře. Pod ní jsou vypsány složky a soubory, které tento adresář obsahuje. Kliknutím na adresář přejdete do Vámi vybraného adresáře. Po stisknutí tlačítka OK bude načten Vámi vybraný soubor ve formátu GRAPHML. Stisknutím tlačítka Cancel opustíte toto menu.

Položky Load SRC a Load GRA Fungují shodně jako předcházející, avšak načten bude soubor ve formátu SRC respektive GRA.

Položka SaveGML Po stiknutí tohoto tlačítka se objeví dialog, který vidíte na obrázku 5.2. V horní části dialogu je zobrazena absolutní cesta do adresáře, ve kterém se právě nacházíte. V prostřední části vidíte podadresáře a soubory, které se nachází v aktuálním adresáři. Dvojím kliknutím na podadresář do něho přejdete. Jméno souboru nastavíte v dolní části okna v položce Filename.


59

Obrázek 5.1: Dialog pro načtení souboru. Alternativně můžete nastavit jméno souboru dvojím kliknutím na jméno souboru v seznamu souborů.Po stisknutí tlačítka OK se uloží právě editovaný graf. Stisknutí tlačítka Cancel ukončí dialog.

Položka Quit Vybráním této položky ukončíte aplikaci.


60

Obrázek 5.2: Dialog pro uložení souboru.

5.4

Generování grafů

Graphdraw umí generovat řadu základních typů grafů. Všechny následující možnosti vyvoláte prostřednictvím menu Generate Graph.

Kružnice – Cycle Vygeneruje kružnici na Vámi zadaném počtu vrcholů (Number of vertices).


61

Sierpinského Fraktál – Sierpinski Triangle Vygeneruje Sierpinského fraktál Vámi zvolené hloubky (Depth). Konstrukce Sierpinského fraktálu je popsána např. v [34].

Small World Vygeneruje graf typu Small World. Small world vznikne následujícím způsobem: nejprve je vytvořen torus řádu Torus order na number of vertices vrcholech. Torus řádu k je graf, kde je každý vrchol spojen s 2k nejbližšími vrcholy dle přirozeného očíslování.1 Ve druhé fázi je procentuální část (Random edge percentage) původních hran odebrána a nahrazena náhodně vedenými hranami.

Náhodný Graf – Random Graph Vygeneruje úplný graf s Vámi zvoleným počtem vrcholů, z něhož bude náhodně odebráno zvolené procento hran. Parametr Missing edge percentage udává, jaké množství hran má být vynecháno. Při volbě Missing edge percentage=0 bude vygenerován úplný graf na n vrcholech. Při volbě Missing edge percentage=10 nebude mít výsledný graf žádné hrany.

Krychle – Cubic Grid Vygeneruje krychlovou síť na Vertices in X-layer * Vertices in Y-layer * Vertices in Z-layer vrcholech, ze které bude náhodně odebráno zvolené procento hran. Parametr Missing edge percentage udává, jaké množství hran 1

Tedy torus řádu 1 je kružnice.


62

má být vynecháno. Při volbě Missing edge percentage=0 bude vygenerována úplná síť. Při volbě Missing edge percentage=10 nebude mít výsledný graf žádné hrany.

Čtvercová síť – Orthogonal Grid Vygeneruje čtvercovou síť na Vertices in X-layer * Vertices in Y-layer vrcholech, ze které bude náhodně odebráno zvolené procento hran. Parametr Missing edge percentage udává, jaké množství hran má být vynecháno. Při volbě Missing edge percentage=0 bude vygenerována úplná síť. Při volbě Missing edge percentage=10 nebude mít výsledný graf žádné hrany. Zatržením volby torus bude vygenerován topologický torus místo čtvercové sítě tedy síť, ve které byly horizontální a vertikální vnější hrany spojeny.

Zobecněný Petersenův Graf – Generalized Petersen Graph Vytvoří zobecněný Petersenův Graf GP (Number of Vertices in Outer Ring, Star Modus). Zobecněný Petersenův graf se skládá z vnější kružnice na Number of Vertices in Outer Ring vrcholech, která je spojena s vnitřní hvězdou na stejném počtu vrcholů. Vrcholy vnitřní hvězdy jsou spojeny hranou, pokud se liší jejich pořadí v přirozeném očíslování liší právě o Star Modus.

5.5

Draw2D – Kreslení grafů ve 2D

Random Layout – náhodné nakreslení Rozmístí vrcholy náhodně na plochu


63

Radial Layout – umístění vrcholů na kružnici Umístí vrcholy na kružnici. Parametr Radius in Pixels udává poloměr kružnice v pixelech.

Spring Layout – Nakreslení pomocí algoritmu KawadaKamai Nalezne nakreslení grafu pomocí algoritmu Kawada-Kamai, který je relativně pomalý a není vhodné ho použít pro grafy s více než 50 uzly. Prvním parametrem algoritmu je spring power - síla pružiny. Zvýšení spring power dosáhnete rychlejší konvergence algoritmu za cenu kvality výsledného nakreslení. Layout tolerance udává maximální energii potřebnou pro ukončení programu.

LPP Drawing – 2D nakreslení pomocí LPP Po vybrání této volby se objeví okno, které můžete vidět na obrázku 5.3. Parametr Center Count udává počet pivotů využitých k nalezení HDE. Vyšší hodnota může částečně vylepšit výsledné nakreslení, na druhou stranu vede k pomalejšímu běhu algoritmu. Pro většinu grafů je standardní hodnota 50 optimální. Parametry Eigenvalue for x-coordinate a Eigenvalue for y-coordinate udávají, která vlastní čísla mají být použita pro x-ovou respektive y-ovou souřadnici výsledného nakreslení. V některých případech je vhodné zaexperimentovat s nalezením správné volby těchto parametrů, neboť další vlastní čísla mohou odkrýt významné detaily grafu, ale pro většinu grafů je standardní nastavení vyhovující. Pokud zatrhnete volbu Weighted, bude uvažováno Vámi definované ohodnocení hran – viz část o editování hran. V opač-


64

ném případě budou všechny hrany uvažovány jako jednotkové. Po kliknutí na tlačítko OK, nalezne program nakreslení současného grafu pomocí algortimu LPP ve 2D.


Obrázek 5.3: Menu pro kreslení metodou LPP ve 2D.

65


66

PCA Drawing – 2D nakreslení pomocí PCA-projekce Po vybrání této volby se objeví okno, které můžete vidět na obrázku 5.4. Combobox Covariance Matrix Type udává, jakým způsobem má být získána kovariační matice. Pokud zvolíte High Dimensional, bude k nalezení kovariační matice použito vysoko-dimenzionální nakreslení grafu. Pokud zvolíte 3D Projection, je jako základ kovariační matici bráno současné 3-dimenzionální nakreslení. Parametr Center Count udává počet pivotů využitých k nalezení HDE. Vyšší hodnota může částečně vylepšit výsledné nakreslení, na druhou stranu vede k pomalejšímu běhu algoritmu. Pro většinu grafů je standardní hodnota 50 optimální. Parametry PC for x-coordinate a PC for y-coordinate udávají, které hlavní komponenty mají být použity pro x-ovou respektive y-ovou souřadnici výsledného nakreslení. V některých případech je vhodné zaexperimentovat s nalezením správné volby těchto parametrů, neboť další vlastní čísla mohou odhalit zajímavé struktury grafu, ale pro většinu aplikací je standardní nastavení vyhovující. Pokud zatrhnete volbu Weighted, bude uvažováno Vámi definované ohodnocení hran – viz část o editování hran. V opačném případě budou všechny hrany uvažovány jako jednotkové. Po kliknutí na tlačítko OK, nalezne program nakreslení současného grafu pomocí PCA-projekce ve 2D.


Obrázek 5.4: Menu pro kreslení metodou PCA ve 2D.

67


5.6

68

Draw3D – Kreslení grafů ve 3D

Orthogonal Grid Layout - 7 bends Nalezne ortogonální nakreslení grafu se 7 zlomy kompaktním algoritmem. Graf musí být souvislý a jeho maximální stupeň nesmí přesáhnout 6.

LPP Projection – 3D nakreslení pomocí LPP Po vybrání této volby se objeví okno, které můžete vidět na obrázku 5.5. Parametr Center Count udává počet pivotů využitých k nalezení HDE. Vyšší hodnota může částečně vylepšit výsledné nakreslení, na druhou stranu vede k pomalejšímu běhu algoritmu. Pro většinu grafů je standardní hodnota 50 optimální. Parametry Eigenvalue for x-coordinate, Eigenvalue for y-coordinate a Eigenvalue for z-coordinate udávají, která vlastní čísla mají být použita pro x-ovou,y-ovou a z-ovou souřadnici výsledného nakreslení. V některých případech je vhodné zaexperimentovat s nalezením správné volby těchto parametrů, neboť další vlastní čísla mohou odkrýt významné detaily grafu, ale pro většinu grafů je standardní nastavení vyhovující. Pokud zatrhnete volbu Weighted, bude uvažováno Vámi definované ohodnocení hran – viz část o editování hran. V opačném případě budou všechny hrany uvažovány jako jednotkové. Po kliknutí na tlačítko OK, nalezne program nakreslení současného grafu pomocí algortimu LPP ve 3D.


Obrázek 5.5: Menu pro kreslení metodou LPP ve 3D.

69


70

PCA Projection – 3D nakreslení pomocí PCA-projekce Po vybrání této volby se objeví okno, které můžete vidět na obrázku 5.6. Parametr Center Count udává počet pivotů využitých k nalezení HDE. Vyšší hodnota může částečně vylepšit výsledné nakreslení, na druhou stranu vede k pomalejšímu běhu algoritmu. Pro většinu grafů je standardní hodnota 50 optimální. Parametry PC for x-coordinate, PC for y-coordinate a PC for z-coordinate udávají, které hlavní komponenty mají být použity pro x-ovou,y-ovou respektive z-ovou souřadnici výsledného nakreslení. V některých případech je vhodné zaexperimentovat s nalezením správné volby těchto parametrů, neboť další komponenty mohou odhalit zajímavé struktury grafu, ale pro většinu aplikací je standardní nastavení vyhovující. Pokud zatrhnete volbu Weighted, bude uvažováno Vámi definované ohodnocení hran – viz část o editování hran. V opačném případě budou všechny hrany uvažovány jako jednotkové. Po kliknutí na tlačítko OK, nalezne program nakreslení současného grafu pomocí PCA-projekce ve 3D.


Obrázek 5.6: Menu pro kreslení pomocí PCA projekce ve 3D.

71


72

Force Embedding – 3D nakreslení pomocí fyzikálního modelu Nalezne nakreslení aktuálního grafu ve 3D pomocí Fruchterman-Reingoldova algoritmu, algoritmus se nehodí pro velké grafy s více než 200 vrcholy. Prvním parametrem je multiplikátor přitažlivé síly hran Hook Force Multiplier. Druhým parametrem je multiplikátor odpudivé síly mezi vrcholy Electrical Force Multiplier. Do pole number of iterations zadejte požadovaný počet iterací. Zatrhnete-li hodnotu Use current 3D position bude použito současné umístění vrcholů ve 3D jako iniciální konfigurace algoritmu. Toto nastavení lze využít pro vylepšení výsledků dosažených jinými algoritmy – například LPP projekcí. V opačném případě budou vrcholy nejprve rozmístěny náhodně v prostoru. Pokud zatrhnete volbu Generate 2D Projection bude výsledné nakreslení ve 3D převedeno do 2D pomocí algoritmu PCA. V záložce Advanced jsou další možnosti pro ovlivnění běhu algoritmu. Hodnota minimal energy to continue udává, za jaké minimální hodnoty energie dojde k předčasnému ukončení algoritmu, aniž by byl proveden požadovaný počet iterací. Hodnota damping in percent udává odpor prostředí. Je možné například nejprve použít nízkou hodnotu v kombinaci s velkým časovým intervalem mezi jednotlivými iteracemi – položka time elapsed between iterations – pro rychlé nalezení vhodné iniciální konfigurace. Následně pak použít takto nalezený mezivýsledek pro druhý běh algoritmu s vysokým odporem prostředí a minimálním časovým intervalem. Menu vidíte na obrázku ˜reffig:Forcemenu.


Obrázek 5.7: Menu nalezení nakreslení pomocí fyzikálního algoritmu.

73


5.7

74

Ovládání kamery a volba vykreslovacího režimu

Uprostřed na liště vidíte combobox označený Drawing style. Pomocí tohoto ovládacího prvku přepínáte mezi jednotlivými režimy kreslení. Pro editování grafu slouží 2D režim 2D Straight Line. Dále je k dispozici režim kreslení ve 3D rovnými čarami3D Straight Line a ortogonální kresleníOrto 3D, které Vám dávají plnou kontrolu nad kamerou. V režimu 3D a při ortogonálním kreslení máte plnou kontrolu nad úhlem pohledu na vykreslovaný graf. Pokud držíte levé tlačítko myši, můžete kamerou libovolně posunovat. Pro rotaci kamery přidržte pravé tlačítko myši. Pro přiblížení kamery držte obě tlačítka myši současně. V režimu 2D můžete posunovat graf pomocí šipek a kláves WASD. Stisknutím klávesy ’O’ oddálíte graf. Naopak stisknutím klávesy ’I’ přiblížíte graf.

5.8

Editace grafu

Pro editaci grafu zvolte režim vykreslování ve 2D. Pokud jste dosud graf nevykreslili v režimu 2D, zvolte libovolné nakreslení grafu ve 2D. Na liště vlevo vidíte čtyři tlačítka jako na obrázku 5.8. Pokud podržíte nad těmito tlačítky kurzor objeví se text nápovědy. Po stisknutí první ikony (Add Vertex) můžete přidávat vrcholy kliknutí levým tlačítkem na plochu hlavního okna. Pokud kliknete na existující vrchol objeví se menu, ve kterém můžete upravit vlastnosti daného vrcholu.


75

Obrázek 5.8: Tlačítka pro editaci grafu.

Editace vlastností vrcholu U vrcholů můžete v záložce Color měnit jejich barvu. Barva je zadávána ve formátu RGB. Zadáte-li (0, 0, 0), bude vrchol černý. Pokud zadáte (255, 255, 255), bude vrchol bílý. V záložce Position in 2D and Weight můžete upravit pozici vrcholu ve 2D a nastavit jeho ohodnocení, které je využito pro kreslení pomocí fyzikálních algoritmů ve 3D. Po stisknutí druhé ikony (Add Edge) můžete přidávat hrany mezi existujícími vrcholy. Klikněte na první vrchol levým tlačítkem a následně klikněte levým tlačítkem na koncový vrchol Vámi požadované hrany. Pokud mezi Vámi vybranými vrcholy hrana již existuje, objeví se okno pro editaci vlastností zvolené hrany.

Editace vlastností hran U hrany můžete měnit její barvu. Podobně jako u vrcholů je barva zadávána ve formátu RGB. Zadáte-li (0, 0, 0), bude hrana černá. Pokud zadáte (255, 255, 255), bude hrana bílá. Položka Weight slouží k nastavení ohodnocení hrany, které je využito pro kreslení pomocí fyzikálních algoritmů ve 3D i 2D, vážené PCA a LPP projekce. Po stisknutí třetí ikony (Remove Vertex) můžete odebírat vrcholy z existujího grafu kliknutím levým tlačítkem na vrchol, který si přejete odebrat. Poslední tlačítko (Remove Edge) slouží k odebírání hran z grafu. Postupujte stejně jako u přidávání hran. Nejprve zvolte první vrchol hrany levým


76

tlačítkem myši, následně zvolte koncový vrchol stejným způsobem.

5.9

Options

Po vybrání této položky se objeví okno, které vidíte na obrázku 5.9. Záložka Camera Options Vám umožňuje změnit rychlost rotace (rotation speed), posuvu (translation speed) a přibližování (zooming speed) kamery v režimu 3D vykreslování. Povolené hodnoty jsou mezi 1 (nejmenší) až 5 (největší). V záložce Drawing Options najdete volby zobrazení. Položka Resolution udává rozlišení okna programu. Položka Software Mode udává, zda bude probíhat renderování s hardwarovou akcelerací či v softwarovém modu. Další položkou je Fullscreen, která udává, zda bude aplikace spuštěna v celoobrazovkovém režimu. Předchozí tři nastavení se projeví až po restartování aplikace. Položka Show vertices in 3D udává, zda budou vrcholy vykresleny v režimu 3D vykreslování. Toto je velmi užitečné pro vykreslování velkých grafů kvůli zvýšení počtu snímků za sekundu.


Obrázek 5.9: Options.

77

Kapitola 6 Programová dokumentace Program byl implementován v C++ pro Win32 a odladěn v MS Visual Studiu 2005. Lze ho přeložit i překladačem gcc pod MinGW v prostředí Dev-Cpp verze beta 5.

6.1

Základní popis programu

Po spuštění aplikace je načten konfigurační soubor ”options.cfg” a na základě parametrů v něm obsažených je vytvořeno okno enginu Irrlicht [37]. Tomuto oknu je předána jako parametr třída pro zpracování událostí – v našem případě je to třída GUI MANAGER. GUI MANAGER následně reaguje na uživatelův vstup a provádí renderování výsledného nakreslení grafu. GUI MANAGER vlastní instanci třídy IrrGraph, která reprezentuje uživatelem právě editovaný graf. IrrGraph je adaptérem nad typem GeneticGraph. IrrGraph zapouzdřuje GeneticGraph a tvoří adaptační vrstvu mezi uživatelským rozhraním a vlastními grafovými algoritmy, které jsou prováděny právě nad typem GeneticGraph. 78

KAPITOLA 6. PROGRAMOVÁ DOKUMENTACE

79

GeneticGraph je instancí šablony seznamu sousedů (adjacency list [21]) z knihovny boost. Všechny dříve popsané algoritmy (PCA,LPP . . . ) jsou prováděny právě nad touto datovou strukturou. Nejrpve je GeneticGraph převeden na přechodnou strukturu vhodnou pro daný algoritmus. Následně je požadovaný algoritmus proveden a výsledek zapsán po synchronizaci do původního grafu. V případě, že uživatel požádá o nalezení nového nakreslení nebo jinou časově náročnou akci, vytvoří GUI MANAGER odpovídajícího potomka třídy thread caller. Abstraktní třída thread caller definuje statický void operator()(). Jeho definice je následující: zavolej virtuální funkci run(). Po ukončení funkce run nastav proměnnou informující hlavní vlákno o jeho výsledku. Pro samotné vytvoření vlákna je nejprve vytvořena instance potomka třídy thread caller, která je použita jako parametr konstruktoru třídy boost::thread. Boost::thread okopíruje výše uvedenou instanci a zavolá operator void()() okopírované instance jako nové vlákno. Potomci třídy thread caller tedy fungují jako komunikační kanál a mediátor mezi třídami IrrGraph a GUI MANAGER. Hlavní vlákno testuje, zda výpočetní vlákno stále běží. Když výpočetní vlákno ukončí činnost, hlavní vlákno znovu umožní editovat graf. Za běhu výpočetního vlákna není možné měnit aktuální graf, je však umožněno volně pohybovat kamerou. V každém bodu běhu programu mohou být spuštěna nejvýše dvě vlákna hlavní program a jedno vlákno pro provedení uživatelem požadované akce. Pokud bylo vytvořeno vlákno, čeká hlavní program na jeho ukončení a mezitím vykresluje scénu. Je třeba zajistit synchronizaci mezi hlavním vláknem a právě prováděným grafovým algoritmem pomocí synchronizačních primitiv. V našem případě se jedná o třídu boost::mutex, která zapouzdřuje funkcionalitu kritické sekce pro odlišné operační systémy.


80

Zapouzdření operací IO má na starosti třída IO unit. Vykreslování grafu je prováděnou třídou render unit. Základní programové schéma znázorňuje diagram. 6.1


Obrázek 6.1: Základní programové schéma.

81


6.2

82

Dokumentace API

Kompletní dokumentace API byla vygenerována v programu Doxygen a po instalaci programu se nachází v adresáři ./APIdoc.

6.3

Formát grafových a konfiguračních souborů

¨

GRAPHML Pro uložení vytvořených grafů na disk používá GraphDraw formát GRAPHML (Graph Markup Language) popsaný v [45]. GRAPHML je založen na formátu XML a umožňuje uchovávat data potřebná k vykreslení grafu, jako je pozice nebo barvu vrcholu. Nejprve je třeba vložit hlavičku označující formát dokumentu. Ta vypadá následovně:

83

KAPITOLA 6. PROGRAMOVÁ DOKUMENTACE Dále je třeba definovat graf. To provedeme následujícím způsobem:

Nyní je možno definovat atributy vrcholů a hran. V našem případě bude tato deklarace vypadat následujícím způsobem.

84


Vrchol grafu pak definujeme následovně:

<node id="n0"> 0 0


85

-3.690001 15.260775 13.988662 3.000000 3.000000 3.000000 255 255 255 1


<-- absolutní cesta k textuře je zadána v parametru path --> Hranu pak definujeme následovně: <edge id="e0_3" target="n0" source="n3"> 12.000000 12.000000 12.000000 12.000000 2.000000 12.000000 3.000000 2.000000 12.000000 3.000000 2.000000 3.000000 3.000000 3.000000 3.000000 255 255 255 1

86


87

Po definici hran a vrcholů soubor uzavřeme:

Nevýhodou tohoto formátu je velikost souborů, na druhou stranu poskytuje dobrou abstrakci a umožňuje uchovávát vzhled grafu.

Formáty GRA a SRC GraphDraw umí načíst grafové soubory ve formátu GRA a SRC. Formát GRA je definován následovně: Na prvním řádku je definován počet vrcholů a počet hran. Prázdné řádky jsou ignorovány. Každá následující neprázdná řádka je pak posloupnost pořadí vrcholů incidentních s vrcholem, který má pořadí shodné s počtem načtených neprázdných řádek. Vrcholy jsou číslovány od 1. Následující posloupnost popisuje graf C4 : 4 4 2 3 1 4 1 4 2 3 Formát SRC je definován následovně: První hodnota je libovolné číslo. Další dvě hodnoty udávají po řadě počet vrcholů a počet hran načítaného grafu.


88

Následují dvě libovolná čísla. Každý řádek je uvozen číslem, které představuje stupeň vrcholu. Následuje posloupnost vrcholů, které sousedí s aktualním vrcholem. Tentokrát jsou vrcholy číslovány od nuly. Formát opět demonstrujeme na příkladu grafu C4 : 0 4 4 0 000 2 1 2 2 0 3 2 0 3 2 1 2

Konfigurační soubor options.cfg Program načte na počátku běhu programu konfigurační soubor options.cfg. Jeho struktura je následovná SCREEN_HEIGHT 768 //výška obrazovky SCREEN_WIDTH 1024 //šířka obrazovky TRANS 1 // rychlost posuvu ve 3D mezi 1-5 ROT 3 //rychlost rotace ve 3D mezi 1-5 ZOOM 5 // rychlost zoomu ve 3D mezi 1-5 FULL_SCR 0 //celoobrazovkový režim SKIN 0 //typ skinu pro GUI mezi 0-3 SOFTWARE 0 // softwarový mod(1) nebo OPENGL SHOW_VERTEX 0 //zobrazit vrcholy ve 3D RED 255 //barva pozadí ve formátu RGB RED udává intenzitu červené barvy GREEN 255 //barva pozadí ve formátu RGB GREEN udává intenzitu zelené barvy BLUE 255 //barva pozadí ve formátu RGB BLUE udává intenzitu modré barvy


6.4

89

Použité knihovny

Irrlicht [37] Irrlicht je open-source 3D engine. Aplikace používá Irrlicht zejména pro vykreslování scény. Dále je na knihovně Irrlicht založeno GUI. Zatímco pro vykreslování grafu je Irrlicht velmi vhodným nástrojem díky kvalitní dokumentaci a prověřené implementaci rendereru, byla volba využití Irrlichtu pro GUI poněkud svazující. Funkce pro vytváření GUI jsou v Irrlichtu značně omezené (neexistuje např. dialog pro uložení souboru). Navíc jsme v průběhu vytváření GUI narazili na některé chyby v knihovně spojené zejména s třídou IGUIScrollBar. Finální implementace tedy nevyužívá ScrollBar, ale vlastní implementaci spinboxu. Dále je velmi omezený vizuální editor a celé GUI tedy bylo umísťováno přímo v kódu. Pro ukládání a parsování GRAPHML souborů je dále využit v Irrlichtu integrovaný XML parser, který je velmi rychlý a má srozumitelné rozhraní. Nejprve je třeba zkompilovat zdrojový kód knihovny. Pro kompilaci naší aplikace je třeba dále překladači zadat cestu ke hlavičkovým souborům Irrlichtu a linkeru nastavit cestu k souboru Irrlicht.dll. Podrobný postup je uveden na [38]. Soubor irrlicht1-3.zip na instalačním CD obsahuje úplnou distribuci Irrlichtu verze 1.3. Licenční ustanovení pro Irrlicht Engine jsou uvedena na [39].

Boost [40] Knihovny Boost jsou rozšířením standardní šablonové knihovny jazyka (STL) C++. Obsahují celou řadu základních algoritmů, které značně usnadňují vývoj aplikací. Naše aplikace extenzivně používá zejména grafovou knihovnu Boost::Graph[42] pro základní grafové algoritmy a knihovnu pro vytváření


90

vícevláknových aplikací Boost::Thread[43]. Dále je v menší míře využita maticová knihovna Boost::numeric::µblas a knihovna pro generování náhodných čísel Boost::Random. Boost::Graph je mocný a díky šablonám flexibilní nástroj pro manipulaci s grafy. Na druhou stranu je jeho flexibilita vykoupena poněkud zdlouhavým učebním procesem. Překladač totiž má často potíže s odvozením defaultních parametrů šablonových funkcí a je tedy nutné použít složitější varianty téže funkce s explicitně deklarovanými parametry, z nichž řada nemá vliv na vlastní běh algoritmu a slouží pouze jako pomocné proměnné. Navíc se zdá, že Boost::Graph je poměrně pomalý ve srovnání s optimalizovanými ad hoc řešeními. Mimo jiné je použito implementace algoritmu Kawada-Kamai a jako odlehčení jsou uživateli poskytnuty i kresby na základě algoritmu Gurson-Atuy implemntovaného knihovnou. Základní postup pro připojení zdrojových textů knihoven Boost je obdobný jako u Irrlichtu a je přesně zdokumentován na [44]. Licenční podmínky pro užití knihoven Boost jsou uvedeny na [41].Soubor boost 1 34 1.zip na instalačním CD obsahuje kompletní distribuci knihoven Boost verze 1 34 1.

ALGLIB [23] ALGLIB je soubor knihoven dostupných pro řadu programovacích jazyků zaměřený na numerické a statistické algoritmy. Naše aplikace využívá ALGLIB pro výpočet zobecněných vlastních čísel. Zdrojové kódy ALGLIBU jsou integrovány po instalaci umístěny v adresáři ./src/generalized eigenproblem.

6.5

Kompilace pod MS Visual Studio

Pokud chcete projekt zkompilovat musíte nejprve rozbalit archivy Irrlicht a boost v adresáři INSTALL, kam jste aplikaci nainstalovali. Absolutní


91

cestu do nově vzniklých adresářů budeme dále nazývat BOOST a IRRLICHT. V adresáři INSTALL/src se nachází zdrojové texty programu a soubor graph draw.vc proj. Otevřte tento projektový soubor ve Visual Studiu. Po načtení projektu vyberte v menu Project položku GraphDraw Properties. V seznamu Configuration Properties zvolte C/C++ a do položky Additional Include Directories zadejte následující text: "IRRLICHT\irrlicht\irrlicht-1.3\include"; "BOOST\boost\boost1_34_1" Následně zvolte položku Linker a do položky Additional Library Directories zadejte: "IRRLICHT\irrlicht\irrlicht-1.3\lib\Win32-visualstudio"; "BOOST\boost\boost1_34_1\lib" Nyní můžete projekt zkompilovat. Vyberte v menu Build položku Build Graph Draw.

6.6

Kompilace pod Dev-Cpp

Pokud chcete projekt zkompilovat musíte nejprve rozbalit archivy Irrlicht a boost v adresáři INSTALL, kam jste aplikaci nainstalovali. Absolutní cestu do nově vzniklých adresářů budeme dále nazývat BOOST a IRRLICHT. V adresáři INSTALL/src se nachází zdrojové texty programu a soubor graph draw. . Otevřte tento projektový soubor v DevCpp. Po načtení projektu vyberte v menu Projekt položku Projekt Options. V seznamu Configuration Properties. V záložce Library Directories zadejte následující text:


92

"IRRLICHT\irrlicht\irrlicht-1.3\lib"

"BOOST\boost\boost_1_34_1\bin.v2\libs\thread\build\gcc-mingw-3.4.2\release\threadi V záložce Additional Include Directories zadejte: "IRRLICHT\irrlicht\irrlicht-1.3\include" "BOOST\boost\boost1_34_1\lib" Nyní můžete projekt zkompilovat. Vyberte v menu Run položku Compile.

Pozor pro běh programu je třeba přejmenovat knihovnu Irrlichtg cc.dllnaIrrlicht.dll, nebojinakbypou

Kapitola 7 Závěr V práci jsme přiblížili řadu algoritmů pro kreslení grafů ve 2D a ve 3D. Popsali jsme fyzikální algoritmy založené na simulovaném žíhání a pružinovém modelu. Dále jsme implementovali dva algoritmy pro nalezení ortogonálního mřížkového nakreslení [3]. Dodejme, že otevřeným problémem zůstává, zda každý graf s maximálním stupněm 6 má 3DMNO, kde se každá hrana skládá nejvýše ze 3 segmentů [3]. V [36] bylo dokázáno, že graf K7 takové nakreslení má. Zobecnění tohoto tvrzení však dosud nebylo nalezeno. Demonstrovali jsme využití algoritmů pro redukci dimenze pro kreslení grafů na příkladu PCA-projekce. Popsali jsme také, jak nalézt vhodnou projekci nakreslení grafu z 3D do 2D pomocí PCA-projekce. Zejména jsme však prezentovali nový algoritmus pro kreslení rozsáhlých grafů s více než 10 000 uzly. Teoreticky i praktickou implementací jsme demonstrovali jeho lineární složitost a porovnali ji s ostatními současnými algoritmy. Naše výsledky ukazují, že nový algoritmus je ve srovnání s PCA projekcí o více než 50 procent rychlejší pro řídké grafy. Kvalita výsledných nakreslení je vysoká, zejména pokud se jedná o zobrazení globální symetrie. 93

KAPITOLA 7. ZÁVĚR

94

Pokud je zapotřebí nalézt perfektní lokální nakreslení, je vhodné kombinovat naši techniku s některým z fyzikálních algoritmů. Otevřená zůstává otázka, zda lze nalézt nejkratší cesty v grafu pro k zdrojových vrcholů rychleji než v čase O(k*Dijkstra). Nalezení takového algoritmu by vedlo ke zrychlení našeho algoritmu pro ohodnocené grafy. Další výzvou je bližší charakterizace prostorů generovaných metrikou HDE pro různé třídy grafů. Bylo by zajímavé provést detailní srovnání kvality výstupu našeho algoritmu s algoritmem uvedeným v [15]. Poznamenejme, že naši techniku lze využít k extrémně rychlému odhadu dominantních vlastních čísel libovolné matice. Nabízí se tedy podstatně širší aplikace než pouhé kreslení grafů, neboť vlastní čísla jsou využívána např. pro nalezení optimálního rozložení sil působících na mostní konstrukce. Další významnou aplikací algoritmů pro kreslení grafů ve 3D je rozklad meshí 3D modelů viz [48] a [47].

Seznam tabulek 2.1

Body mřížky, které nevyužívají dopředné hrany. . . . . . . .

2.2

Body mřížky využité hranami C1 u vrcholu uprostřed mřížky příslušného zpětné hraně. . . . . . . . . . . . . . . . . . . . .

2.3

17 17

Body mřížky využité hranami C1 u vrcholu na okraji mřížky příslušného zpětné hraně.

. . . . . . . . . . . . . . . . . . .

18

2.4

Vedení hran faktoru C2 viz [3]. . . . . . . . . . . . . . . . . .

18

4.1

Doba běhu algoritmu LPP pro čtvercové mřížky. . . . . . . .

49

4.2

Doba běhu algoritmu PCA pro čtvercové mřížky.

. . . . . .

49

4.3

Porovnání běhu algoritmů . . . . . . . . . . . . . . . . . . .

52

4.4

Doba běhu algoritmu PCA pro čtvercové mřížky.

52

95

. . . . . .

Seznam obrázků 2.1

Vedení hran ve faktoru C1 zdroj viz [3]. . . . . . . . . . . . .

16

2.2


19

2.3


22

2.4

Graf K7 nakreslený kompaktním algoritmem. . . . . . . . . .

24

2.5

Graf K7 nakreslený kubickým algoritmem. . . . . . . . . . .

25

2.6

Graf K7 nakreslený inkrementálním algoritmem . . . . . . .

26

3.1

Graf typu small world (100,4,5) nakreslený fyzikálním algoritmem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.2

Kružnice na 1000 vrcholech nakreslená fyzikálním algoritmem

34

4.1

Globální nakreslení grafu 4elt2 pomocí LPP.

. . . . . . . .

52

4.2

Globální nakreslení grafu 4elt2 pomocí PCA.

. . . . . . . .

52

4.3

Nakreslení grafu 4elt2 pomocí LPP ve 3D. . . . . . . . . . .

53

4.4

Graf big . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

4.5

Graf big . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

4.6

Graf 3elt . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

4.7

Graf 3elt . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

96

SEZNAM OBRÁZKŮ

97

4.8

Sierpinského hvězda hloubky 9 metodou LPP. . . . . . . . .

54

4.9

Graf airfoildual nakreslený metodou LPP. . . . . . . . . . .

55

4.10 Graf Finap512 metodou LPP – pomocí vlastních čísel 0, 1 a 2. 55 4.11 Graf crack nakreslený metodou LPP ve 3D. . . . . . . . . .

55

4.12 Mřížka 100 × 100 3D LPP-projekce. . . . . . . . . . . . . . .

56

4.13 Pohled do centra grafu sphere, LPP projekce ve 3D. . . . . .

56

4.14 Krychle 11 × 11 × 11 pomocí vlastních čísel 2, 3 a 4 metodou

LPP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

5.1

Dialog pro načtení souboru. . . . . . . . . . . . . . . . . . .

58

5.2

Dialog pro uložení souboru. . . . . . . . . . . . . . . . . . .

59

5.3

Menu pro kreslení metodou LPP ve 2D. . . . . . . . . . . . .

64

5.4

Menu pro kreslení metodou PCA ve 2D. . . . . . . . . . . .

66

5.5

Menu pro kreslení metodou LPP ve 3D. . . . . . . . . . . . .

68

5.6

Menu pro kreslení pomocí PCA projekce ve 3D. . . . . . . .

70

5.7

Menu nalezení nakreslení pomocí fyzikálního algoritmu. . . .

72

5.8

Tlačítka pro editaci grafu. . . . . . . . . . . . . . . . . . . .

74

5.9

Options. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

6.1

Základní programové schéma. . . . . . . . . . . . . . . . . .

80

Literatura [1] J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Nakladatelství Karolinum, 2003 [2] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985 [3] P. Eades, A. Symvonis, S. Whitesides, Three-dimensional orthogonal graph drawing algorithms, Discrete Applied Mathematics, č. 103, str. 55-87, 2000 [4] P. Hall, On representation of subsets, Journal of London Math Society, č. 10, str. 26-30, 1930 [5] K. M. Hall, An r-dimensional Quadratic Placement Algorithm, Management Science, č. 17, str. 219-229, 1970 [6] J. Edmonds, Paths, trees, and flowers, Canadian Journal of Mathematics, č. 17, str. 449-467, 1965 [7] A. Schrijver, Bipartite edge-coloring in O(maxdeg∗n), SIAM J. Comput., č. 28/3, str. 841-846, 1998 [8] R. Cohen, P. Eades, T. Lin, F. Ruskey et. al, Three diminsional drawing, Proceeding of 12th Annual ACM Symposium on Computational Geometry, Springer Verlag, str. 319-328, 1996 98

99

LITERATURA [9] A. Papakostas, Ioannis G. Tollis Incremental Orthogonal Graph ons,

dostupné

na

Drawing In Three Dimensi-

http://www.utdallas.edu/∼tollis-

/papers ortho.html, 1997 [10] Y. Koren, L. Carmel and D. Harel, ACE: A Fast Multiscale Eigenvector Computation for Drawing Huge Graphs, Proceedings of IEEE Information Visualization 2002 (InfoVis’02), IEEE, str. 137-144, 2002 [11] Y. Koren, Graph Drawing by Subspace Optimization, Proceedings of 6th Joint Eurographics - IEEE TCVG Symp. Visualization (VisSym ’04), Eurographics, str. 65-74, 2004 [12] D. Harel and Y. Koren, Graph Drawing by High-Dimensional Embedding, Proceedings of 10th Int. Symp. Graph Drawing (GD’02), Lecture Notes in Computer Science, Vol. 2528, Springer Verlag, str. 207-219, 2002 [13] M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, č. 34/3, str. 596-615, 1987 [14] E. W. Dijkstra, a note on two problems in connexion with graphs, Numerische Mathematik, č. 1, str. 269–271, 1959 [15] A. Civril, M. Magdon-Ismail and E. Bocek-Rivele, SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding, Proceedings of 14th Int. Symp. Graph Drawing (GD’06), 2006, str. 30-41 [16] Approximation Algorithms for NP-hard problems, Dorit S. Hochbaum, PWS Publishing, 1999

100

LITERATURA

[17] Pankaj K. Agarwal, Lecture notes on Geometric Optimization, dostupné

na

http://www.cs.duke.edu/courses/spring07-

/cps296.2/scribe notes/lecture14.pdf [18] X. He, P. Niyogi, Locality Preserving Projections, The University of Chicago, dostupné na http://www.cs.uchicago.edu/files/tr authentic/TR-2002-09.pdf [19] I. K. Fodor, A survey of Dimesionality Reduction Techniques, dostupné na

https://computation.llnl.gov/casc/sapphire-

/pubs/148494.pdf [20] K. Pearson, On Lines and Planes of Closest Fit to Systems of Points in Space, Philosophical Magazine 2 (6) : str. 559–572, 1901 [21] Boost Graph Library, Adjacency List Documentation, http://www.boost.org/doc/libs/1 34 1/libs/graph/doc/using adjacency list.html [22] The ALGLIB library – symmetric eigenvector problem, dostupné na http://www.alglib.net/eigen/symmetric/symmevd.php [23] The tor

ALGLIB

library

–

problem,

dostupné

generalized na

symmetric

eigenvec-

http://www.alglib.net/eigen/-

symmetric/generalizedsymmevd.php [24] W. T. Tutte, How to draw a graph, Proceedings of London Mathematical Society, č. 13, str. 743-768, 1963 [25] P. Eades and P. Garvan, Drawing stressed planar graphs in three dimensions, Proceedings of the 3rd Symposium on Graph Drawing, str. 212-223, 1995

101

LITERATURA

[26] T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs, Information Processing Letters,č. 31, 1989, str. 8-19 [27] R.W. Floyd, Algorithm 97: Shortest Path, Communications of the ACM, 1962 [28] Aaron J. Quigley and Peter Eades, FADE: Graph Drawing, Clustering and Visual Abstraction, Proceedings of Graph Drawing, 2000 [29] J.

Felcman,

Skripta

z

numerické

matematiky,

dostupné

na http://www.karlin.mff.cuni.cz/∼felcman/nm.pdf [30] W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes in C++: Scientific Art of Computing, Cambridge University Press, 2007 [31] P. Eades, A heuristic for graph drawing, Congressus Numerantium, č. 42, str. 149-160, 1984. [32] S. Keith, Mechanics, Addison-Wesley, 1971 [33] D.J. Griffiths, Introduction to Electrodynamics, Prentice Hall, 1998 [34] C.

Lanius,

The

Sierpinski

Fractal,

dostupné

na

http://math.rice.edu/∼lanius/fractals/ [35] T. Fruchterman and E. Reingold, Graph drawing by force-directed placement, Software- Practice and Experience, č. 11, str. 1129-1164, 1991 [36] D. Wood, On higher-dimensional orthogonal graph drawing, Proceedings of CATS’97, Computing: The Australasian Theory Symposium, str. 3-8, 1997

102

LITERATURA [37] The Irrlicht Engine Homepage http://irrlicht.sourceforge.net/ [38] The Irrlicht Engine Hello World Tutorial http://irrlicht.sourceforge.net/tut001.html [39] Irrlicht Engine License http://irrlicht.sourceforge.net/license.html [40] Boost libraries homepage http://www.boost.org/

[41] Boost Library License, http://www.boost.org/LICENSE 1 0.txt [42] Documentation of the Boost::Graph Library http://www.boost.org/doc/libs/1 34 1/libs/graph/doc/index.html [43] Documentation of the Boost::Thread Library http://www.boost.org/doc/libs/1 34 1/doc/html/thread.html [44] Boost Instalation Guide http://www.boost.org/doc/libs/1 34 1/more/getting started/index.html [45] U. Brandes,M. Eiglsperger and J. Lerner, GRAPHML Primer http://graphml.graphdrawing.org/primer/graphml-primer.html [46] University

of

Paderborn,

Graph

Collection,

http://wwwcs.uni-paderborn.de/fachbereich/AG/monien/RESEARCH/PART/graphs.htm [47] C. Walshaw, University of Greenwitch Partitioning Archive, http://staffweb.cms.gre.ac.uk/∼wc06/partition/ [48] http://www-unix.mcs.anl.gov/sumaa3d/PARS/partition.html ¨

Obsah CD • graph draw.exe – zde popsaný program • bp.pdf,bp.ps – text této práce¨ • user.pdf, user.ps – uživatelská dokumentace • ./src – zdrojové texty – ./boost.zip – knihovna boost – ./irrlicht.zip – knihovna Irrlicht – ./generalisede igen−−knihovnaALGLIBIrrlichtg cc.dll−−knihovnaIrrlichtprogcc – • graphs – testovací soubory • icons – ikony nutné pro běh programu

103

BAKALÁŘSKÁ PRÁCE. Jakub Kratochvíl. Kreslení grafů

Recommend Documents