Réteges grafikon rajz

A réteges gráfrajz vagy hierarchikus gráfrajz egy gráfvizualizációs módszer , amelyben az irányított gráf csúcsait vízszintes sorokba vagy rétegekbe rajzolják, amelyek élei túlnyomórészt lefelé irányulnak [1] [2] [3] . Ez a gráfvizualizáció Sugiyama stílusaként ismert, Kozo Sugiyama után, aki először fejlesztette ki ezt a stílust [4] .

A réteges rajz ideális formája a felfelé irányuló síkrajz , amelyben minden él ugyanabba az irányba van orientálva, és egyetlen élpár sem metszi egymást. A gráfok azonban gyakran tartalmaznak ciklusokat, és az ellenkező irányba mutató élek számának minimalizálása NP-nehéz , csakúgy, mint a metszéspontok számának minimalizálása. Emiatt a réteges gráf-megjelenítő rendszerek jellemzően heurisztikus megközelítések sorozatát alkalmazzák, amelyek csökkentik az ilyen típusú hibákat, és megtalálják a legkevesebb hibával rendelkező mintát.

Elrendezési algoritmus

A grafikonok rétegenkénti megjelenítésének felépítése több szakaszban történik:

Megvalósítások

A legegyszerűbb formájában a réteges gráf renderelő algoritmusok O( mn ) időt vehetnek igénybe n csúcsú és m élű gráfokon, mivel nagyszámú további csúcs hozható létre. Az algoritmus egyes változatainál azonban lehetőség van további csúcsok hatásának szimulálására anélkül, hogy azokat ténylegesen hozzáadnánk, ami az algoritmus közel lineáris végrehajtási idővel való megvalósításához vezet [18] .

A Graphviz csomag "DOT" leíró nyelve réteges reprezentációkat hoz létre [9] . A réteges gráf vizualizációs algoritmus a Microsoft automatikus gráfelrendezési könyvtárában [19] és a Tulip keretrendszerben [20] is megtalálható .

Változatok

Bár a rajzolás általában sorok csúcsaival és felülről lefelé haladó élekkel történik, a réteges gráfleképezési algoritmusok ehelyett képesek függőlegesen oszlopokba rendezni a csúcsokat, és balról jobbra rajzolni az éleket [21] . Ugyanez a keretrendszer használhat radiális elrendezést, ahol a csúcsok koncentrikus körökön helyezkednek el (valamilyen kezdeti csomópont középpontjában) [3] [22] , valamint 3D gráfrétegezést [3] [23] .

A nagyszámú hosszú ívű gráfok rétegenkénti megjelenítése esetén a káosz csökkenthető, ha az élkészleteket kötegekbe csoportosítjuk, és ugyanazon a további csúcsokon keresztül irányítjuk [24] . Hasonlóképpen, sok egymást metsző él megrajzolásához az egymást követő rétegpárok között a maximális kétrészes részgráfok élei összefüggő csomagokba csoportosíthatók [25] .

Azok az ábrák, amelyekben a csúcsok rétegekbe vannak rendezve, olyan algoritmusokkal készíthetők, amelyek nem követik Sugiyama sémáját. Például meg lehet állapítani, hogy egy irányítatlan gráf reprezentációja legfeljebb k metszésponttal és h réteggel rendelkezik-e polinomiális időben rögzített k és h értékek esetén , abból a tényből, hogy az ilyen ábrázolású gráfok korlátos útszélességgel rendelkeznek [26 ] .

Fogalomrácsok rétegről rétegre történő rajzolásához hibrid megközelítés használható, amely Sugiyama megközelítését additív módszerekkel kombinálja (amelyben minden csúcs egy halmazt reprezentál, a csúcs pozíciója pedig a halmaz elemeit reprezentáló vektorok összege ). Ebben a hibrid megközelítésben az algoritmus csúcspermutációs és koordináta-hozzárendelési fázisait egyetlen lépéssel helyettesítjük, amelyben minden csúcs minden vízszintes helyzetét az adott csúcs skalárelemreprezentációinak összegeként választjuk ki [27] . Réteges gráf-vizualizációs technikákat alkalmaztak a teljesítménygráf-vizualizációs algoritmusok kezdeti helyének meghatározására [28] .

Jegyzetek

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

Irodalom