GraphvizLayouts: Graphviz Layout Methods

In kasperdanielhansen/Rgraphviz: Provides plotting capabilities for R graph objects

Graphviz Layout Methods

Description

The following describes the different layout methods that can be used within Rgraphviz. Each layout method has its own particular advantages and disadvantages and can have its own quirks. Currently Rgraphviz supports three different layout methods: dot, twopi and neato.

Details

Portions of the layout descriptions were taken from documents provided at http://www.research.att.com/sw/graphviz. The specific documents are listed in the references section of this page.

The dot layout

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

dot draws a graph 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 coordnates of nodes to keep edges short, and the final step routes edge splines.

In dot, higher edge weights have the effect of causing edges to be shorter and straighter.

Fine-tuning should be approached cautiously. dot works best when it can makes a layout without much help or interference in its placement of individual nodes and edges. Layouts can be adjusted somewhat by increasing the weight of certain edges, and sometimes even by rearranging the order of nodes and edges in the file. But this can backfire because the layouts are not necessarily stable with respect to changes in the input graph. One last adjustment can invalidate all previous changes and make a very bad drawing.

The neato layout

neato is a program that makes layouts of undirected graphs following the filter model of dot. Its layout heuristic creates virtual physical models and runs an iterative solver to find low energy configurations. An ideal spring is placed between every pair of nodes such that its length is set to the shortest path distance between the endpoints. The springs push the nodes so their geometric distance in the layout approximates their path distance in the graph.

In neato, the edge weight is the strength of the corresponding spring.

As with dot, fine-tuning should be approached cautiously, as often small changes can have a drastic effect and create a poor looking layout.

The twopi layout

The radial layout algorithm represented by twopi is conceptually the simplest. It takes a node specified as the center of the layout and the root of the generated spanning tree. The remaining nodes are placed on a series of concentric circles about the center, the circle used corresponding to the graph-theoretic distance from the node to the center. Thus, for example, all of the neighbors of the center node are placed on the first circle around the center. The algorithm allocates angular slices to each branch of the induced spanning tree to guarantee enough space for the tree on each ring. It should be obvious from the description that the basic version of the twopi algorithm relies on the graph being connected.

Of great importance to the quality of the layout is the selection of an appropriate center node. By default, the twopi will randomly pick one of the nodes that are furthest from a leaf node, where a leaf node is a node of degree 1. The root attribute can be used to manually select a central node for the layout, and users are encouraged to use this attribute to select a node which provides a good quality layout. It often might not be obvious what that node will be, as it will vary from graph to graph, so some experimentation might be required.

As with dot and neato, fine-tuning should be approached cautiously, as often small changes can have a drastic effect and create a poor looking layout. The root node of the layout, as mentioned before, can have a profound effect on the outcome of the layout and care should be taken to select an appropriate one.

The circo layout

The circo layout method draws graphs using a circular layout (see Six and Tollis, GD '99 and ALENEX '99, and Kaufmann and Wiese, GD '02.) The tool identifies biconnected components and draws the nodes of the component on a circle. The block-cutpoint tree is then laid out using a recursive radial algorithm. Edge crossings within a circle are minimized by placing as many edges on the circle's perimeter as possible. In particular, if the component is outerplanar, the component will have a planar layout.

If a node belongs to multiple non-trivial biconnected components, the layout puts the node in one of them. By default, this is the first non-trivial component found in the search from the root component.

The fdp layout

The fdp layout draws undirected graphs using a spring model similar to neato. It relies on a force-directed approach in the spirit of Fruchterman and Reingold. The fdp model uses springs only between nodes connected with an edge, and an electrical repulsive force between all pairs of nodes. Also, it achieves a layout by minimizing the forces rather than the energy of the system.

Author(s)

Jeff Gentry

References

http://www.research.att.com/sw/tools/graphviz/dotguide.pdf, http://www.research.att.com/sw/tools/graphviz/neatoguide.pdf, http://www.research.att.com/sw/tools/graphviz/libguide.pdf

See Also

GraphvizAttributes, plot.graph, agopen

Examples

set.seed(123)
V <- letters[1:10]
M <- 1:4
g1 <- randomGraph(V, M, .2)
if (interactive()) {
  op <- par()
  on.exit(par=op)
  par(ask=TRUE)
  plot(g1, "dot")
  plot(g1, "neato")
  plot(g1, "twopi")
}

kasperdanielhansen/Rgraphviz documentation built on Nov. 4, 2022, 4:14 a.m.