Graphviz Algorithme Dot

Question

Y a-t-il une documentation (code pseudo-complet?) sur l'algorithme du dot dans la bibliothèque Graphviz?

J'ai seulement trouvé une documentation partielle en pseudo-code.

Answer 1

Voici quelques références pour vous. La plus complète (à l'exception du code source de Graphviz lui-même) est probablement la n°2, l'article "A Technique for Drawing Directed Graphs" écrit par plusieurs des contributeurs de Graphviz eux-mêmes.

(1) "Dessiner des graphiques avec dot"

Dans Drawing graphs with dot, l'algorithme de disposition de dot est décrit ainsi :

dot dessine des graphiques en quatre phases principales. Cela vous aide à comprendre le type de mises en page que dot réalise et comment vous pouvez les contrôler. La procédure de disposition utilisée par dot repose sur le fait que le graphique est acyclique. Ainsi, la première étape consiste à casser les cycles qui se produisent dans le graphique d'entrée en inversant la direction interne de certaines arêtes cycliques. La prochaine étape consiste à attribuer des noeuds à des rangs ou niveaux distincts. Dans un dessin de haut en bas, les rangs déterminent les coordonnées Y. Les arêtes qui traversent plusieurs rangs sont fractionnées en chaînes de noeuds "virtuels" et en arêtes de longueur unitaire. La troisième étape consiste à ordonner les noeuds au sein des rangs pour éviter les croisements. La quatrième étape définit les coordonnées X des noeuds pour raccourcir les arêtes, et la dernière étape trace les splines des arêtes. C'est la même approche générale que la plupart des programmes de dessins de graphiques hiérarchiques, basée sur le travail de Warfield [War77], Carpano [Car80] et Sugiyama [STT81]. Nous renvoyons le lecteur à [GKNV93] pour une explication approfondie des algorithmes de dot.

Les documents cités dans ce paragraphe sont les suivants :

• [Car80] M. Carpano. Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Transactions on Software Engineering, SE-12(4):538–546, avril 1980. (Apparemment disponible à l'achat ici.)

• [GKNV93] Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, et Kiem-Phong Vo. A Technique for Drawing Directed Graphs. IEEE Trans. Sofware Eng., 19(3):214–230, mai 1993. (Disponible ici sur le site Graphviz.org.)

• [STT81] K. Sugiyama, S. Tagawa, et M. Toda. Methods for Visual Understanding of Hierarchical System Structures. IEEE Transactions on Systems, Man, and Cybernetics, SMC-11(2):109–125, février 1981. (Apparemment disponible à l'achat ici.)

• [War77] John Warfield. Crossing Theory and Hierarchy Mapping. IEEE Transactions on Systems, Man, and Cybernetics, SMC-7(7):505–523, juillet 1977. (Apparemment disponible à l'achat ici.)

(2) "Une technique pour dessiner des graphiques dirigés"

L'algorithme de dot est décrit en détail dans l'article "Une technique pour dessiner des graphiques dirigés", publié dans la revue IEEE Transactions on Software Engineering en 1993 (et disponible gratuitement sur le site Graphviz.org). Ceci correspond à la source "[GKNV93]" citée ci-dessus.

L'abstract, pour ce que ça vaut, est le suivant :

Nous décrivons un algorithme en quatre passes pour dessiner des graphiques dirigés. La première passe trouve une affectation de rang optimal en utilisant un algorithme simplex de réseau. La deuxième passe définit l'ordre des sommets au sein des rangs par une heuristique itérative intégrant une nouvelle fonction de poids et des transpositions locales pour réduire les croisements. La troisième passe trouve des coordonnées optimales pour les noeuds en construisant et classant un graphe auxiliaire. La quatrième passe crée des splines pour dessiner les arêtes. L'algorithme produit de bons dessins et fonctionne rapidement.

(3) "Utiliser Graphviz comme une bibliothèque"

"Utiliser Graphviz comme une bibliothèque" fournit un résumé de l'algorithme de chaque moteur de disposition dans la Section 3.1. Une partie de la description pour dot est la suivante :

L'algorithme de dot produit une disposition classée d'un graphique en respectant autant que possible les directions des arêtes. Il est particulièrement approprié pour afficher des hiérarchies ou des graphiques dirigés acycliques. Le schéma de disposition de base est attribué à Sugiyama et al.[STT81] L'algorithme spécifique utilisé par dot suit les étapes décrites par Gansner et al.[GKNV93]

Les étapes dans la mise en page de dot sont : 1) initialisation 2) rang 3) mincross 4) position 5) sameports 6) splines 7) compoundEdges

Après l'initialisation, l'algorithme attribue à chaque noeud un rang discret (rang) en utilisant un programme entier pour minimiser la somme des longueurs d'arêtes (discrètes). La prochaine étape (mincross) réarrange les noeuds au sein des rangs pour réduire les croisements d'arêtes. Cela est suivi par l'affectation (position) des coordonnées réelles aux noeuds, en utilisant un autre programme entier pour compacter le graphe et aligner les arêtes. À ce stade, tous les noeuds auront une position définie dans l'attribut coord. De plus, la boîte englobante bb de tous les clusters est définie.

La référence "[GKNV93]" renvoie à "Une technique pour dessiner des graphiques dirigés", comme mentionné ci-dessus.

La référence "[STT81]" concerne "Méthodes pour la compréhension visuelle des structures de systèmes hiérarchiques" comme mentionné ci-dessus.

(4) Vous pourriez également être intéressé par :

• Index de documentation de Graphviz, qui contient des liens vers une documentation détaillée et du matériel de fond supplémentaire.

• Page "Théorie" de Graphviz qui renvoie à encore plus de matériel de fond.

• Le code source brut de dot est maintenant sur GitLab, voir dotgen et dotgen2. Le code source brut de dot, qui est disponible sur GitHub.

• Une discussion connexe sur le groupe Google d3.js.