TikZ and PGF Manual

Graph Drawing

28 Using Graph Drawing in TikZ¶

by Till Tantau

28.1 Choosing a Layout and a Library¶

The graph drawing engine is initialized when you load the library graphdrawing. This library provides the basic framework for graph drawing, including all options and keys described in the present section. However, this library does not load any actual algorithms for drawing graphs. For this, you need to use the following command, which is defined by the graphdrawing library:

Note that in addition to the graph drawing libraries, you may also wish to load the normal TikZ library graphs. It provides the powerful graph path command with its easy-to-use syntax for specifying graphs, but you can use the graph drawing engine independently of the graphs library, for instance in conjunction with the child or the edge syntax. Here is a typical setup:

Having set things up, you must then specify for which scopes the graph drawing engine should apply a layout algorithm to the nodes in the scope. Typically, you just add an option ending with ... layout to the graph path operation and then let the graph drawing do its magic:

Whenever you use such an option, you can:

• • Create nodes in the usual way. The nodes will be created completely, but then tucked away in an internal table. This means that all of TikZ’s options for nodes can be applied. You can also name a node and reference it later.

• • Create edges using either the syntax of the graph command (using --, <-, ->, or <->), or using the edge command, or using the child command. These edges will, however, not be created immediately. Instead, the basic layer’s command \pgfgdedge will be called, which stores “all the information concerning the edge”. The actual drawing of the edge will only happen after all nodes have been positioned.

• • Most of the keys that can be passed to an edge will work as expected. In particular, you can add labels to edges using the usual node syntax for edges.

• • The label and pin options can be used in the usual manner with nodes inside a graph drawing scope. Only, the labels and nodes will play no role in the positioning of the nodes and they are added when the nodes are finally positioned.

• • Similarly, nodes that are placed “on an edge” using the implicit positioning syntax can be used in the usual manner.

Here are some things that will not work:

• • Only edges created using the graph syntax, the edge command, or the child command will correctly pass their connection information to the basic layer. When you write \draw (a)--(b); inside a graph drawing scope, where a and b are nodes that have been created inside the scope, you will get an error message / things will look wrong. The reason is that the usual -- is not “caught” by the graph drawing engine and, thus, tries to immediately connect two nodes that do not yet exist (except inside some internal table).

• • The options of edges are executed twice: Once when the edge is “examined” by the \pgfgdedge command (using some magic to shield against the side effects) and then once more when the edge is actually created. Fortunately, in almost all cases, this will not be a problem; but if you do very evil magic inside your edge options, you must roll a D100 to see what strange things will happen. (Do no evil, by the way.)

If you are really interested in the “fine print” of what happens, please see Section 29.

28.2 Graph Drawing Parameters¶

Graph drawing algorithms can typically be configured in some way. For instance, for a graph drawing algorithm that visualizes its nodes as a tree, it will typically be useful when the user can change the so-called level distance and the sibling distance. For other algorithms, like force-based algorithms, a large number of parameters influence the way the algorithms work. Options that influence graph drawing algorithms will be called (graph drawing) parameters in the following. From the user’s point of view, these parameters look like normal TikZ keys and you set them in the usual way. Internally, they are treated a bit differently from normal keys since their “effect” becomes apparent only later on, namely during the run of the graph drawing algorithm.

A graph drawing algorithm may or may not take different graph parameters into account. After all, these options may even outright contradict each other, so an algorithm can only try to “do its best”. While many graph parameters are very specific to a single algorithm, a number of graph parameters will be important for many algorithms and they are documented in the course of the present section. Here is an example of an option the “always works”:

28.3 Padding and Node Distances¶

In many drawings, you may wish to specify how “near” two nodes should be placed by a graph drawing algorithm. Naturally, this depends strongly on the specifics of the algorithm, but there are a number of general keys that will be used by many algorithms.

There are different kinds of objects for which you can specify distances and paddings:

• • You specify the “natural” distance between nodes connected by an edge using node distance, which is also available in normal TikZ albeit for a slightly different purpose. However, not every algorithm will (or can) honor the key; see the description of each algorithm what it will “make of this option”.

• • A number of graph drawing algorithms arrange nodes in layers (or levels); we refer to the nodes on the same layer as siblings (although, in a tree, siblings are only nodes with the same parent; nevertheless we use “sibling” loosely also for nodes that are more like “cousins”).

