Kreslení grafu - Graph drawing

Kreslení grafu je oblast matematika a počítačová věda kombinující metody z teorie geometrických grafů a informační vizualizace odvodit dvojrozměrné zobrazení grafy vyplývající z aplikací, jako je analýza sociálních sítí, kartografie, lingvistika, a bioinformatika.[1]
Výkres grafu nebo síťový diagram je obrazové znázornění vrcholy a hrany grafu. Tuto kresbu nelze zaměňovat se samotným grafem: stejnému grafu mohou odpovídat velmi různá rozvržení.[2] V abstraktu záleží jen na tom, které páry vrcholů jsou spojeny hranami. V betonu však uspořádání těchto vrcholů a hran ve výkresu ovlivňuje jeho srozumitelnost, použitelnost, výrobní náklady a estetika.[3] Problém se zhoršuje, pokud se graf v průběhu času mění přidáváním a mazáním okrajů (dynamické kreslení grafu) a cílem je zachovat mentální mapu uživatele.[4]
Grafické konvence

Grafy jsou často vykreslovány jako diagramy uzlů a odkazů, ve kterých jsou vrcholy reprezentovány jako disky, pole nebo textové štítky a hrany jsou reprezentovány jako úsečky, křivky, nebo křivky v Euklidovské letadlo.[3] Schémata uzlů a odkazů lze vysledovat až k dílům Pseudo-Lull ze 14. – 16. Století, která byla publikována pod názvem Ramon Llull, polymath ze 13. století. Pseudo-Lull nakreslil diagramy tohoto typu pro kompletní grafy aby bylo možné analyzovat všechny párové kombinace mezi sadami metafyzických konceptů.[5]
V případě řízené grafy, hroty šípů tvoří běžně používanou grafickou konvenci orientace;[2] uživatelské studie však ukázaly, že jiné konvence, jako je tapering, poskytují tyto informace efektivněji.[6] Nahoru planární kresba používá konvenci, že každá hrana je orientována od spodního vrcholu k vyššímu, což činí šipky zbytečnými.[7]
Alternativní konvence k diagramům uzlů a spojů zahrnují reprezentace sousedství, například kruhové obaly, ve kterém jsou vrcholy reprezentovány nesouvislými oblastmi v rovině a hrany jsou reprezentovány sousednostmi mezi oblastmi; křižovatkové reprezentace ve kterých jsou vrcholy reprezentovány neodpojenými geometrickými objekty a hrany jsou reprezentovány jejich průsečíky; reprezentace viditelnosti, ve kterých jsou vrcholy reprezentovány oblastmi v rovině a hrany jsou reprezentovány oblastmi, které mají vzájemně volný výhled; soutokové kresby, ve kterých jsou hrany v rámci matematiky reprezentovány jako hladké křivky kolejnice; textilie, ve kterých jsou uzly reprezentovány jako vodorovné čáry a hrany jako svislé čáry;[8] a vizualizace matice sousedství grafu.
Opatření kvality
Pro výkresy grafů bylo definováno mnoho různých měřítek kvality ve snaze najít objektivní prostředky k vyhodnocení jejich estetiky a použitelnosti.[9] Kromě vedení výběru mezi různými metodami rozložení pro stejný graf se některé metody rozložení pokusí přímo optimalizovat tato měřítka.

