Graphviz Dot Algorithm

Question

Czy istnieje dokumentacja (pełny pseudo kod?) Na algorytmie z kropki w bibliotece Graphviz?

Znalazłem jedynie częściową dokumentację pseudo-kodu.

Answer 1

Oto kilka referencji dla Ciebie. Najbardziej kompletny (poza samym kodem źródłowym kropki) jest prawdopodobnie # 2, dokument "Technika rysowania wyreżyserowanych wykresów" napisana przez kilku autorów Graphiz.

(1) "z rysunku wykresy dot"

W Drawing graphs with dot algorytm Dot układ jest opisany w następujący sposób:

kropka rysuje wykres w czterech głównych etapach. Znajomość tego pomaga zrozumieć, jakiego rodzaju układy tworzą kropki i jak można je kontrolować. Procedura umieszczana przez dot opiera się na wykresie będącym acyklicznym. Zatem pierwszym krokiem jest przerwanie dowolnych cykli, które występują na wykresie wejściowym poprzez odwrócenie kierunku wewnętrznego pewnych cyklicznych krawędzi. Następny krok przypisuje węzły do ​​dyskretnych rang lub poziomów. W rysunku od góry do dołu rangi określają współrzędne Y. Krawędzie obejmujące więcej niż jedną rangę dzielą się na łańcuchy "wirtualnych" węzłów i krawędzi o długości jednostkowej. Trzeci krok nakazuje węzły w szeregach, aby uniknąć przekroczenia. Czwarty krok ustawia współrzędne X węzłów, aby zachować krótkie krawędzie, a ostatni krok trasuje krawędzie splajnów. To jest to samo ogólne podejście, co większość hierarchicznych programów do rysowania wykresów, opartych na pracach Warfield [War77], Carpano [Car80] i Sugiyama [STT81]. Odsyłamy czytelnika do [GKNV93] do dokładnego wyjaśnienia algorytmów Dot za

Dokumenty wymienione w tym ustępie są takie:

• [Car80] M. Carpano. Automatyczne wyświetlanie zhierarchizowanych wykresów dla komputerowej analizy decyzji. IEEE Transactions on Software Engineering, SE-12 (4): (. Oczywiście do kupienia here) 538-546, kwiecień 1980.

• [GKNV93] Emden R. Gansner Eleftherios Koutsofios, Stephen C. Północnej i Kiem-Phong Vo. Technika rysowania ukierunkowanych wykresów. IEEE Trans. Sofware Eng., 19 (3): 214-230, maj 1993. (Dostępne here na stronie Graphviz.org.)

• [STT81] K. Sugiyama, S. Tagawa i M. Toda. Metody wizualnego zrozumienia hierarchicznych struktur systemowych. IEEE Transactions on Systems, Man i Cybernetyki, SMC-11 (2): (. Oczywiście do kupienia here) 109-125, luty 1981.

• [War77] John Warfield. Crossing Theory and Hierarchy Mapping. IEEE Transactions on Systems, Man i Cybernetyki, SMC-7 (7): (. Oczywiście do kupienia here) 505-523, lipiec 1977.

(2) "technikę rysowania graf skierowany" algorytm

Dot jest szczegółowo opisana w artykule "A Technique for Drawing Directed Graphs", opublikowane w czasopiśmie IEEE Transactions on Software Engineering w 1993 roku (i dostępny za darmo na stronie Graphviz.org). To jest źródło "[GKNV93]" cytowane powyżej.

Abstrakcyjny, na co warto, to:

Opiszemy algorytm cztery przejścia do rysowania graf skierowany. Pierwsze przejście znajduje optymalne przypisanie rangi przy użyciu algorytmu sieci simplex. Drugie przejście ustala kolejność wierzchołków w szeregach przez iteracyjną heurystykę obejmującą nową funkcję wagową i lokalne transpozycje w celu zmniejszenia przekroczeń. Trzecie przejście znajduje optymalne współrzędne dla węzłów przez skonstruowanie i uszeregowanie pomocniczego wykresu. Czwarte przejście powoduje, że splajny rysują krawędzie. Algorytm wykonuje dobre rysunki i działa szybko.

(3) "Korzystanie Graphviz jako Library"

"Using Graphviz as a Library" stanowi podsumowanie algorithim każdy silnik layoutu w rozdziale 3.1. Część opisu dla kropki jest następująca:

Algorytm kropkowy tworzy uszeregowany układ wykresu z zachowaniem krawędzi, jeśli to możliwe. Jest to szczególnie przydatne do wyświetlania hierarchii lub kierowanych acyklicznych wykresów. Podstawowy schemat układu jest przypisany do Sugiyama i wsp. [STT81] Specyficzny algorytm zastosowany przez kropkę jest zgodny z krokami opisanymi przez Gansner i wsp. [GKNV93]

Kroki w układzie punktowym to: 1) inicjalizacja 2) pozycja 3) mincross 4) pozycja 5) sameports 6) splajny 7) compoundEdges

Po inicjalizacji algorytm przypisuje każdy węzeł do dyskretnej pozycji (rangi) za pomocą programu integer, aby zminimalizować sumę (dyskretnych) długości krawędzi. Następny etap (mincross) zmienia kolejność węzłów w szeregi, aby zmniejszyć poprzeczne przejścia. Następnie następuje przypisanie (pozycja) aktualnych współrzędnych do węzłów, przy użyciu innego programu integer w celu skompaktowania wykresu i wyprostowania krawędzi. W tym momencie wszystkie węzły będą miały ustawioną pozycję w atrybucie coordin. Ponadto ustawiany jest atrybut bb graniczny dla wszystkich klastrów.

Oznaczenie "[GKNV93]" odnosi się do "Techniki rysowania ukierunkowanych wykresów", jak pokazano powyżej.

Odwołanie "[STT81]" odnosi się do "Metody wizualnego zrozumienia hierarchicznych struktur systemowych", jak wspomniano powyżej.

(4) Możesz być także zainteresowany:

• Graphviz's Documentation Index, który zawiera łącza do szczegółowej dokumentacji i dodatkowego materiału tła.

• Graphviz's "Theory" page który łączy się z jeszcze większą ilością materiału tła.

• The raw source code for dot, który jest dostępny na GitHub.

• Niektóre powiązane dyskusje na temat d3.js Google Group.