Kreslení vrstveného grafu

Kreslení grafu vrstev nebo kreslení hierarchického grafu je metoda vizualizace grafu , při které se vrcholy orientovaného grafu kreslí ve vodorovných řadách nebo vrstvách s hranami převážně směřujícími dolů [1] [2] [3] . Toto je známé jako Sugiyama styl vizualizace grafů , po Kozo Sugiyama, který jako první vyvinul tento styl [4] .

Ideální formou vrstvené kresby by byla rovinná kresba směrem nahoru , ve které jsou všechny hrany orientovány stejným směrem a žádná dvojice hran se neprotíná. Grafy však často obsahují cykly a problém s minimalizací počtu hran směřujících opačným směrem je NP-těžký , stejně jako problém s minimalizací počtu průsečíků. Z tohoto důvodu systémy vykreslování vrstvených grafů obvykle používají posloupnost heuristických přístupů, které redukují tyto typy chyb a najdou vzorek s nejmenším počtem chyb.

Algoritmus rozložení

Konstrukce vizualizace grafů vrstva po vrstvě probíhá v několika fázích:

Implementace

Ve své nejjednodušší podobě mohou algoritmy vykreslování vrstvených grafů trvat O( mn ) čas na grafech s n vrcholy a m hranami, protože lze vytvořit velké množství dalších vrcholů. U některých variant algoritmu je však možné simulovat vliv dalších vrcholů bez jejich skutečného přidávání, což vede k implementaci algoritmu s téměř lineární dobou provádění [18] .

Popisný jazyk "DOT" v balíčku Graphviz vytváří vrstvené reprezentace [9] . Algoritmus vizualizace vrstvených grafů je také zahrnut v knihovně automatického rozložení grafů společnosti Microsoft [19] a v rámci Tulip [ [20] .

Variace

Ačkoli se kreslení obvykle provádí s vrcholy v řadách as hranami jdoucími shora dolů, algoritmy vykreslování vrstvených grafů mohou místo toho uspořádat vrcholy svisle do sloupců a kreslit hrany zleva doprava [21] . Stejný rámec může využívat radiální uspořádání, kde jsou vrcholy umístěny na soustředných kružnicích (vystředěných v nějakém počátečním uzlu) [3] [22] , stejně jako 3D vrstvení grafů [3] [23] .

Při vizualizaci grafů po vrstvách s velkým počtem dlouhých oblouků lze chaos snížit seskupením sad hran do svazků a jejich nasměrováním přes stejnou sadu dalších vrcholů [24] . Podobně, aby bylo možné nakreslit mnoho protínajících se hran mezi páry po sobě jdoucích vrstev, mohou být hrany v maximálních bipartitních podgrafech seskupeny do splývajících paketů [25] .

Obrazce, ve kterých jsou vrcholy uspořádány ve vrstvách, lze konstruovat pomocí algoritmů, které se neřídí Sugiyamovým schématem. Například lze říci, zda neorientovaný graf má reprezentaci s nejvýše k průsečíky a h vrstvami v polynomiálním čase pro pevné hodnoty k a h , s použitím skutečnosti, že grafy s reprezentacemi tohoto druhu mají omezenou šířku dráhy [26 ] .

Pro kreslení koncepčních mřížek po vrstvách lze použít hybridní přístup, který kombinuje Sugiyamův přístup s aditivními metodami (ve kterých každý vrchol představuje množinu a poloha vrcholu je součtem vektorů reprezentujících prvky v množině). ). V tomto hybridním přístupu jsou fáze permutace vrcholu a přiřazení souřadnic algoritmu nahrazeny jediným krokem, ve kterém je každá horizontální poloha každého vrcholu vybrána jako součet reprezentací skalárních prvků pro daný vrchol [27] . Pro poskytnutí počátečního umístění pro vizualizační algoritmy výkonového grafu byly použity techniky vrstveného grafu [28] .

Poznámky

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Di Battista, Eades a kol., 1998 , str. 265–302.
  2. ↑ 1 2 3 4 5 6 7 8 9 Bastert, Matuszewski, 2001 , str. 87–120.
  3. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Healy a Nikolov, 2014 , str. 409–453.
  4. ↑ Sugiyama, Tagawa, Toda, 1981 , str. 109–125.
  5. ↑ Berger a Shor 1990 , str. 236–243.
  6. ↑ Eades, Lin, Smyth, 1993 , str. 319–323.
  7. ↑ Eades, Lin, 1995 , str. 15–26.
  8. ↑ Chen, Liu, Lu a kol., 2008 , str. jeden.
  9. ↑ 1 2 3 4 Gansner, Koutsofios, North, Vo, 1993 , str. 214–230.
  10. ↑ Healy, Nikolov, 2002 , str. 16-30.
  11. ↑ Newbery, 1989 , str. 76–85.
  12. ↑ Eppstein, Goodrich, Meng, 2004 , str. 184–194.
  13. ↑ Eades, Whitesides, 1994 , s. 361–374.
  14. ↑ 1 2 Eades, Wormald, 1994 , str. 379–403.
  15. ↑ Mäkinen, 1990 , s. 175–181.
  16. ↑ Dujmovic, Fernau, Kaufmann, 2008 , str. 313–323.
  17. ↑ Brandes, Köpf, 2002 , str. 31–44.
  18. ↑ Eiglsperger, Siebenhaller, Kaufmann, 2005 , str. 155–166.
  19. ↑ Nachmanson, Robertson, Lee, 2008 , str. 389–394.
  20. ↑ Auber, 2004 .
  21. ↑ Baburin, 2002 , str. 366–367.
  22. ↑ Bachmaier, 2007 , s. 583–594.
  23. ↑ Hong, Nikolov, 2005 , s. 69–74.
  24. ↑ Pupyrev, Nachmanson, Kaufmann, 2011 , str. 329–340.
  25. ↑ Eppstein, Goodrich, Meng, 2007 , str. 439–452.
  26. ↑ Dujmović, Fellows, Kitching et al., 2008 , s. 267–292.
  27. ↑ Cole, 2001 , str. 47–53.
  28. ↑ Schwikowski, Uetz, Fields, 2000 , str. 1257–126.

Literatura