- The číslo křížení výkresu je počet párů hran, které se navzájem protínají. Pokud je graf rovinný, pak je často vhodné ho nakreslit bez průsečíků hran; to je, v tomto případě, kreslení grafu představuje a vkládání grafů. V aplikacích však často vznikají neplanární grafy, takže algoritmy kreslení grafů musí obecně umožňovat křížení hran.[10]
- The plocha výkresu je velikost jeho nejmenšího ohraničující rámeček relativní k nejbližší vzdálenosti mezi dvěma vrcholy. Kresby s menší plochou jsou obecně výhodnější než kresby s větší plochou, protože umožňují zobrazit rysy kresby ve větší velikosti a tedy čitelněji. The poměr stran může být také důležité ohraničující rámeček.
- Hledání symetrie je problém skupiny symetrie v daném grafu a nalezení výkresu, který zobrazuje co nejvíce symetrie. Některé metody rozvržení automaticky vedou k symetrickým výkresům; Alternativně některé metody kreslení začínají hledáním symetrií ve vstupním grafu a jejich použitím k vytvoření výkresu.[11]
- Je důležité, aby hrany měly co nejjednodušší tvary, aby je oko snáze sledovalo. Ve výkresech křivky lze složitost hrany měřit pomocí počet zatáček, a mnoho metod má za cíl poskytnout výkresy s několika celkovými ohyby nebo několika ohyby na hranu. Podobně u křivek spline lze složitost hrany měřit počtem řídicích bodů na hraně.
- Několik běžně používaných opatření kvality se týká délek okrajů: je obecně žádoucí minimalizovat celkovou délku okrajů i maximální délku kteréhokoli okraje. Kromě toho může být výhodné, aby délky okrajů byly spíše jednotné než velmi rozmanité.
- Úhlové rozlišení je míra nejostřejších úhlů ve výkresu grafu. Pokud má graf vrcholy s vysokými stupeň pak nutně bude mít malé úhlové rozlišení, ale úhlové rozlišení může být omezeno níže funkcí stupně.[12]
- The číslo svahu grafu je minimální počet zřetelných sklonů okrajů potřebných ve výkresu s hranami přímých segmentů (umožňujícími křížení). Krychlové grafy mít číslo svahu nejvýše čtyři, ale grafy stupně pět mohou mít neomezené číslo sklonu; zůstává otevřené, zda je počet sklonů grafů stupně 4 ohraničen.[12]
Metody rozložení

Existuje mnoho různých strategií rozložení grafů:
- v rozložení na základě síly systémy, software pro kreslení grafů upravuje počáteční umístění vrcholů kontinuálním pohybem vrcholů podle systému sil na základě fyzických metafor souvisejících se systémy pružiny nebo molekulární mechanika. Tyto systémy obvykle kombinují přitažlivé síly mezi sousedními vrcholy s odpudivými silami mezi všemi dvojicemi vrcholů, aby hledaly rozložení, ve kterém jsou délky hran malé, zatímco vrcholy jsou dobře oddělené. Tyto systémy mohou fungovat klesání založená minimalizace energetická funkce, nebo mohou převést síly přímo na rychlosti nebo zrychlení pro pohybující se vrcholy.[14]
- Spektrální rozložení metody používají jako souřadnice vlastní vektory a matice tak jako Laplacian odvozeno z matice sousedství grafu.[15]
- Metody ortogonálního rozložení, které umožňují, aby okraje grafu probíhaly vodorovně nebo svisle, rovnoběžně s koordinačními osami rozložení. Tyto metody byly původně navrženy pro VLSI a PCB problémy s rozvržením, ale byly také upraveny pro kreslení grafů. Obvykle zahrnují vícefázový přístup, ve kterém je vstupní graf planární nahrazením křížových bodů vrcholy, je nalezeno topologické zakotvení rovinného grafu, jsou vybrány orientace hran, aby se minimalizovaly ohyby, vrcholy jsou umístěny konzistentně s těmito orientacemi a nakonec rozložení fáze zhutnění zmenšuje plochu výkresu.[16]
- Algoritmy rozložení stromu, které ukazují zakořeněné strom -jako formace, vhodná pro stromy. V technice zvané „rozložení balónku“ jsou děti každého uzlu stromu často nakresleny na kruh obklopující uzel, přičemž poloměry těchto kruhů se zmenšují na nižších úrovních stromu, aby se tyto kruhy nepřekrývaly.[17]
- Vrstvený graf kreslení metody (často nazývané kresba ve stylu Sugiyama) jsou nejvhodnější směrované acyklické grafy nebo grafy, které jsou téměř acyklické, například grafy závislostí mezi moduly nebo funkcemi v softwarovém systému. V těchto metodách jsou uzly grafu uspořádány do vodorovných vrstev pomocí metod, jako je Coffman – Grahamův algoritmus, takovým způsobem, že většina hran jde dolů z jedné vrstvy do další; po tomto kroku jsou uzly v každé vrstvě uspořádány, aby se minimalizovalo křížení.[18]

