Graphviz Dot Algorithm

Question

Is there any documentation (full pseudo code?) on the algorithm from dot within the Graphviz Library?

I only found some partial pseudo code documentation.

Answer 1

Here are a few references for you. The most complete (short of the Graphviz source code itself) is probably #2, the paper "A Technique for Drawing Directed Graphs" which is written by several of the Graphviz contributors themselves.

(1) "Drawing graphs with dot"

In Drawing graphs with dot, dot's layout algorithm is described like this:

dot draws graphs in four main phases. Knowing this helps you to understand what kind of layouts dot makes and how you can control them. The layout procedure used by dot relies on the graph being acyclic. Thus, the first step is to break any cycles which occur in the input graph by reversing the internal direction of certain cyclic edges. The next step assigns nodes to discrete ranks or levels. In a top-to-bottom drawing, ranks determine Y coordinates. Edges that span more than one rank are broken into chains of “virtual” nodes and unit-length edges. The third step orders nodes within ranks to avoid crossings. The fourth step sets X coordinates of nodes to keep edges short, and the final step routes edge splines. This is the same general approach as most hierarchical graph drawing programs, based on the work of Warfield [War77], Carpano [Car80] and Sugiyama [STT81]. We refer the reader to [GKNV93] for a thorough explanation of dot’s algorithms

The papers cited in that paragraph are these:

• [Car80] M. Carpano. Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Transactions on Software Engineering, SE-12(4):538–546, April 1980. (Evidently available for purchase here.)

• [GKNV93] 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. (Available here on the Graphviz.org site.)

• [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. (Evidently available for purchase here.)

• [War77] John Warfield. Crossing Theory and Hierarchy Mapping. IEEE Transactions on Systems, Man, and Cybernetics, SMC-7(7):505–523, July 1977. (Evidently available for purchase here.)

(2) "A Technique for Drawing Directed Graphs"

dot's algorithm is described in detail in the paper "A Technique for Drawing Directed Graphs", published in the journal IEEE Transactions on Software Engineering in 1993 (and available for free on the Graphviz.org site). This is the "[GKNV93]" source cited above.

The abstract, for what it's worth, is this:

We describe a four-pass algorithm for drawing directed graphs. The first pass finds an optimal rank assignment using a network simplex algorithm. The second pass sets the vertex order within ranks by an iterative heuristic incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm makes good drawings and runs fast.

(3) "Using Graphviz as a Library"

"Using Graphviz as a Library" provides a summary of each layout engine's algorithim in Section 3.1. Part of the description for dot is this:

The dot algorithm produces a ranked layout of a graph respecting edge directions if possible. It is particularly appropriate for displaying hierarchies or directed acyclic graphs. The basic layout scheme is attributed to Sugiyama et al.[STT81] The specific algorithm used by dot follows the steps described by Gansner et al.[GKNV93]

The steps in the dot layout are: 1) initialize 2) rank 3) mincross 4) position 5) sameports 6) splines 7) compoundEdges

After initialization, the algorithm assigns each node to a discrete rank (rank) using an integer program to minimize the sum of the (discrete) edge lengths. The next step (mincross) rearranges nodes within ranks to reduce edge crossings. This is followed by the assignment (position) of actual coordinates to the nodes, using another integer program to compact the graph and straighten edges. At this point, all nodes will have a position set in the coord attribute. In addition, the bounding box bb attribute of all clusters are set.

The "[GKNV93]" reference is to "A Technique for Drawing Directed Graphs", as linked above.

The "[STT81]" reference is to "Methods for Visual Understanding of Hierarchical System Structures" as cited above.

(4) You might also be interested in:

• Graphviz's Documentation Index, which has links to detailed documentation and additional background material.

• Graphviz's "Theory" page which links to even more background material.

• The raw source code for dot is now on GitLab, see dotgen and dotgen2. The raw source code for dot, which is available on GitHub.

• Some related discussion on the d3.js Google Group.