Graphviz Layout Methods
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.
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 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.
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 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 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 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.
Jeff Gentry
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")
}Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.