Summary of the document : Dot Guide - Graphviz
Graphviz is an open source solution to generate graphs from code. Here is a short summary of how the algorithm works and what is possible to do with it.
Component placement algorithm
The Dot component placement algorithm can be decomposed into five phases :
- Step 1 : Break all cycles by reversing some edge directions within cycles.
- Step 2 : Assign each node a rank level. This will determine the Y coordinates in a top to bottom drawing.
- Step 3 : Avoid crossings by rearranging nodes within ranks.
- Step 4 : Set X coordinates to keep edges short.
- Step 5 : Route edge splines.
This strategy is based on the work of Warfiel, Carpano and Surgiyama. See references below.
Dot tips and tricks - Layout
List of dot tips and tricks to customize and influence component placement in a graph.
- The ranks determine the nodes Y coordinates.
- 'Nodesep' and 'ranksep' attributes influence distances between nodes. 'Nodesep' acts on distances between two adjacent nodes within the same rank (horizontal) whereas 'ranksep' acts on distances between nodes of different ranks (vertical). p12
- 'Rankdir' attribute allows us to change the positioning from TopBottom to LeftRight (usefull when drawing timelines). p14
- Influence node ranks with attributes like 'rank' = same, min, source, max and sink. p15
- Influence edge weight : the heavier is an edge weight, the closer the node will be from each other. p15
- Group nodes together ('group') : It will keep edges as straight as possible and avoid crossings within the group.
- Node ports : define where the edge should land on a node. p18
- Clusters : define subgraphs in their own rectangle area. Possible to fill the rectangle with color for clarity. p19
- Concentrators : allow a technique of edge merging which can be useful in a dense layout. p24
Dot tips and tricks - Design
- Change node shape. p4
- Customize node labels. p6
- Edge label : add a line to link which label belongs to which edge - decorate attribute. p8
- Edge label : change the label orientation/distance with 'labelangle' and 'labeldistance' attributes. p8
- Change node color. p9
Link to Dot Guide
Papers to read later
M. Carpano. Automatic display of hierarchized graphs for computer aided decision analysis.IEEE Transactions on Software Engineering, SE-12(4):538–546, April 1980.Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong Vo. A Technique for Drawing Directed Graphs. IEEE Trans. Sofware Eng., 19(3):214–230, May 1993.
[New89] Frances J. Newbery. Edge Concentration: A Method for Clustering Directed Graphs. In 2nd International Workshop on Software Configuration Management, pages 76–85, October 1989. Published as ACM SIGSOFT Software Engineering Notes, vol. 17, no. 7, Novem-ber 1989.
[Nor92] Stephen C. North. Neato User’s Guide. Technical Report 59113-921014-14TM, AT&T Bell Laboratories, Murray Hill, NJ, 1992.
[STT81] K. Sugiyama, S. Tagawa, and M. Toda. Methods for Visual Understanding of Hierarchical System Structures. IEEE Transactions on Systems, Man, and Cybernetics, SMC-11(2):109–125, February 1981.
[War77] John Warfield. Crossing Theory and Hierarchy Mapping. IEEE Transactions on Systems, Man, and Cybernetics, SMC-7(7):505–523, July 1977.
No comments:
Post a Comment