• • When a graph consists of several connected component, many graph drawing algorithms will layout these components individually. The different components will then be arranged next to each other, see Section 28.7 for the details, such that between the nodes of any two components a padding is available.

28.4 Anchoring a Graph¶

A graph drawing algorithm must compute positions of the nodes of a graph, but the computed positions are only relative (“this node is left of this node, but above that other node”). It is not immediately obvious where the “the whole graph” should be placed absolutely once all relative positions have been computed. In case that the graph consists of several unconnected components, the situation is even more complicated.

The order in which the algorithm layer determines the node at which the graph should be anchored:

• 1. If the anchor node=⟨node name⟩ option given to the graph as a whole, the graph is anchored at ⟨node name⟩, provided there is a node of this name in the graph. (If there is no node of this name or if it is misspelled, the effect is the same as if this option had not been given at all.)

• 2. Otherwise, if there is a node where the anchor here option is specified, the first node with this option set is used.

• 3. Otherwise, if there is a node where the desired at option is set (perhaps implicitly through keys like x), the first such node is used.

• 4. Finally, in all other cases, the first node is used.

In the above description, the “first” node refers to the node first encountered in the specification of the graph.

Once the node has been determined, the graph is shifted so that this node lies at the position specified by anchor at.

28.5 Orienting a Graph¶

Just as a graph drawing algorithm cannot know where a graph should be placed on a page, it is also often unclear which orientation it should have. Some graphs, like trees, have a natural direction in which they “grow”, but for an “arbitrary” graph the “natural orientation” is, well, arbitrary.

There are two ways in which you can specify an orientation: First, you can specify that the line from a certain vertex to another vertex should have a certain slope. How these vertices and slopes are specified in explained momentarily. Second, you can specify a so-called “growth direction” for trees.

28.6 Fine-Tuning Positions of Nodes¶

28.7 Packing of Connected Components¶

Graphs may be composed of subgraphs or components that are not connected to each other. In order to draw these nicely, most graph drawing algorithms split them into separate graphs, compute their layouts with the same graph drawing algorithm independently and, in a postprocessing step, arrange them next to each other. Note, however, that some graph drawing algorithms can also arrange the nodes of the graph in a uniform way even for unconnected components (the simple necklace layout is a case in point); for such algorithms you can choose whether they should be applied to each component individually or not (if not, the following options do not apply). To configure which is the case, use the componentwise key.

The default method for placing the different components works as follows:

• 1. For each component, a layout is determined and the component is oriented as described Section 28.5 on the orientation of graphs.

• 2. The components are sorted as prescribed by the component order key.

• 3. The first component is now placed (conceptually) at the origin. (The final position of this and all other components will be determined later, namely in the anchoring phase, but let us imagine that the first component lies at the origin at this point.)

• 4. The second component is now positioned relative to the first component. The “direction” in which the next component is placed relative to the first one is determined by the component direction key, so components can be placed from left to right or up to down or in any other direction (even something like \(30^\circ \)). However, both internally and in the following description, we assume that the components are placed from left to right; other directions are achieved by doing some (clever) rotating of the arrangement achieved in this way.

  So, we now wish to place the second component to the right of the first component. The component is first shifted vertically according to some alignment strategy. For instance, it can be shifted so that the topmost node of the first component and the topmost node of the second component have the same vertical position. Alternatively, we might require that certain “alignment nodes” in both components have the same vertical position. There are several other strategies, which can be configured using the component align key.

  One the vertical position has been fixed, the horizontal position is computed. Here, two different strategies are available: First, image rectangular bounding boxed to be drawn around both components. Then we shift the second component such that the right border of the bounding box of the first component touches the left border of the bounding box of the second component. Instead of having the bounding boxes “touch”, we can also have a padding of component sep between them. The second strategy is more involved and also known as a “skyline” strategy, where (roughly) the components are “moved together as near as possible so that nodes do not touch”.

• 5. After the second component has been placed, the third component is considered and positioned relative to the second one, and so on.

• 6. At the end, as hinted at earlier, the whole arrangement is rotate so that instead of “going right” the component go in the direction of component direction. Note, however, that this rotation applies only to the “shift” of the components; the components themselves are not rotated. Fortunately, this whole rotation process happens in the background and the result is normally exactly what you would expect.