- Obloukové diagramy, styl rozvržení sahající až do 60. let,[19] umístěte vrcholy na čáru; hrany mohou být nakresleny jako půlkruhy nad nebo pod čarou nebo jako hladké křivky spojené z více půlkruhů.
- Kruhové rozložení metody umisťují vrcholy grafu na kružnici a pečlivě volí řazení vrcholů kolem kružnice, aby se zmenšily přechody a umístily sousední vrcholy blízko sebe. Okraje mohou být nakresleny buď jako akordy kruhu, nebo jako oblouky uvnitř nebo vně kruhu. V některých případech lze použít více kruhů.[20]
- Kresba dominance umisťuje vrcholy takovým způsobem, že jeden vrchol je nahoru, doprava nebo oba jiný, právě když je dosažitelný z druhého vrcholu. Tímto způsobem styl rozložení vizuálně ukazuje vztah dosažitelnosti grafu.[21]
Aplikačně specifické výkresy grafů
Mezi ně patří grafy a výkresy grafů vznikající v jiných oblastech aplikace
- Sociogramy, kresby a sociální síť, jak často nabízí software pro analýzu sociálních sítí[22]
- Hasse diagramy, typ grafu, který se specializuje na dílčí objednávky[23]
- Dessin d'enfants, typ grafu použitého v algebraická geometrie[24]
- Stavové diagramy, grafická znázornění stroje konečného stavu[25]
- Počítačové síťové diagramy, vyobrazení uzlů a spojení v a počítačová síť[26]
- Vývojové diagramy a drakon-mapy, kresby, ve kterých uzly představují kroky an algoritmus a hrany představují regulační tok mezi kroky.
- Diagramy toku dat, výkresy, ve kterých uzly představují součásti souboru informační systém a hrany představují pohyb informací z jedné složky do druhé.
- Bioinformatika počítaje v to fylogenetické stromy, interakce protein-protein sítě a metabolické cesty.[27]
Kromě toho umístění a směrování kroky automatizace elektronického designu (EDA) jsou v mnoha ohledech podobné grafickému kreslení, stejně jako problém chamtivé vkládání v distribuované výpočty a literatura pro kreslení grafů obsahuje několik výsledků vypůjčených z literatury EDA. Tyto problémy se však také liší několika důležitými způsoby: například v EDA je minimalizace oblasti a délka signálu důležitější než estetika a problém směrování v EDA může mít více než dva terminály na síť, zatímco analogický problém v obecném kreslení grafů zahrnuje pouze páry vrcholů pro každou hranu.
Software

