Desen grafic stratificat

Desenul de grafic stratificat sau desenul de grafic ierarhic este o metodă de vizualizare a graficului în care vârfurile unui grafic direcționat sunt desenate în rânduri orizontale sau straturi cu marginile îndreptate predominant în jos [1] [2] [3] . Acesta este cunoscut sub numele de stilul Sugiyama de vizualizare grafică , după Kozo Sugiyama, care a dezvoltat pentru prima dată acest stil [4] .

O formă ideală de desen stratificat ar fi desenul plan în sus , în care toate marginile sunt orientate în aceeași direcție și nicio pereche de margini nu se intersectează. Cu toate acestea, graficele conțin adesea cicluri, iar problema minimizării numărului de muchii îndreptate în direcția opusă este NP-hard , la fel ca problema minimizării numărului de intersecții. Din acest motiv, sistemele de randare a graficelor stratificate utilizează de obicei o secvență de abordări euristice care reduc aceste tipuri de defecte și găsesc modelul cu cele mai puține defecte.

Algoritm de aspect

Construcția vizualizării strat cu strat a graficelor are loc în mai multe etape:

Implementări

În forma sa cea mai simplă, algoritmii de redare a graficelor stratificate pot dura O( mn ) timp pe grafice cu n vârfuri și m muchii, deoarece pot fi create un număr mare de vârfuri suplimentare. Totuși, pentru unele variante ale algoritmului, este posibil să se simuleze efectul unor vârfuri suplimentare fără a le adăuga efectiv, ceea ce duce la implementarea algoritmului cu un timp de execuție aproape liniar [18] .

Limbajul de descriere „DOT” din pachetul Graphviz creează reprezentări stratificate [9] . Algoritmul de vizualizare a graficului stratificat este, de asemenea, inclus în biblioteca Microsoft automat graph layout [19] și în cadrul Tulip [ [20] .

Variante

Deși desenul se face de obicei cu vârfuri în rânduri și cu muchii mergând de sus în jos, algoritmii de redare a graficelor stratificate pot în schimb aranja vârfurile vertical în coloane și desena marginile de la stânga la dreapta [21] . Același cadru poate folosi aranjamentul radial, unde vârfurile sunt situate pe cercuri concentrice (centrate la un nod inițial) [3] [22] , precum și stratificarea graficului 3D [3] [23] .

La vizualizarea strat cu strat a graficelor cu un număr mare de arce lungi, haosul poate fi redus prin gruparea seturi de muchii în mănunchiuri și direcționarea lor prin același set de vârfuri suplimentare [24] . De asemenea, pentru a desena multe muchii care se intersectează între perechi de straturi succesive, muchiile din subgrafele bipartite maxime pot fi grupate în pachete confluente [25] .

Figurile în care vârfurile sunt aranjate în straturi pot fi construite prin algoritmi care nu urmează schema lui Sugiyama. De exemplu, se poate spune dacă un graf nedirecționat are o reprezentare cu cel mult k intersecții și h straturi în timp polinomial pentru valori fixe ale lui k și h , folosind faptul că graficele care au reprezentări de acest fel au o lățime de cale mărginită [26]. ] .

Pentru desenarea strat-cu-strat a rețelelor conceptuale , se poate folosi o abordare hibridă, combinând abordarea lui Sugiyama cu metode aditive (în care fiecare vârf reprezintă o mulțime, iar poziția vârfului este suma vectorilor reprezentând elementele din mulțime). ). În această abordare hibridă, fazele de permutare a vârfurilor și de atribuire a coordonatelor ale algoritmului sunt înlocuite cu un singur pas în care fiecare poziție orizontală a fiecărui vârf este aleasă ca sumă a reprezentărilor elementului scalar pentru acel vârf [27] . Tehnicile de vizualizare a graficului stratificat au fost utilizate pentru a furniza locația inițială pentru algoritmii de vizualizare a graficului de putere [28] .

Note

  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 și Nikolov, 2014 , p. 409–453.
  4. ↑ Sugiyama, Tagawa, Toda, 1981 , p. 109–125.
  5. ↑ Berger și Shor 1990 , p. 236–243.
  6. ↑ Eades, Lin, Smyth, 1993 , p. 319–323.
  7. ↑ Eades, Lin, 1995 , p. 15–26.
  8. ↑ Chen, Liu, Lu et al., 2008 , p. unu.
  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, Câmpuri, 2000 , p. 1257–126.

Literatură