In the following, we go over the different keys that can be used to configure the component packing.

28.7.1 Ordering the Components¶

The different connected components of the graph are collected in a list. The ordering of the nodes in this list can be configured using the following key.

28.7.2 Arranging Components in a Certain Direction¶

28.7.3 Aligning Components¶

When components are placed next to each from left to right, it is not immediately clear how the components should be aligned vertically. What happens is that in each component a horizontal line is determined and then all components are shifted vertically so that the lines are aligned. There are different strategies for choosing these “lines”, see the description of the options described later on. When the component direction option is used to change the direction in which components are placed, it certainly make no longer sense to talk about “horizontal” and “vertical” lines. Instead, what actually happens is that the alignment does not consider “horizontal” lines, but lines that go in the direction specified by component direction and aligns them by moving components along a line that is perpendicular to the line. For these reasons, let us call the line in the component direction the alignment line and a line that is perpendicular to it the shift line.

The first way of specifying through which point of a component the alignment line should get is to use the option align here. In many cases, however, you will not wish to specify an alignment node manually in each component. Instead, you will use the component align key to specify a strategy that should be used to automatically determine such a node.

Using a combination of component direction and component align, numerous different packing strategies can be configured. However, since names like counterclockwise are a bit hard to remember and to apply in practice, a number of easier-to-remember keys are predefined that combine an alignment and a direction.

28.7.4 The Distance Between Components¶

Once the components of a graph have been oriented, sorted, aligned, and a direction has been chosen, it remains to determine the distance between adjacent components. Two methods are available for computing this distance, as specified by the following option:

28.8 Anchoring Edges¶

When a graph has been laid out completely, the edges between the nodes must be drawn. Conceptually, an edge is “between two nodes”, but when we actually draw the node, we do not really want the edge’s path to start “in the middle” of the node; rather, we want it to start “on the border” and also end there.

Normally, computing such border positions for nodes is something we would leave to the so-called display layer (which is typically TikZ and TikZ is reasonably good at computing border positions). However, different display layers may behave differently here and even TikZ fails when the node shapes are very involved and the paths also.

For these reasons, computing the anchor positions where edges start and end is done inside the graph drawing system. As a user, you specify a tail anchor and a head anchor, which are points inside the tail and head nodes, respectively. The edge path will then start and end at these points, however, they will usually be shortened so that they actually start and end on the intersection of the edge’s path with the nodes’ paths.

28.9 Hyperedges¶

28.10 Using Several Different Layouts to Draw a Single Graph¶

Inside each graph drawing scope, a main algorithm is used to perform the graph drawing. However, parts of the graph may be drawn using different algorithms: For instance, a graph might consist of several, say, cliques that are arranged in a tree-like fashion. In this case, it might be useful to layout each clique using a circular layout, but then lay out all laid out cliques using a tree drawing algorithm.

In order to lay out a graph using multiple algorithms, we need two things: First, we must be able to specify which algorithms should be used where and, second, we must be able to resolve conflicts that may result from different algorithms “having different ideas” concerning where nodes should be placed.

28.10.1 Sublayouts¶

Specifying different layouts for a graph is easy: Inside a graph drawing scope, simply open scopes, in which you use an option like tree layout for the nodes mentioned in this scope. Inside these scopes, you can open even subscopes for sublayouts, and so on. Furthermore, the graphs library has special support for sublayouts.

Let us start with the “plain” syntax for opening sublayouts: You pass a key for creating layouts to a scope:

Let us see, what is going on here. The main layout (spring layout) contains two sublayouts (the two tree layouts). Both of them are laid out independently (more on the details in a moment). Then, from the main layout’s point of view, the sublayouts behave like “large nodes” and, thus, the edge between a and 1 is actually the only edge that is used by the spring layout – resulting in a simple layout consisting of one big node at the top and a big node at the bottom.

The graphs library has a special support for sublayouts: The syntax is as follows: wherever a normal node would go, you can write

// [⟨layout options⟩] {⟨sublayout⟩}

Following the double slash, you may provide ⟨layout options⟩ in square brackets. However, you must provide a sublayout in braces. The contents of ⟨sublayout⟩ will be parsed using the usual graph syntax, but will form a sublayout.