Software, systémy a poskytovatelé systémů pro kreslení grafů zahrnují:
- BioFabric open-source software pro vizualizaci velkých sítí nakreslením uzlů jako vodorovných čar.
- Cytoscape, open-source software pro vizualizaci sítí molekulárních interakcí
- Gephi, open-source software pro analýzu a vizualizaci sítě
- grafický nástroj, a zdarma / zdarma Krajta knihovna pro analýzu grafů.
- Graphviz, open-source systém pro kreslení grafů z AT&T Corporation[28]
- Odkazující, komerční software pro analýzu a vizualizaci sítě pro databáze grafů
- Mathematica, obecný výpočetní nástroj, který zahrnuje nástroje pro vizualizaci 2D a 3D grafů a nástroje pro analýzu grafů.[29][30]
- Automatické rozložení grafu Microsoft, open-source knihovna .NET (dříve GLEE) pro rozložení grafů[31]
- NetworkX je knihovna v Pythonu pro studium grafů a sítí.
- Software Tom Sawyer[32] Tom Sawyer Perspectives je grafický software pro vytváření podnikových grafů a vizualizačních a analytických aplikací. Jedná se o Software Development Kit (SDK) s grafickým designem a náhledem prostředí.
- Tulipán (software),[33] nástroj pro vizualizaci dat s otevřeným zdrojovým kódem
- yEd, editor grafů s funkcí rozložení grafů[34]
- PGF / TikZ 3.0 s
kreslení grafů
balíček (vyžaduje LuaTeX ).[35] - LaNet-vi, software pro vizualizaci velké sítě typu open-source
- Edraw Max Software pro 2D technické technické plánování
Reference
- Poznámky pod čarou
- ^ Di Battista a kol. (1994), str. vii – viii; Herman, Melançon a Marshall (2000), Oddíl 1.1, „Typické oblasti použití“.
- ^ A b Di Battista a kol. (1994), str. 6.
- ^ A b Di Battista a kol. (1994), str. viii.
- ^ Misue a kol. (1995)
- ^ Knuth, Donald E. (2013), „Dva tisíce let kombinatoriky“, Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern„Oxford University Press, s. 7–37.
- ^ Holten & van Wijk (2009); Holten a kol. (2011).
- ^ Garg & Tamassia (1995).
- ^ Longabaugh (2012).
- ^ Di Battista a kol. (1994), Sekce 2.1.2, Estetika, s. 14–16; Nákup, Cohen & James (1997).
- ^ Di Battista a kol. (1994), s. 14.
- ^ Di Battista a kol. (1994), str. 16.
- ^ A b Pach & Sharir (2009).
- ^ Publikoval v Grandjean, Martin (2014). „La connaissance est un réseau“. Les Cahiers du Numérique. 10 (3): 37–54. doi:10.3166 / lcn.10.3.37-54. Citováno 2014-10-15.
- ^ Di Battista a kol. (1994), Oddíl 2.7, „Přístup zaměřený na sílu“, s. 29–30, a Kapitola 10, „Síla zaměřené metody“, s. 303–326.
- ^ Beckman (1994); Koren (2005).
- ^ Di Battista a kol. (1994), Kapitola 5, „Průtokové a ortogonální kresby“, s. 137–170; (Eiglsperger, Fekete & Klau 2001 ).
- ^ Herman, Melançon a Marshall (2000), Oddíl 2.2, „Tradiční rozložení - přehled“.
- ^ Sugiyama, Tagawa a Toda (1981); Bastert & Matuszewski (2001); Di Battista a kol. (1994), Kapitola 9, „Vrstvené kresby digrafů“, s. 265–302.
- ^ Saaty (1964).
- ^ Doğrusöz, Madden & Madden (1997).
- ^ Di Battista a kol. (1994), Sekce 4.7, „Kresby dominance“, s. 112–127.
- ^ Scott (2000); Brandes, Freeman & Wagner (2014).
- ^ Di Battista a kol. (1994), s. 15–16 a Kapitola 6, „Tok a vzestupná rovinnost“, s. 171–214; Freese (2004).
- ^ Zapponi (2003).
- ^ Anderson & Head (2006).
- ^ Di Battista & Rimondini (2014).
- ^ Bachmaier, Brandes & Schreiber (2014).
- ^ „Graphviz a Dynagraph - statické a dynamické nástroje pro kreslení grafů“, John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North a Gordon Woodhull, v Jünger & Mutzel (2004).
- ^ GraphPlot Dokumentace Mathematica
- ^ Výukový program pro kreslení grafů
- ^ Nachmanson, Robertson & Lee (2008).
- ^ Madden a kol. (1996).
- ^ "Tulipán - obrovský rámec pro vizualizaci grafů", David Auber, v Jünger & Mutzel (2004).
- ^ „yFiles - Vizualizace a automatické rozložení grafů“, autori: Roland Wiese, Markus Eiglsperger a Michael Kaufmann, v Jünger & Mutzel (2004).
- ^ Tantau (2013); viz také starší Prezentace GD 2012
- Obecné odkazy
- Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1994), „Algoritmy pro kreslení grafů: anotovaná bibliografie“, Výpočetní geometrie: Teorie a aplikace, 4 (5): 235–282, doi:10.1016 / 0925-7721 (94) 00014-x.
- Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Kreslení grafu: Algoritmy pro vizualizaci grafů, Prentice Hall, ISBN 978-0-13-301615-4.
- Herman, Ivan; Melançon, Guy; Marshall, M. Scott (2000), „Vizualizace grafů a navigace ve vizualizaci informací: průzkum“, Transakce IEEE na vizualizaci a počítačové grafice, 6 (1): 24–43, doi:10.1109/2945.841119.
- Jünger, Michael; Mutzel, Petra (2004), Software pro kreslení grafů, Springer-Verlag, ISBN 978-3-540-00881-1.
- Kaufmann, Michael; Wagner, Dorothea, eds. (2001), Kreslení grafů: Metody a modely, Přednášky z informatiky, 2025, Springer-Verlag, doi:10.1007/3-540-44969-8, ISBN 978-3-540-42062-0, S2CID 1808286.
- Tamassia, Roberto, vyd. (2014), Příručka kreslení a vizualizace grafů, CRC Press, archivováno z originál dne 15. 8. 2013, vyvoláno 2013-08-28.
- Specializované podtémata
- Anderson, James Andrew; Head, Thomas J. (2006), Teorie automatů s moderními aplikacemi, Cambridge University Press, s. 38–41, ISBN 978-0-521-84887-9.
- Bachmaier, Christian; Brandes, Ulrik; Schreiber, Falk (2014), „Biological Networks“, in Tamassia, Roberto (vyd.), Příručka kreslení a vizualizace grafů, CRC Press, str. 621–651.
- Bastert, Oliver; Matuszewski, Christian (2001), „Vrstvené kresby digrafů“, Kaufmann, Michael; Wagner, Dorothea (eds.), Kreslení grafů: Metody a modely, Přednášky v informatice, 2025, Springer-Verlag, str. 87–120, doi:10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0.
- Beckman, Brian (1994), Teorie rozložení spektrálního grafu, Tech. Zpráva MSR-TR-94-04, Microsoft Research.
- Brandes, Ulrik; Freeman, Linton C .; Wagner, Dorothea (2014), „Social Networks“, in Tamassia, Roberto (vyd.), Příručka kreslení a vizualizace grafů, CRC Press, str. 805–839.
- Di Battista, Giuseppe; Rimondini, Massimo (2014), „Computer Networks“, in Tamassia, Roberto (vyd.), Příručka kreslení a vizualizace grafů, CRC Press, str. 763–803.
- Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), „Circular layout in the Graph Layout toolkit“, North, Stephen (ed.), Symposium on Graph Drawing, GD '96 Berkeley, Kalifornie, USA, 18. – 20. Září 1996, sborník, Přednášky v informatice, 1190, Springer-Verlag, str. 92–100, doi:10.1007/3-540-62495-3_40, ISBN 978-3-540-62495-0.
- Eiglsperger, Markus; Fekete, Sándor; Klau, Gunnar (2001), „Orthogonal graph drawing“, v Kaufmann, Michael; Wagner, Dorothea (eds.), Kreslení grafů, Přednášky v informatice, 2025, Springer Berlin / Heidelberg, str. 121–171, doi:10.1007/3-540-44969-8_6, ISBN 978-3-540-42062-0.
- Freese, Ralph (2004), „Automated lattice drawing“, v Eklund, Peter (ed.), Concept Lattices: Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, 23-26 February, 2004, Proceedings (PDF), Přednášky v informatice, 2961, Springer-Verlag, str. 589–590, CiteSeerX 10.1.1.69.6245, doi:10.1007/978-3-540-24651-0_12, ISBN 978-3-540-21043-6.
- Garg, Ashim; Tamassia, Roberto (1995), „Vzestupné testování rovinnosti“, Objednat, 12 (2): 109–133, CiteSeerX 10.1.1.10.2237, doi:10.1007 / BF01108622, PAN 1354797, S2CID 14183717.
- Holten, Danny; Isenberg, Petra; van Wijk, Jarke J.; Fekete, Jean-Daniel (2011), „Rozšířené vyhodnocení čitelnosti zúžené, animované a texturované reprezentace s přímým okrajem v grafech uzlových odkazů“, IEEE Pacific Visualization Symposium (PacificVis 2011) (PDF), str. 195–202, doi:10.1109 / PACIFICVIS.2011.5742390, ISBN 978-1-61284-935-5, S2CID 16526781.
- Holten, Danny; van Wijk, Jarke J. (2009), „Uživatelská studie o vizualizaci směrovaných hran v grafech“, Sborník 27. mezinárodní konference o lidských faktorech ve výpočetních systémech (CHI '09) (PDF), str. 2299–2308, CiteSeerX 10.1.1.212.5461, doi:10.1145/1518701.1519054, ISBN 9781605582467, S2CID 9725345, archivovány z originál (PDF) dne 06.11.2011.
- Koren, Jehuda (2005), „Kreslení grafů vlastními vektory: teorie a praxe“ (PDF), Počítače a matematika s aplikacemi, 49 (11–12): 1867–1888, doi:10.1016 / j.camwa.2004.08.015, PAN 2154691, archivovány z originál (PDF) dne 02.04.2012, vyvoláno 2011-09-17.
- Longabaugh, William (2012), „Kombinace hairball s BioFabric: nový přístup k vizualizaci velkých sítí“ (PDF), BMC bioinformatika, 13: 275, doi:10.1186/1471-2105-13-275, PMC 3574047, PMID 23102059.
- Madden, Brendan; Madden, Patrick; Powers, Steve; Himsolt, Michael (1996), „Přenosné rozložení a úpravy grafů“, Brandenburg, Franz J. (ed.), Grafická kresba: Symposium on Graph Drawing, GD '95, Passau, Německo, 20. – 22. Září 1995, sborník, Přednášky v informatice, 1027, Springer-Verlag, str. 385–395, doi:10.1007 / BFb0021822, ISBN 978-3-540-60723-6.
- Misue, K .; Eades, P .; Lai, W .; Sugiyama, K. (1995), „Layout Adjustment and the Mental Map“, Journal of Visual Languages & Computing, 6 (2): 183–210, doi:10.1006 / jvlc.1995.1010.
- Nachmanson, Lev; Robertson, George; Lee, Bongshin (2008), „Kreslení grafů pomocí GLEE“ (PDF), v Hong, Seok-Hee; Nišizeki, Takao; Quan, Wu (eds.), Grafická kresba, 15. mezinárodní sympozium, GD 2007, Sydney, Austrálie, 24. – 26. Září 2007, revidované práce, Přednášky v informatice, 4875, Springer-Verlag, str. 389–394, doi:10.1007/978-3-540-77537-9_38, ISBN 978-3-540-77536-2.
- Pach, János; Sharir, Micha (2009), „5.5 Úhlové rozlišení a sklony“, Kombinatorická geometrie a její algoritmické aplikace: Alcalá přednáškyMatematické průzkumy a monografie 152, Americká matematická společnost, str. 126–127.
- Nákup, H. C.; Cohen, R. F .; James, M. I. (1997), „Experimentální studie základu pro algoritmy kreslení grafů“ (PDF), Journal of Experimental Algorithmics, 2, Článek 4, doi:10.1145/264216.264222, S2CID 22076200[trvalý mrtvý odkaz ].
- Saaty, Thomas L. (1964), „Minimální počet křižovatek v celých grafech“, Proc. Natl. Acad. Sci. USA, 52 (3): 688–690, doi:10.1073 / pnas.52.3.688, PMC 300329, PMID 16591215.
- Scott, John (2000), „Sociogramy a teorie grafů“, Analýza sociálních sítí: příručka (2. vyd.), Sage, str. 64–69, ISBN 978-0-7619-6339-4.
- Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), „Metody vizuálního porozumění strukturám hierarchického systému“, Transakce IEEE na systémech, člověku a kybernetice, SMC-11 (2): 109–125, doi:10.1109 / TSMC.1981.4308636, PAN 0611436, S2CID 8367756.
- Tantau, Till (2013), „Graph Drawing in TikZ“, Journal of Graph Algorithms and Applications, 17 (4): 495–513, doi:10,7155 / jgaa.00301.
- Zapponi, Leonardo (srpen 2003), „Co je to Dessin d'Enfant“ (PDF), Oznámení Americké matematické společnosti, 50: 788–789.
externí odkazy
- Knihovna GraphX pro .NET: open-source knihovna WPF pro výpočet a vizualizaci grafů. Podporuje mnoho algoritmů rozložení a směrování hran.
- Archiv e-tisku grafů: včetně informací o příspěvcích od všech Symposia pro kreslení grafů.
- Kreslení grafu na Curlie pro mnoho dalších odkazů týkajících se kreslení grafů.