In the above example, there is no node before the double slash, which means that the two sublayouts will be part of the main graph, but will not be indicated otherwise.

In the above example, the first sublayout is the one for the nodes with letter names. These nodes are arranged using a simple necklace layout as the sublayout inherits this option from the main layout. The two small trees (a -> {1, 2} and the tree starting at the d node) are also sublayouts, triggered by the tree layout option. They are also arranged. Then, all of the layouts are merged (as described later). The result is actually a single node, so the main layout does nothing here.

Compare the above to the following code:

Here, only the two trees are laid out first. They are then contracted into “giant nodes” and these are then part of the set of nodes that are arranged by the simple necklace layout. For details of how this contracting works, see below.

28.10.2 Subgraph Nodes¶

A subgraph node is a special kind of node that “surrounds” the vertices of a subgraph. The special property of a subgraph node opposed to a normal node is that it is created only after the subgraph has been laid out. However, the difference to a collection like hyper is that the node is available immediately as a normal node in the sense that you can connect edges to it.

The syntax used to declare a subgraph node in a graph specification is as follows:

"⟨node name⟩"/"⟨text⟩" [⟨node options⟩] // [⟨layout options⟩] {⟨subgraph⟩}

The idea ist that a subgraph node is declared like a normal node specification, but is followed by a double slash and a subgraph:

Note how the two subgraph nodes tree 1 and tree 2 surround the two smaller trees. In the example, both had trees as contents and these trees were rendered using a sublayout. However, a subgraph layout does not need to have its own layout: If you do not provide a layout name after the double slash, the subgraph node will simply surround all nodes that were placed by the main layout wherever they were placed:

Every time a subgraph node is created, the following style is execute:

28.10.3 Overlapping Sublayouts¶

Nodes and edges can be part of several layouts. This will inevitably lead to conflicts because algorithm will disagree on where a node should be placed on the canvas. For this reason, there are some rules governing how such conflicts are resolved: Given a layout, starting with the main layout, the graph drawing system does the following:

• 1. We start by first processing the (direct) sublayouts of the current layout (recursively). Sublayouts may overlap (they may share one or more nodes), but we run the specified layout algorithm for each sublayout independently on a “fresh copy” of all the nodes making up the sublayout. In particular, different, conflicting positions may be computed for nodes when they are present in several sublayouts.

• 2. Once all nodes in the sublayouts have been laid out in this way, we join overlapping elements. The idea is that if two layouts share exactly one vertex, we can shift them around so that his vertex is at the same position in both layouts. In more detail, the following happens:

  We build a (conceptual) graph whose nodes are the sublayouts and in which there is an edge between two nodes if the sublayouts represented by these elements have a node in common. Inside the resulting graph, we treat each connected component separately. Each component has the property that the sublayouts represented by the nodes in the component overlap by at least one node. We now join them as follows: We start with the first sublayout in the component (“first” with respect to the order in which they appear in the input graph) and “mark” this sublayout. We loop the following instructions as long as possible: Search for the first sublayout (again, with respect to the order in which they appear in the input) that is connect by an edge to a marked sublayout. The sublayout will now have at least one node in common with the marked sublayouts (possibly, even more). We consider the first such node (again, first respect to the input ordering) and shift the whole sublayout is such a way that this particular node is at the position is has in the marked sublayouts. Note that after the shift, other nodes that are also present in the marked sublayouts may lie at a different position in the current sublayout. In this case, the position in the marked sublayouts “wins”. We then mark the sublayout.

• 3. When the above algorithm has run, we will have computed positions for all nodes in all sublayouts of each of the components. For each component, we contract all nodes of the component to a single node. This new node will be “large” in the sense that its convex hull is the convex hull of all the nodes in the component. All nodes that used to be part of the component are removed and the new large node is added (with arcs adjusted appropriately).

• 4. We now run the layout’s algorithm on the resulting nodes (the remaining original nodes and the contracted nodes).

• 5. In a last step, once the graph has been laid out, we expand the nodes that were previously contracted. For this, the nodes that were deleted earlier get reinserted, but shifted by whatever amount the contraction node got shifted.

28.11 Miscellaneous Options¶