The TikZ and PGF Packages
Manual for version 3.1.10

The table doc is used for documentation purposes. It is used to provide lazy documentation for keys, that is, to install documentation for keys only when this information is requested and when the documentation is kept in a separate file.

Using the doc facility is easy:

• 1. In the declare statement of the key, you do not provide fields like documentation or summary. Rather, you provide the field documentation_in, which gets the name of a Lua file the will be read whenever one of the fields documentation, summary, or examples is requested for the key.

• 2. When the key is requested, require will be applied to the filename given in the documentation_in field.

• 3. In this file, you start with the following code:

  copy
local doc = require 'pgf.gd.doc'
local key = doc.key
local documentation = doc.documentation
local summary = doc.summary
local example = doc.example


  This will setup nice shortcuts for the commands you are going to use in your file.

• 4. Next, for each to-be-lazily-documented key, add a block to the file like the following:

  copy
---
key "my radius"
summary "This key specifies a radius."
documentation
[[

This key is used, whenever...

]]
example "\tikz \graph [foo layout, my radius=5] { a--b };"
example "\tikz \graph [foo layout, my radius=3] { c--d };"


  Note that [[ and ]] are used in Lua for raw multi-line strings.

  The effect of the above code will be that for the key my radius the different field like summary or documentation get updated. The key function simple “selects” a key and subsequent commands like summary will update this key until a different key is selected through another use of key.

Alphabetical method summary:

function doc.documentation (string)

function doc.example (string)

function doc.key (key)

function doc.summary (string)

Selects the key which will be subsequently updated by the other functions of this class.

Parameters: 1. key A key.

Updates (replaces) the summary field of the last key selected through the key command.

Parameters: 1. string A (new) summary string.

Updates (replaces) the documentation field of the last key selected through the key command.

Parameters: 1. string A (new) documentation string. Typically, the [[ syntax will be used to specify this string.

Adds an example to the examples field of the last key selected through the key command.

Parameters: 1. string An additional example string.

In theory, graph drawing algorithms take graphs as input and output graphs embedded into the plane as output. In practice, however, the input to a graph drawing algorithm is not “just” the graph. Rather, additional information about the graph, in particular about the way the user specified the graph, is also important to many graph drawing algorithms.

The graph drawing system gathers both the original input graph as well as all additional information that is provided in the graph drawing scope inside a scope table. The object has a number of fields that inform an algorithm about the input.

For each graph drawing scope, a new Scope object is created. Graph drawing scopes are kept track of using a stack, but only the top of this stack is available to the interface classes.

Alphabetical method summary:

function Scope.new (initial)

Create a new Scope object.

Parameters: 1. initial A table of initial values for the newly created Scope object.

Returns: 1. The new scope object.

This namespace contains the classes modeling graphs, nodes, and edges. Also, the Coordinate class is found here, since coordinates are also part of the modeling.

Each Digraph instance models a directed, simple graph. “Directed” means that all edges “point” from a head node to a tail node. “Simple” means that between any nodes there can be (at most) one edge. Since these properties are a bit at odds with the normal behavior of “nodes” and “edges” in TikZ, different names are used for them inside the model namespace: The class modeling “edges” is actually called Arc to stress that an arc has a specific “start” (the tail) and a specific “end” (the head). The class modeling “nodes” is actually called Vertex, just to stress that this is not a direct model of a TikZ node, but can represent a arbitrary vertex of a graph, independently of whether it is an actual node in TikZ.

Time Bounds. Since digraphs are constantly created and modified inside the graph drawing engine, some care was taken to ensure that all operations work as quickly as possible. In particular:

• • Adding an array of \(k\) vertices using the add method needs time \(O(k)\).

• • Adding an arc between two vertices needs time \(O(1)\).

• • Accessing both the vertices and the arcs fields takes time \(O(1)\), provided only the above operations are used.

Deleting vertices and arcs takes more time:

• • Deleting the vertices given in an array of \(k\) vertices from a graph with \(n\) vertices takes time \(O(\max \{n,c\})\) where \(c\) is the number of arcs between the to-be-deleted nodes and the remaining nodes. Note that this time bound in independent of \(k\). In particular, it will be much faster to delete many vertices by once calling the remove function instead of calling it repeatedly.

• • Deleting an arc takes time \(O(t_o+h_i)\) where \(t_o\) is the number of outgoing arcs at the arc’s tail and \(h_i\) is the number of incoming arcs at the arc’s head. After a call to disconnect, the next use of the arcs field will take time \(O(|V| + |E|)\), while subsequent accesses take time \(O(1)\) – till the next use of disconnect. This means that once you start deleting arcs using disconnect, you should perform as many additional disconnects as possible before accessing arcs one more.

Stability. The vertices field and the array returned by Digraph:incoming and Digraph:outgoing are stable in the following sense: The ordering of the elements when you use ipairs on the will be the ordering in which the vertices or arcs were added to the graph. Even when you remove a vertex or an arc, the ordering of the remaining elements stays the same.

Alphabetical method summary:

function Digraph.new (initial)

function Digraph:__tostring ()

function Digraph:add (array)

function Digraph:arc (tail, head)

function Digraph:collapse (collapse_vertices, collapse_vertex, vertex_fun, arc_fun)

function Digraph:connect (s, t)

function Digraph:contains (v)

function Digraph:disconnect (v, t)

function Digraph:expand (vertex, vertex_fun, arc_fun)

function Digraph:incoming (v)

function Digraph:orderIncoming (v, vertices)

function Digraph:orderOutgoing (v, vertices)

function Digraph:outgoing (v)

function Digraph:reconnect (arc, tail, head)

function Digraph:remove (array)

function Digraph:sortIncoming (v, f)

function Digraph:sortOutgoing (v, f)

function Digraph:sync ()

Graphs are created using the new method, which takes a table of initial values as input (like most new methods in the graph drawing system). It is permissible that this table of initial values has a vertices field, in which case this array will be copied. In contrast, an arcs field in the table will be ignored – newly created graphs always have an empty arcs set. This means that writing Digraph.new(g) where g is a graph creates a new graph whose vertex set is the same as g’s, but where there are no edges:

To completely copy a graph, including all arcs, you have to write:

This operation takes time \(O(1)\).

Parameters: 1. initial A table of initial values. It is permissible that this array contains a vertices field. In this case, this field must be an array and its entries must be nodes, which will be inserted. If initial has an arcs field, this field will be ignored. The table must contain a field syntactic_digraph, which should normally be the syntactic digraph of the graph, but may also be the string "self", in which case it will be set to the newly created (syntactic) digraph.

Returns: 1. A newly-allocated digraph.

Add vertices to a digraph.

This operation takes time \(O(|\verb !array!|)\).

Parameters: 1. array An array of to-be-added vertices.

Remove vertices from a digraph.

This operation removes an array of vertices from a graph. The operation takes time linear in the number of vertices, regardless of how many vertices are to be removed. Thus, it will be (much) faster to delete many vertices by first compiling them in an array and to then delete them using one call to this method.

This operation takes time \(O(\max \{|\verb !array!|, |\verb !self.vertices!|\})\).

Parameters: 1. array The to-be-removed vertices.

Test, whether a graph contains a given vertex.

This operation takes time \(O(1)\).

Parameters: 1. v The vertex to be tested.

Returns the arc between two nodes, provided it exists. Otherwise, nil is returned.

This operation takes time \(O(1)\).

Parameters: 1. tail The tail vertex 2. head The head vertex

Returns: 1. The arc object connecting them

Returns an array containing the outgoing arcs of a vertex. You may only iterate over his array using ipairs, not using pairs.

This operation takes time \(O(1)\).

Parameters: 1. v The vertex

Returns: 1. An array of all outgoing arcs of this vertex (all arcs whose tail is the vertex)

Sorts the array of outgoing arcs of a vertex. This allows you to later iterate over the outgoing arcs in a specific order.

This operation takes time \(O(|\verb !outgoing!| \log |\verb !outgoings!|)\).

Parameters: 1. v The vertex 2. f A comparison function that is passed to table.sort

Reorders the array of outgoing arcs of a vertex. The parameter array must contain the same set of vertices as the outgoing array, but possibly in a different order.

This operation takes time \(O(|\verb !outgoing!|)\), where outgoing is the array of v’s outgoing arcs in self.

Parameters: 1. v The vertex 2. vertices An array containing the outgoing vertices in some order.

See outgoing.

See sortOutgoing.

See orderOutgoing.

Connects two nodes by an arc and returns the newly created arc object. If they are already connected, the existing arc is returned.

This operation takes time \(O(1)\).

Parameters: 1. s The tail vertex 2. t The head vertex (may be identical to tail in case of a loop)

Returns: 1. The arc object connecting them (either newly created or already existing)

Disconnect either a single vertex v from all its neighbors (remove all incoming and outgoing arcs of this vertex) or, in case two nodes are given as parameter, remove the arc between them, if it exists.

This operation takes time \(O(|I_v| + |I_t|)\), where \(I_x\) is the set of vertices incident to \(x\), to remove the single arc between \(v\) and \(v\). For a single vertex \(v\), it takes time \(O(\sum _{y: \text {there is some arc between $v$ and $y$ or $y$ and $v$}} |I_y|)\).

Parameters: 1. v The single vertex or the tail vertex 2. t The head vertex

An arc is changed so that instead of connecting self.tail and self.head, it now connects a new head and tail. The difference to first disconnecting and then reconnecting is that all fields of the arc (other than head and tail, of course), will be “moved along”. Reconnecting an arc in the same way as before has no effect.

If there is already an arc at the new position, fields of the to-be-reconnected arc overwrite fields of the original arc. This is especially dangerous with a syntactic digraph, so do not reconnect arcs of the syntactic digraph (which you should not do anyway).

The arc object may no longer be valid after a reconnect, but the operation returns the new arc object.

This operation needs the time of a disconnect (if necessary).

Parameters: 1. arc The original arc object 2. tail The new tail vertex 3. head The new head vertex

Returns: 1. The new arc object connecting them (either newly created or already existing)

Collapse a set of vertices into a single vertex

Often, algorithms will wish to treat a whole set of vertices “as a single vertex”. The idea is that a new vertex is then inserted into the graph, and this vertex is connected to all vertices to which any of the original vertices used to be connected.

The collapse method takes an array of to-be-collapsed vertices as well as a vertex. First, it will store references to the to-be-collapsed vertices inside the vertex. Second, we iterate over all arcs of the to-be-collapsed vertices. If this arc connects a to-be-collapsed vertex with a not-to-be-collapsed vertex, the not-to-be-collapsed vertex is connected to the collapse vertex. Additionally, the arc is stored at the vertex.

Note that the collapse vertex will be added to the graph if it is not already an element. The collapsed vertices will not be removed from the graph, so you must remove them yourself, if necessary.

A collapse vertex will store the collapsed vertices so that you can call expand later on to “restore” the vertices and arcs that were saved during a collapse. This storage is not local to the graph in which the collapse occurred.

Parameters: 1. collapse_vertices An array of to-be-collapsed vertices 2. collapse_vertex The vertex that represents the collapse. If missing, a vertex will be created automatically and added to the graph. 3. vertex_fun This function is called for each to-be-collapsed vertex. The parameters are the collapse vertex and the to-be-collapsed vertex. May be nil. 4. arc_fun This function is called whenever a new arc is added between rep and some other vertex. The arguments are the new arc and the original arc. May be nil.

Returns: 1. The new vertex that represents the collapsed vertices.

Expand a previously collapsed vertex.

If you have collapsed a set of vertices in a graph using collapse, you can expand this set once more using this method. It will add all vertices that were previously removed from the graph and will also reinstall the deleted arcs. The collapse vertex is not removed.

Parameters: 1. vertex A to-be-expanded vertex that was previously returned by collapse. 2. vertex_fun A function that is called once for each reinserted vertex. The parameters are the collapse vertex and the reinstalled vertex. May be nil. 3. arc_fun A function that is called once for each reinserted arc. The parameter is the arc and the vertex. May be nil.

Invokes the sync method for all arcs of the graph.

See also: Arc:sync()

Computes a string representation of this graph including all nodes and edges. The syntax of this representation is such that it can be used directly in TikZ’s graph syntax.

Returns: 1. self as string.

A Vertex instance models a node of graphs. Each Vertex object can be an element of any number of graphs (whereas an Arc object can only be an element of a single graph).

When a vertex is added to a digraph g, two tables are created in the vertex’ storage: An array of incoming arcs (with respect to g) and an array of outgoing arcs (again, with respect to g). The fields are managed by the Digraph class and should not be modified directly.

Note that a Vertex is an abstraction of TikZ nodes; indeed the objective is to ensure that, in principle, we can use them independently of TeX. For this reason, you will not find any references to tex inside a Vertex; this information is only available in the syntactic digraph.

One important aspect of vertices are its anchors – a concept well familiar for users of TikZ, but since we need to abstract from TikZ, a separate anchor management is available inside the graph drawing system. It works as follows:

First of all, every vertex has a path, which is a (typically closed) line around the vertex. The display system will pass down the vertex’ path to the graph drawing system and this path will be stored as a Path object in the path field of the vertex. This path lives in a special “local” coordinate system, that is, all coordinates of this path should actually be considered relative to the vertex’ pos field. Note that the path is typically, but not always, “centered” on the origin. A graph drawing algorithm should arrange the vertices in such a way that the origins in the path coordinate systems are aligned.

To illustrate the difference between the origin and the vertex center, consider a tree drawing algorithm in which a node root has three children a, b, and g. Now, if we were to simply center these three letters vertically and arrange them in a line, the letters would appear to “jump up and down” since the height of the three letters are quite different. A solution is to shift the letters (and, thus, the paths of the vertices) in such a way that in all three letters the baseline of the letters is exactly at the origin. Now, when a graph drawing algorithm aligns these vertices along the origins, the letters will all have the same baseline.

Apart from the origin, there may be other positions in the path coordinate system that are of interest – such as the center of the vertex. As mentioned above, this need not be the origin and although a graph drawing algorithm should align the origins, edges between vertices should head toward these vertex centers rather that toward the origins. Other points of interest might be the “top” of the node.

All points of special interest are called “anchors”. The anchor method allows you to retrieve them. By default, you always have access to the center anchor, but other anchors may or may not be available also, see the anchor method for details.

Alphabetical method summary:

function Vertex.new (values)

function Vertex:anchor (anchor)

function Vertex:boundingBox ()

Create a new vertex. The initial parameter allows you to setup some initial values.

Usage:

Parameters: 1. initial Values to override default node settings. The following are permissible:

pos Initial position of the node. name The name of the node. It is optional to define this. path A Path object representing the vertex’s hull. anchors A table of anchors. options An options table for the vertex. animations An array of generated animation attributes. shape A string describing the shape. If not given, "none" is used. kind A kind like "node" or "dummy". If not given, "dummy" is used.

Returns: 1. A newly allocated node.

Returns a bounding box of a vertex.

Returns: 1. min_x The minimum \(x\) value of the bounding box of the path

Returns: 1. min_y The minimum \(y\) value

Returns: 1. max_x

Returns: 1. max_y

Returns: 1. center_x The center of the bounding box

Returns: 1. center_y

Returns an anchor position in a vertex. First, we try to look the anchor up in the vertex’s anchors table. If it is not found there, we test whether it is one of the direction strings north, south east, and so on. If so, we consider a line from the center of the node to the position on the bounding box that corresponds to the given direction (so south east would be the lower right corner). We intersect this line with the vertex’s path and return the result. Finally, if the above fails, we try to consider the anchor as a number and return the intersection of a line starting at the vertex’s center with the number as its angle and the path of the vertex.

Parameters: 1. anchor An anchor as detailed above

Returns: 1. A coordinate in the vertex’s local coordinate system (so add the pos field to arrive at the actual position). If the anchor was not found, nil is returned

An arc is a light-weight object representing an arc from a vertex in a graph to another vertex. You may not create an Arc by yourself, which is why there is no new method, arc creation is done by the Digraph class.

Every arc belongs to exactly one graph. If you want the same arc in another graph, you need to newly connect two vertices in the other graph.

You may read the head and tail fields, but you may not write them. In order to store data for an arc, use Storage objects.

Between any two vertices of a graph there can be only one arc, so all digraphs are always simple graphs. However, in the specification of a graph (the syntactic digraph), there might be multiple edges between two vertices. This means, in particular, that an arc has no options field. Rather, it has several optionsXxxx functions, that will search for options in all of the syntactic edges that “belong” to an edge.

In order to set options of the edges, you can set the generated_options field of an arc (which is nil by default), see the declare_parameter_sequence function for the syntax. Similar to the path field below, the options set in this table are written back to the syntactic edges during a sync.

Finally, there is also an animations field, which, similarly to the generated_options, gets written back during a sync when it is not nil.

In detail, the following happens: Even though an arc has a path, generated_options, and animations fields, setting these fields does not immediately set the paths of the syntactic edges nor does it generate options. Indeed, you will normally want to setup and modify the path field of an arc during your algorithm and only at the very end, “write it back” to the multiple syntactic edges underlying the graph. For this purpose, the method sync is used, which is called automatically for the ugraph and digraph of a scope as well as for spanning trees.

The bottom line concerning the path field is the following: If you just want a straight line along an arc, just leave the field as it is (namely, nil). If you want to have all edges along a path to follow a certain path, set the path field of the arc to the path you desire (typically, using the setPolylinePath or a similar method). This will cause all syntactic edges underlying the arc to be set to the specified path. In the event that you want to set different paths for the edges underlying a single arc differently, set the path fields of these edges and set the path field of the arc to nil. This will disable the syncing for the arc and will cause the edge paths to remain untouched.

Alphabetical method summary:

function Arc:eventIndex ()

function Arc:headAnchorForArcPath ()

function Arc:optionsAccumulated (option, accumulator, only_aligned)

function Arc:optionsArray (option)

function Arc:options (option, only_aligned)

function Arc:pointCloud ()

function Arc:setPolylinePath (coordinates)

function Arc:spanPriority ()

function Arc:sync ()

function Arc:syntacticTailAndHead ()

function Arc:tailAnchorForArcPath ()

Get an array of options of the syntactic edges corresponding to an arc.

An arc in a digraph is typically (but not always) present because there are one or more edges in the syntactic digraph between the tail and the head of the arc or between the head and the tail.

Since for every arc there can be several edges present in the syntactic digraph, an option like length may have been given multiple times for the edges corresponding to the arc.

If your algorithm gets confused by multiple edges, try saying a:options(your_option). This will always give the “most sensible” choice of the option if there are multiple edges corresponding to the same arc.

Parameters: 1. option A string option like "length".

Returns: 1. A table with the following contents:

1. It is an array of all values the option has for edges corresponding to self in the syntactic digraph. Suppose, for instance, you write the following:

copy
graph {
tail -- [length=1] head, % multi edge 1
tail -- [length=3] head, % mulit edge 2
head -- [length=8] tail, % multi edge 3
tail -- head, % multi edge 4
head -- [length=7] tail, % multi edge 5
tail -- [length=2] head, % multi edge 6
}


Suppose, furthermore, that length has been setup as an edge option. Now suppose that a is the arc from the vertex tail to the vertex head. Calling a:optionsArray('length') will yield the array part {1,3,2,8,7}. The reason for the ordering is as follows: First come all values length had for syntactic edges going from self.tail to self.head in the order they appear in the graph description. Then come all values the options has for syntactic edges going from self.head to self.tail. The reason for this slightly strange behavior is that many algorithms do not really care whether someone writes a --[length=1] b or b --[length=1] a; in both cases they would “just” like to know that the length is 1.

2. There is field called aligned, which is an array storing the actual syntactic edge objects whose values can be found in the array part of the returned table. However, aligned contains only the syntactic edges pointing “in the same direction” as the arc, that is, the tail and head of the syntactic edge are the same as those of the arc. In the above example, this array would contain the edges with the comment numbers 1, 2, and 6.

Using the length of this array and the fact that the “aligned” values come first in the table, you can easily iterate over the option’s values of only those edges that are aligned with the arc:

copy
local a = g:arc(tail.head) -- some arc
local opt = a:optionsArray('length')
local sum = 0
for i=1,#opt.aligned do
sum = sum + opt[i]
end


3. There is a field called anti_aligned, which is an array containing exactly the edges in the array part of the table not aligned with the arc. The numbering start at 1 as usual, so the \(i\)th entry of this table corresponds to the entry at position \(i + \verb !#opt.aligned!\) of the table.

Returns the first option, that is, the first entry of Arc:optionsArray(option). However, if the only_aligned parameter is set to true and there is no option with any aligned syntactic edge, nil is returned.

Parameters: 1. option An option 2. only_aligned If true, only aligned syntactic edges will be considered.

Returns: 1. The first entry of the optionsArray

Get an accumulated value of an option of the syntactic edges corresponding to an arc.

Parameters: 1. option The option of interest 2. accumulator A function taking two values. When there are more than one syntactic edges corresponding to self for which the option is set, this function will be called repeatedly for the different values. The first time it will be called for the first two values. Next, it will be called for the result of this call and the third value, and so on. 3. only_aligned A boolean. If true, only the aligned syntactic edges will be considered.

Returns: 1. If the option is not set for any (aligned) syntactic edges corresponding to self, nil is returned. If there is exactly one edge, the value of this edge is returned. Otherwise, the result of repeatedly applying the accumulator function as described above.

The result is cached, repeated calls will not invoke the accumulator function again.

Usage: Here is typical usage:

Compute the syntactic head and tail of an arc. For this, we have a look at the syntactic digraph underlying the arc. If there is at least once syntactic edge going from the arc’s tail to the arc’s head, the arc’s tail and head are returned. Otherwise, we test whether there is a syntactic edge in the other direction and, if so, return head and tail in reverse order. Finally, if there is no syntactic edge at all corresponding to the arc in either direction, nil is returned.

Returns: 1. The syntactic tail

Returns: 1. The syntactic head

Compute the point cloud.

Returns: 1. This method will return the “point cloud” of an arc, which is an array of all points that must be rotated and shifted along with the endpoints of an edge.

Compute an event index for the arc.

Returns: 1. The lowest event index of any edge involved in the arc (or nil, if there is no syntactic edge).

The span collector

This method returns the top (that is, smallest) priority of any edge involved in the arc.

The priority of an edge is computed as follows:

• 1. If the option "span priority" is set, this number will be used.

• 2. If the edge has the same head as the arc, we lookup the key
  "span priority " .. edge.direction. If set, we use this value.

• 3. If the edge has a different head from the arc (the arc is “reversed” with respect to the syntactic edge), we lookup the key "span priority reversed " .. edge.direction. If set, we use this value.

• 4. Otherwise, we use priority 5.

Returns: 1. The priority of the arc, as described above.

Sync an Arc with its syntactic edges with respect to the path and generated options. It causes the following to happen: If the path field of the arc is nil, nothing happens with respect to the path. Otherwise, a copy of the path is created. However, for every path element that is a function, this function is invoked with the syntactic edge as its parameter. The result of this call should now be a Coordinate, which will replace the function in the Path.

You use this method like this:

Next, similar to the path, the field generated_options is considered. If it is not nil, then all options listed in this field are appended to all syntactic edges underlying the arc.

Note that this function will automatically be called for all arcs of the ugraph, the digraph, and the spanning_tree of an algorithm by the rendering pipeline.

This method returns a “coordinate factory” that can be used as the coordinate of a moveto at the beginning of a path starting at the tail of the arc. Suppose you want to create a path starting at the tail vertex, going to the coordinate \((10,10)\) and ending at the head vertex. The trouble is that when you create the path corresponding to this route, you typically do not know where the tail vertex is going to be. Even if that has already been settled, you will still have the problem that different edges underlying the arc may wish to start their paths at different anchors inside the tail vertex. In such cases, you use this method to get a function that will, later on, compute the correct position of the anchor as needed.

Here is the code you would use to create the above-mentioned path:

Normally, however, you will not write code as detailed as the above and you would just write instead of the last three lines:

See Arc:tailAnchorForArcPath.

Setup the path field of an arc in such a way that it corresponds to a sequence of straight line segments starting at the tail’s anchor and ending at the head’s anchor.

Parameters: 1. coordinates An array of Coordinates through which the line will go through.

An Edge is a “syntactic” connection between two vertices that represents a connection present in the syntactic digraph. Unlike an Arc, Edge objects are not controlled by the Digraph class. Also unlike Arc objects, there can be several edges between the same vertices, namely whenever several such edges are present in the syntactic digraph.

In detail, the relationship between arcs and edges is as follows: If there is an Edge between two vertices \(u\) and \(v\) in the syntactic digraph, there will be an Arc from \(u\) to \(v\) and the array syntactic_edges of this Arc object will contain the Edge object. In particular, if there are several edges between the same vertices, all of these edges will be part of the array in a single Arc object.

Edges, like arcs, are always directed from a tail vertex to a head vertex; this is true even for undirected vertices. The tail vertex will always be the vertex that came first in the syntactic specification of the edge, the head vertex is the second one. Whether an edge is directed or not depends on the direction of the edge, which may be one of the following:

• 1. "->"

• 2. "--"

• 3. "<-"

• 4. "<->"

• 5. "-!-"

Alphabetical method summary:

function Edge.new (values)

function Edge:headAnchorForEdgePath ()

function Edge:setPolylinePath (coordinates)

function Edge:tailAnchorForEdgePath ()

Create a new edge. The initial parameter allows you to setup some initial values.

Usage:

Parameters: 1. initial Values to override defaults. –

Returns: 1. A new edge object.

This method returns a “coordinate factory” that can be used as the coordinate of a moveto at the beginning of a path starting at the tail of the arc. Suppose you want to create a path starting at the tail vertex, going to the coordinate \((10,10)\) and ending at the head vertex. The trouble is that when you create the path corresponding to this route, you typically do not know where the tail vertex is going to be. In this case, you use this method to get a function that will, later on, compute the correct position of the anchor as needed.

Note that you typically do not use this function, but use the corresponding function of the Arc class. Use this function only if there are multiple edges between two vertices that need to be routed differently.

Here is the code you would use to create the above-mentioned path:

As for the Arc class, you can also setup a polyline more easily:

See Arc:tailAnchorForArcPath.

Setup the path field of an edge in such a way that it corresponds to a sequence of straight line segments starting at the tail’s anchor and ending at the head’s anchor.

Parameters: 1. coordinates An array of Coordinates through which the line will go through.

A collection is essentially a subgraph of a graph, that is, a “collection” of some nodes and some edges of the graph. The name “collection” was chosen over “subgraph” since the latter are often thought of as parts of a graph that are rendered in a special way (such as being surrounded by a rectangle), while collections are used to model such diverse things as hyperedges, sets of vertices that should be on the same level in a layered algorithm, or, indeed, subgraphs that are rendered in a special way.

Collections are grouped into “kinds”. All collections of a given kind can be accessed by algorithms through an array whose elements are the collections. On the display layer, for each kind a separate key is available to indicate that a node or an edge belongs to a collection.

Collections serve two purposes: First, they can be seen as “hints” to graph drawing algorithms that certain nodes and/or edges “belong together”. For instance, collections of kind same layer are used by the Sugiyama algorithm to group together nodes that should appear at the same height of the output. Second, since collections are also passed back to the display layer in a postprocessing step, they can be used to render complicated concepts such as hyperedges (which are just collections of nodes, after all) or subgraphs.

Alphabetical method summary:

function Collection.new (t)

function Collection:childrenOfKind (kind)

function Collection:children ()

function Collection:descendantsOfKind (kind)

function Collection:descendants ()

Creates a new collection. You should not call this function directly, it is called by the interface classes.

Parameters: 1. t A table of initial values. The field t.kind must be a nonempty string.

Returns: 1. The new collection

A collection can have any number of child collections, which are collections nested inside the collection. You can access the array of these children through this method. You may not modify the array returned by this function.

Returns: 1. The array of children of self.

This method works like the children method. However, the tree of collections is, conceptually, contracted by considering only these collections that have the kind given as parameter. For instance, if self has a child collection of a kind different from kind, but this child collection has, in turn, a child collection of kind kind, this latter child collection will be included in the array – but not any of its child collections.

Parameters: 1. kind The collection kind to which the tree of collections should be restricted.

Returns: 1. The array of children of self in this contracted tree.

The descendants of a collection are its children, plus their children, plus their children, and so on.

Returns: 1. An array of all descendants of self. It will be in preorder.

The descendants of a collection of the given kind.

Parameters: 1. kind A collection kind.

Returns: 1. An array of all descendants of self of the given kind.

A Coordinate models a position on the drawing canvas.

It has an x field and a y field, which are numbers that will be interpreted as TeX points (1/72.27th of an inch). The \(x\)-axis goes right and the \(y\)-axis goes up.

Alphabetical method summary:

function Coordinate.__add (a,b)

function Coordinate.__div (a,b)

function Coordinate.__mul (a,b)

function Coordinate.__sub (a,b)

function Coordinate.__unm (a)

function Coordinate.boundingBox (array)

function Coordinate.new (x,y)

function Coordinate:apply (t)

function Coordinate:clone ()

function Coordinate:moveTowards (c,f)

function Coordinate:normalized ()

function Coordinate:normalize ()

function Coordinate:norm ()

function Coordinate:scale (s)

function Coordinate:shiftByCoordinate (c)

function Coordinate:shift (a,b)

function Coordinate:unshiftByCoordinate (c)

function Coordinate:unshift (a,b)

Creates a new coordinate.

Parameters: 1. x The \(x\) value 2. y The \(y\) value

Returns: 1. A coordinate

Creates a new coordinate that is a copy of an existing one.

Returns: 1. A new coordinate at the same location as self

Apply a transformation matrix to a coordinate, see pgf.gd.lib.Transform for details.

Parameters: 1. t A transformation.

Shift a coordinate

Parameters: 1. a An \(x\) offset 2. b A \(y\) offset

“Unshift” a coordinate (which is the same as shifting by the inversed coordinate; only faster).

Parameters: 1. a An \(x\) offset 2. b A \(y\) offset

Like shift, only for coordinate parameters.

Parameters: 1. c Another coordinate. The \(x\)- and \(y\)-values of self are increased by the \(x\)- and \(y\)-values of this coordinate.

Like unshift, only for coordinate parameters.

Parameters: 1. c Another coordinate.

Moves the coordinate a fraction of f along a straight line to c.

Parameters: 1. c Another coordinate 2. f A fraction

Scale a coordinate by a factor

Parameters: 1. s A factor.

Add two coordinates, yielding a new coordinate. Note that it will be a lot faster to call shift, whenever this is possible.

Parameters: 1. a A coordinate 2. b A coordinate

Subtract two coordinates, yielding a new coordinate. Note that it will be a lot faster to call unshift, whenever this is possible.

Parameters: 1. a A coordinate 2. b A coordinate

The unary minus (mirror the coordinate against the origin).

Parameters: 1. a A coordinate

The multiplication operator. Its effect depends on the parameters: If both are coordinates, their dot-product is returned. If exactly one of them is a coordinate and the other is a number, the scalar multiple of this coordinate is returned.

Parameters: 1. a A coordinate or a scalar 2. b A coordinate or a scalar

Returns: 1. The dot product or scalar product.

The division operator. Returns the scalar division of a coordinate by a scalar.

Parameters: 1. a A coordinate 2. b A scalar (not equal to zero).

Returns: 1. The scalar product or a * (1/b).

The norm function. Returns the norm of a coordinate.

Parameters: 1. a A coordinate

Returns: 1. The norm of the coordinate

Normalize a vector: Ensure that it has length 1. If the vector used to be the 0-vector, it gets replaced by (1,0).

Normalized version of a vector: Like normalize, only the result is returned in a new vector.

Returns: 1. Normalized version of self

Compute a bounding box around an array of coordinates

Parameters: 1. array An array of coordinates

Returns: 1. min_x The minimum \(x\) value of the bounding box of the array

Returns: 1. min_y The minimum \(y\) value

Returns: 1. max_x

Returns: 1. max_y

Returns: 1. center_x The center of the bounding box

Returns: 1. center_y

A Path models a path in the plane.

Following the PostScript/pdf/svg convention, a path consists of a series of path segments, each of which can be closed or not. Each path segment, in turn, consists of a series of Bézier curves and straight line segments; see Section 14 for an introduction to paths in general.

A Path object is a table whose array part stores Coordinate objects, strings, and functions that describe the path of the edge. The following strings are allowed in this array:

• • "moveto" The line’s path should stop at the current position and then start anew at the next coordinate in the array.

• • "lineto" The line should continue from the current position to the next coordinate in the array.

• • "curveto" The line should continue form the current position with a Bézier curve that is specified by the next three Coordinate objects (in the usual manner).

• • "closepath" The line’s path should be “closed” in the sense that the current subpath that was started with the most recent moveto operation should now form a closed curve.

Instead of a Coordinate, a Path may also contain a function. In this case, the function, when called, must return the Coordinate that is “meant” by the position. This allows algorithms to add coordinates to a path that are still not fixed at the moment they are added to the path.

Alphabetical method summary:

function Path.new (initial)

function Path:appendArcTo (target,radius_or_center,clockwise,trans)

function Path:appendArc (start_angle,end_angle,radius,trans)

function Path:appendClosepath ()

function Path:appendCurveto (a,b,c,d,e,f)

function Path:appendLineto (x,y)

function Path:appendMoveto (x,y)

function Path:boundingBox ()

function Path:clear ()

function Path:clone ()

function Path:coordinates ()

function Path:cutAtBeginning (index, time)

function Path:cutAtEnd (index, time)

function Path:intersectionsWith (path)

function Path:makeRigid ()

function Path:pad (padding)

function Path:reversed ()

function Path:shiftByCoordinate (x)

function Path:shift (x,y)

function Path:transform (t)

Creates an empty path.

Parameters: 1. initial A table containing an array of strings and coordinates that constitute the path. Coordinates may be given as tables or as a pair of numbers. In this case, each pair of numbers is converted into one coordinate. If omitted, a new empty path is created.

Returns: 1. A empty Path

Creates a copy of a path.

Returns: 1. A copy of the path

Returns the path in reverse order.

Returns: 1. A copy of the reversed path

Transform all points on a path.

Parameters: 1. t A transformation, see pgf.gd.lib.Transform. It is applied to all Coordinate objects on the path.

Shift all points on a path.

Parameters: 1. x An \(x\)-shift 2. y A \(y\)-shift

Shift by all points on a path.

Parameters: 1. x A coordinate

Makes the path empty.

Appends a moveto to the path.

Parameters: 1. x A Coordinate or function or, if the y parameter is not nil, a number that is the \(x\)-part of a coordinate. 2. y The \(y\)-part of the coordinate.

Appends a lineto to the path.

Parameters: 1. x A Coordinate or function, if the y parameter is not nil, a number that is the \(x\)-part of a coordinate. 2. y The \(y\)-part of the coordinate.

Appends a closepath to the path.

Appends a curveto to the path. There can be either three coordinates (or functions) as parameters (the two support points and the target) or six numbers, where two consecutive numbers form a Coordinate. Which case is meant is detected by the presence of a sixth non-nil parameter.

Makes a path “rigid”, meaning that all coordinates that are only given as functions are replaced by the values these functions yield.

Returns an array of all coordinates that are present in a path. This means, essentially, that all strings are filtered out.

Returns: 1. An array of all coordinate objects on the path.

Returns a bounding box of the path. This will not necessarily be the minimal bounding box in case the path contains curves because, then, the support points of the curve are used for the computation rather than the actual bounding box of the path.

If the path contains no coordinates, all return values are 0.

Returns: 1. min_x The minimum \(x\) value of the bounding box of the path

Returns: 1. min_y The minimum \(y\) value

Returns: 1. max_x

Returns: 1. max_y

Returns: 1. center_x The center of the bounding box

Returns: 1. center_y

Computes all intersections of a path with another path and returns them as an array of coordinates. The intersections will be sorted “along the path self”. The implementation uses a divide-and-conquer approach that should be reasonably fast in practice.

Parameters: 1. path Another path

Returns: 1. Array of all intersections of path with self in the order they appear on self. Each entry of this array is a table with the following fields:

• index The index of the segment in self where the intersection occurs. • time The “time” at which a point traveling along the segment from its start point to its end point. • point The point itself.

Shorten a path at the beginning. We are given the index of a segment inside the path as well as a point in time along this segment. The path is now shortened so that everything before this segment and everything in the segment before the given time is removed from the path.

Parameters: 1. index The index of a path segment. 2. time A time along the specified path segment.

Shorten a path at the end. This method works like cutAtBeginning, only the path is cut at the end.

Parameters: 1. index The index of a path segment. 2. time A time along the specified path segment.

“Pads” the path. The idea is the following: Suppose we stroke the path with a pen whose width is twice the value padding. The outer edge of this stroked drawing is now a path by itself. The path will be a bit longer and “larger”. The present function tries to compute an approximation to this resulting path.

The algorithm used to compute the enlarged part does not necessarily compute the precise new path. It should work correctly for polyline paths, but not for curved paths.

Parameters: 1. padding A padding distance.

Returns: 1. The padded path.

Appends an arc (as in the sense of “a part of the circumference of a circle”) to the path. You may optionally provide a transformation matrix, which will be applied to the arc. In detail, the following happens: We first invert the transformation and apply it to the start point. Then we compute the arc “normally”, as if no transformation matrix were present. Then we apply the transformation matrix to all computed points.

Parameters: 1. start_angle The start angle of the arc. Must be specified in degrees. 2. end_angle the end angle of the arc. 3. radius The radius of the circle on which this arc lies. 4. trans A transformation matrix. If nil, the identity matrix will be assumed.

Appends a clockwise arc (as in the sense of “a part of the circumference of a circle”) to the path such that it ends at a given point. If a transformation matrix is given, both start and end point are first transformed according to the inverted transformation, then the arc is computed and then transformed back.

Parameters: 1. target The point where the arc should end. 2. radius_or_center If a number, it is the radius of the circle on which this arc lies. If it is a Coordinate, this is the center of the circle. 3. clockwise If true, the arc will be clockwise. Otherwise (the default, if nothing or nil is given), the arc will be counter clockwise. 4. trans A transformation matrix. If missing, the identity matrix is assumed.

The Transform table provides a set of static methods for creating and handling canvas transformation matrices. Such a matrix is actually just an array of six numbers. The idea is that “applying” an array a, b, c, d, e, f a vector \((x,y)\) will yield the new vector \((ax+by+e,cx+dy+f)\). For details on how such matrices work, see Section 108.2.1

Alphabetical method summary:

function Transform.concat (a,b)

function Transform.invert (t)

function Transform.new_rotation (angle)

function Transform.new_scaling (x_scale, y_scale)

function Transform.new_shift (x,y)

function Transform.new (a,b,c,d,x,y)

Creates a new transformation array.

Parameters: 1. a First component 2. b Second component 3. c Third component 4. d Fourth component 5. x The x shift 6. y The y shift

Returns: 1. A transformation object.

Creates a new transformation object that represents a shift.

Parameters: 1. x An x-shift 2. y A y-shift

Returns: 1. A transformation object

Creates a new transformation object that represents a rotation.

Parameters: 1. angle An angle

Returns: 1. A transformation object

Creates a new transformation object that represents a scaling.

Parameters: 1. x The horizontal scaling 2. y The vertical scaling (if missing, the horizontal scaling is used)

Returns: 1. A transformation object

Concatenate two transformation matrices, returning the new one.

Parameters: 1. a The first transformation 2. b The second transformation

Returns: 1. The transformation representing first applying b and then applying a.

Inverts a transformation matrix.

Parameters: 1. t The transformation.

Returns: 1. The inverted transformation

A storage is an object that, as the name suggests, allows you to “store stuff concerning objects.” Basically, it behaves like table having weak keys, which means that once the objects for which you “store stuff” go out of scope, they are also removed from the storage. Also, you can specify that for each object of the storage you store a table. In this case, there is no need to initialize this table for each object; rather, when you write into such a table and it does not yet exist, it is created “on the fly”.

The typical way you use storages is best explained with the following example: Suppose you want to write a depth-first search algorithm for a graph. This algorithm might wish to mark all nodes it has visited. It could just say v.marked = true, but this might clash with someone else also using the marked key. The solution is to create a marked storage. The algorithm can first say

and then say

to mark its objects. The marked storage object does not need to be created locally inside a function, you can declare it as a local variable of the whole file; nevertheless, the entries for vertices no longer in use get removed automatically. You can also make it a member variable of the algorithm class, which allows you make the information about which objects are marked globally accessible.

Now suppose the algorithm would like to store even more stuff in the storage. For this, we might use a table and can use the fact that a storage will automatically create a table when necessary:

Again, once v goes out of scope, both it and the info table will removed.

Alphabetical method summary:

function Storage.newTableStorage ()

function Storage.new ()

Create a new storage object.

Returns: 1. A new Storage instance.

Create a new storage object which will install a table for every entry automatically.

Returns: 1. A new Storage instance.

Events are used to communicate “interesting” events from the parser to the graph drawing algorithms.

As a syntactic description of some graph is being parsed, vertices, arcs, and a digraph object representing this graph get constructed. However, even though syntactic annotations such as options for the vertices and arcs are attached to them and can be accessed through the graph objects, some syntactic information is neither represented in the digraph object nor in the vertices and the arcs. A typical example is a “missing” node in a tree: Since it is missing, there is neither a vertex object nor arc objects representing it. It is also not a global option of the graph.

For these reasons, in addition to the digraph object itself, additional information can be passed by a parser to graph drawing algorithms through the means of events. Each Event consists of a kind field, which is just some string, and a parameters field, which stores additional, kind-specific information. As a graph is being parsed, a string of events is accumulated and is later on available through the events field of the graph drawing scope.

The following events are created during the parsing process by the standard parsers of TikZ:

• node When a node of the input graph has been parsed and a Vertex object has been created for it, an event with kind node is created. The parameter of this event is the just-created vertex.

  The same kind of event is used to indicate “missing” nodes. In this case, the parameters field is nil.

• edge When an edge of the input graph has been parsed, an event is created of kind edge. The parameters field will store an array with two entries: The first is the Arc object whose syntactic_edges field stores the edge. The second is the index of the edge inside the syntactic_edges field.

• begin Signals the beginning of a group, which will be ended with a corresponding end event later on. The parameters field will indicate the kind of group. Currently, only the string "descendants" is used as parameters, indicating the start of several nodes that are descendants of a given node. This information can be used by algorithms for reconstructing the input structure of trees.

• end Signals the end of a group begun by a begin event earlier on.

Alphabetical method summary:

function Event.new (values)

Create a new event object

Parameters: 1. initial Initial fields of the new event.

Returns: 1. The new object

This class controls the running of graph drawing algorithms on graphs. In particular, it performs pre- and posttransformations and also invokes the collapsing of sublayouts.

You do not call any of the methods of this class directly, the whole class is included only for documentation purposes.

Before an algorithm is applied, a number of transformations will have been applied, depending on the algorithm’s preconditions field:

• • connected

  If this property is set for an algorithm (that is, in the declare statement for the algorithm the predconditions field has the entry connected=true set), then the graph will be decomposed into connected components. The algorithm is run on each component individually.

• • tree

  When set, the field spanning_tree of the algorithm will be set to a spanning tree of the graph. This option implies connected.

• • loop_free

  When set, all loops (arcs from a vertex to itself) will have been removed when the algorithm runs.

• • at_least_two_nodes

  When explicitly set to false (this precondition is true by default), the algorithm will even be run if there is only a single vertex in the graph.

Once the algorithm has run, the algorithm’s postconditions will be processed:

• • upward_oriented

  When set, the algorithm tells the layout pipeline that the graph has been laid out in a layered manner with each layer going from left to right and layers at a whole going upwards (positive \(y\)-coordinates). The graph will then be rotated and possibly swapped in accordance with the grow key set by the user.

• • fixed

  When set, no rotational postprocessing will be done after the algorithm has run. Usually, a graph is rotated to meet a user’s orient settings. However, when the algorithm has already “ideally” rotated the graph, set this postcondition.

In addition to the above-described always-present and automatic transformations, users may also specify additional pre- and posttransformations. This happens when users install additional algorithms in appropriate phases. In detail, the following happens in order:

• 1. If specified, the graph is decomposed into connected components and the following steps are applied to each component individually.

• 2. All algorithms in the phase stack for the phase preprocessing are applied to the component. These algorithms are run one after the other in the order they appear in the phase stack.

• 3. If necessary, the spanning tree is now computed and rotational information is gathered.

• 4. The single algorithm in phase main is called.

• 5. All algorithms in the phase stack for the phase edge routing are run.

• 6. All algorithms in the phase stack for phase postprocessing are run.

• 7. Edge syncing, orientation, and anchoring are applied.

If sublayouts are used, all of the above (except for anchoring) happens for each sublayout.

Alphabetical method summary:

function LayoutPipeline.anchor (graph, scope)

function LayoutPipeline.cutEdges (graph)

function LayoutPipeline.decompose (digraph)

function LayoutPipeline.orient (rotation_info, postconditions, graph, scope)

function LayoutPipeline.packComponents (syntactic_digraph, components)

function LayoutPipeline.prepareBoundingBoxes (rotation_info, adjusted_bb, graph, vertices)

function LayoutPipeline.prepareRotateAround (postconditions, graph)

This function is called internally to perform the graph anchoring procedure described in Section 28.4. These transformations are always performed.

Parameters: 1. graph A graph 2. scope The scope

This method tries to determine in which direction the graph is supposed to grow and in which direction the algorithm will grow the graph. These two pieces of information together produce a necessary rotation around some node. This rotation is returned in a table.

Note that this method does not actually cause a rotation to happen; this is left to other method.

Parameters: 1. postconditions The algorithm’s postconditions. 2. graph An undirected graph

Returns: 1. A table containing the computed information.

Compute growth-adjusted node sizes.

For each node of the graph, compute bounding box of the node that results when the node is rotated so that it is in the correct orientation for what the algorithm assumes.

The “bounding box” actually consists of the fields

• • sibling_pre,

• • sibling_post,

• • layer_pre, and

• • layer_post,

which correspond to “min x”, “min y”, “min y”, and “max y” for a tree growing up.

The computation of the “bounding box” treats a centered circle in a special way, all other shapes are currently treated like a rectangle.

Parameters: 1. rotation_info The table computed by the function prepareRotateAround 2. packing_storage A storage in which the computed distances are stored. 3. graph An graph 4. vertices An array of to-be-prepared vertices inside graph

Performs a post-layout orientation of the graph by performing the steps documented in Section 28.5.

Parameters: 1. rotation_info The info record computed by the function prepareRotateAround. 2. postconditions The algorithm’s postconditions. 3. graph A to-be-oriented graph. 4. scope The graph drawing scope.

This internal function is called to decompose a graph into its components. Whether or not this function is called depends on whether the precondition connected is set for the algorithm class and whether the componentwise key is used.

Parameters: 1. graph A to-be-decomposed graph

Returns: 1. An array of graph objects that represent the connected components of the graph.

This internal function packs the components of a graph. See Section 28.7 for details.

Parameters: 1. graph The graph 2. components A list of components

Cut the edges. This function handles the “cutting” of edges. The idea is that every edge is a path going from the center of the from node to the center of the target node. Now, we intersect this path with the path of the start node and cut away everything before this intersection. Likewise, we intersect the path with the head node and, again, cut away everything following the intersection.

These cuttings are not done if appropriate options are set.

The Hints class provides a way for graph drawing algorithms to communicate certain possibilities concerning the routing of edges to edge routing algorithms. This partly decouples the choice of the vertex positioning algorithms from the choice of edge routing algorithm. For instance, for a simple necklace routing, it is unclear whether the edges on the necklace should be routing “along the necklace” or not. Thus, necklace routing algorithms will “hint” that a necklace is present and only when the necklace routing algorithm is selected will these hints lead to actual bending of edges.

For each kind of hint, there are methods in this class for creating the hints and other methods for reading them. Hints are always local to the ugraph.

Alphabetical method summary:

function Hints.addNecklaceCircleHint (ugraph, necklace, center, clockwise)

function Hints.getNecklaceHints (ugraph)

Adds a necklace hint. In this case, the hint indicates that the given sequence of vertices lie on a circle.

The idea is that an algorithm may specify that in a given graph certain sequences of nodes form a “necklace”, which is typically a circle. There may be more than one necklace inside a given graph. For each necklace, whenever an arc connects subsequent nodes on the necklace, they get bend in such a way that they lie follow the path of the necklace. If an arc lies on more than one necklace, the “last one wins”.

Parameters: 1. ugraph The ugraph to which this hint is added 2. necklace The sequence of vertices that form the necklace. If the necklace is closed, the last vertex must equal the first one. 3. center If provided, must be Coordinate that specifies the center of the circle on which the vertices lie. If not provided, the origin is assumed. 4. clockwise If true, the vertices are in clockwise order, otherwise in counter-clockwise order.

Gets the necklace hints.

This function will return an array whose entries are necklace hints. Each entry in the array has a necklace field, which is the field passed to the addNecklaceXxxx methods. For a circle necklace, the center and clockwise fields will be set. (Other necklaces are not yet implemented.)

Parameters: 1. ugraph The ugraph for which the necklace hints are requested.

Returns: 1. The array of necklaces as described above.

This class provides the interface between the graph drawing system and algorithms. Another class, InterfaceToDisplay, binds the display layers (like TikZ or a graph drawing editor) to the graph drawing system “from the other side”.

The functions declared here can be used by algorithms to communicate with the graph drawing system, which will usually forward the “requests” of the algorithms to the display layers in some way. For instance, when you declare a new parameter, this parameter will become available on the display layer.

Alphabetical method summary:

function InterfaceToAlgorithms.addHandler (test, handler)

function InterfaceToAlgorithms.createEdge (algorithm, tail, head, init)

function InterfaceToAlgorithms.createVertex (algorithm, init)

function InterfaceToAlgorithms.declare (t)

function InterfaceToAlgorithms.findVertexByName (name)

Adds a handler for the declare function. The declare command is just a “dispatcher” to one of many possible declaration functions. Which function is used, depends on which fields are present in the table passed to declare. For each registered handler, we call the test function. If it returns neither nil nor false, the handler field of this handler is called. If it returns true, the handler immediately finishes. Otherwise, the next handler is tried.

This function is the “work-horse” for declaring things. It allows you to specify on the algorithmic layer that a key “is available” for use on the display layer. There is just one function for handling all declarations in order to make the declarations easy-to-use since you just need to import a single function:

You can now use declare it as follows: You pass it a table containing information about the to-be-declared key. The table must have a field key whose value is unique and must be a string. If the value of key is, say, "foo", the parameter can be set on the display layer such as, say, the TikZ layer, using /graph drawing/foo. Here is a typical example of how a declaration is done:

Inlining Documentation. The three keys summary, documentation and examples are intended for the display layer to give the users information about what the key does. The summary should be a string that succinctly describes the option. This text will typically be displayed for instance as a “tool tip” or in an option overview. The documentation optionally provides more information and should be typeset using TeX. The examples can either be a single string or an array of strings. Each should be a TikZ example demonstrating how the key is used.

Note that you can take advantage of the Lua syntax of enclosing very long multi-line strings in [[ and ]]. As a bonus, if the summary, documentation, or an example starts and ends with a quote, these two quotes will be stripped. This allows you to enclose the whole multi-line string (additionally) in quotes, leading to better syntax highlighting in editors.

External Documentation. It is sometimes more desirable to put the documentation of a key into an external file. First, this makes the code leaner and, thus, faster to read (both for humans and for computers). Second, for C code, it is quite inconvenient to have long strings inside a C file. In such cases, you can use the documentation_in field:

The some_filename must be the name of a Lua file that will be read “on demand”, that is, whenever someone tries to access the documentation, summary, or examples field of the key, this file will be loaded using require. The file should then use pgf.gd.doc to install the missing information in the keys.

The Use Field. When you declare a key, you can provide a use field. If present, you must set it to an array of small tables which have two fields:

• • key This is the name of another key or a function.

• • value This is either a value (like a string or a number) or a function or nil.

Here is an example:

The effect of a use field is the following: Whenever the key is encountered on the option stack, the key is first handled normally. Then, we iterate over all elements of the use array. For each element, we perform the action as if the key of the array had been set explicitly to the value given by the value field. If the value is a function, we pass a different value to the key, namely the result of applying the function to the value originally passed to the original key. Here is a typical example:

Just like the value, the key itself can also be a function. In this case, the to-be-used key is also computed by applying the function to the value passed to the original key.

As mentioned at the beginning, declare is a work-horse that will call different internal functions depending on whether you declare a parameter key or a new algorithm or a collection kind. Which kind of declaration is being done is detected by the presence of certain fields in the table passed to t. The different kind of possible declarations are documented in the declare_... functions. Note that these functions are internal and cannot be called from outside; you must use the declare function.

Parameters: 1. t A table contain the field key and other fields as described.

This function is called by declare for “normal parameter keys”, which are all keys for which no special field like algorithm or layer is declared. You write

When an author writes my node[electrical charge=5-3] in the description of her graph, the object vertex corresponding to the node my node will have a field options attached to it with

The type field does not refer to Lua types. Rather, these types are sensible types for graph drawing and they are mapped by the higher layers to Lua types. In detail, the following types are available:

• • number A dimensionless number. Will be mapped to a normal Lua number. So, when the author writes foo=5*2, the foo key of the options field of the corresponding object will be set to 10.0.

• • length A “dimension” in the sense of TeX (a number with a dimension like cm attached to it). It is the job of the display layer to map this to a number in “TeX points”, that is, to a multiple of \(1/72.27\)th of an inch.

• • time A “time” in the sense of \pgfparsetime. Examples are 6s or 0.1min or 6000ms, all of which will map to 6.

• • string Some text. Will be mapped to a Lua string.

• • canvas coordinate A position on the canvas. Will be mapped to a model.Coordinate.

• • boolean A Boolean value.

• • raw Some to-be-executed Lua text.

• • direction Normally, an angle; however, the special values of down, up, left, right as well as the directions north, north west, and so on are also legal on the display layer. All of them will be mapped to a number. Furthermore, a vertical bar (|) will be mapped to -90 and a minus sign (-) will be mapped to 0.

• • hidden A key of this type “cannot be set”, that is, users cannot set this key at all. However algorithms can still read this key and, through the use of alias, can use the key as a handle to another key.

• • user value The key stores a Lua user value (userdata). Such keys can only be set from C since user values cannot be created in Lua (let alone in TikZ).

If the type field is missing, it is automatically set to "string".

A parameter can have an initial value. This value will be used whenever the parameter has not been set explicitly for an object.

A parameter can have a default value. This value will be used as the parameter value whenever the parameter is explicitly set, but no value is provided. For a key of type "boolean", if no default is provided, "true" will be used automatically.

A parameter can have an alias field. This field must be set to the name of another key or to a function. Whenever you access the current key and this key is not set, the alias key is tried instead. If it is set, its value will be returned (if the alias key has itself an alias set, this is tried recursively). If the alias is not set either and neither does it have an initial value, the initial value is used. Note that in case the alias has its initial field set, the initial value of the current key will never be used.

The main purpose of the current key is to allow algorithms to introduce their own terminology for keys while still having access to the standard keys. For instance, the OptimalHierarchyLayout class uses the name layerDistance for what would be called level distance in the rest of the graph drawing system. In this case, we can declare the layerDistance key as follows:

Inside the algorithm, we can write ...options.layerDistance and will get the current value of the level distance unless the layerDistance has been set explicitly. Indeed, we might set the type to hidden to ensure that only the level distance can and must set to set the layerDistance.

Note that there is a difference between alias and the use field: Suppose we write

Here, when you say layerDistance=1cm, the level distance itself will be modified. When the level distance is set, however, the layerDistance will not be modified.

If the alias is a function, it will be called with the option table as its parameter. You can thus say things like

As a special courtesy to C code, you can also set the key alias_function_string, which allows you to put the function into a string that is read using loadstring.

(You cannot call this function directly, it is included for documentation purposes only.)

Parameters: 1. t The table originally passed to declare.

This function is called by declare for “algorithm keys”. These keys are normally used without a value as in just \graph[tree layout], but you can optionally pass a value to them. In this case, this value must be the name of a phase and the algorithm of this phase will be set (and not the default phase of the key), see the description of phases below for details.

Algorithm keys are detected by the presence of the field algorithm in the table t passed to declare. Here is an example of how it is used:

The algorithm field expects either a table or a string as value. If you provide a string, then require will be applied to this string to obtain the table; however, this will happen only when the key is actually used for the first time. This means that you can declare (numerous) algorithms in a library without these algorithms actually being loaded until they are needed.

Independently of how the table is obtained, it will be “upgraded” to a class by setting its __index field and installing a static new function (which takes a table of initial values as argument). Both these settings will only be done if they have not yet been performed.

Next, you can specify the fields preconditions and postconditions. The preconditions are a table that tell the graph drawing engine what kind of graphs your algorithm expects. If the input graph is not of this kind, it will be automatically transformed to meet this condition. Similarly, the postconditions tell the engine about properties of your graph after the algorithm has run. Again, additional transformations may be performed.

You can also specify the field phase. This tells the graph drawing engine which “phase” of the graph drawing process your option applies to. Each time you select an algorithm later on through use of the algorithm’s key, the algorithm for this phase will be set; algorithms of other phases will not be changed. For instance, when an algorithm is part of the spanning tree computation, its phase will be "spanning tree computation" and using its key does not change the main algorithm, but only the algorithm used during the computation of a spanning tree for the current graph (in case this is needed by the main algorithm). In case the phase field is missing, the phase main is used. Thus, when no phase field is given, the key will change the main algorithm used to draw the graph.

Later on, the algorithm set for the current phase can be accessed through the special algorithm_phases field of options tables. The algorithm_phases table will contain two fields for each phase for which some algorithm has been set: One field is the name of the phase and its value will be the most recently set algorithm (class) set for this phase. The other field is the name of the phase followed by " stack". It will contain an array of all algorithm classes that have been set for this key with the most recently at the end.

The following example shows the declaration of an algorithm that is the default for the phase "spanning tree computation":

The algorithm is called as follows during a run of the main algorithms:

If you set the phase_default field of t to true, the algorithm will be installed as the default algorithm for the phase. This can be done only once per phase. Furthermore, for such a default algorithm the algorithm key must be table, it may not be a string (in other words, all default algorithms are loaded immediately). Accessing the algorithm_phases table for a phase for which no algorithm has been set will result in the default algorithm and the phase stack will also contain this algorithm; otherwise the phase stack will be empty.

(You cannot call this function directly, it is included for documentation purposes only.)

Parameters: 1. t The table originally passed to declare.

This function is called by declare for “collection kinds”. They are detected by the presence of the field layer in the table t passed to declare. See the class Collection for details on what a collection and a collection kind is.

The key field of the table t passed to this function is both the name of the to-be-declared collection kind as well as the key that is used on the display layer to indicate that a node or edge belongs to a collection.

The Display Layer. Let us first have a look at what happens on the display layer: A key t.key is setup on the display layer that, when used inside a graph drawing scope, starts a new collection of the specified kind. “Starts” means that all nodes and edges mentioned in the rest of the current option scope will belong to a new collection of kind t.key.

you can say on the TikZ layer

In this case, the nodes a, b, c will belong to a collection of kind hyper. The nodes b, c, and d will (also) belong to another collection of the same kind hyper. You can nest collections; in this case, nodes will belong to several collections.

The effect of declaring a collection kind on the algorithm layer it, first of all, that scope.collections will have a field named by the collection kind. This field will store an array that contains all collections that were declared as part of the graph. For instance, collections.hyper will contain all hyperedges, each of which is a table with the following fields: The vertices and edges fields each contain arrays of all objects being part of the collection. The sub field is an array of “subcollections”, that is, all collections that were started inside another collection. (For the collection kinds hyper and same layer this makes no sense, but subgraphs could, for instance, be nested.)

Rendering of Collections. For some kinds of collections, it makes sense to render them, but only after the graph drawing algorithm has run. For this purpose, the binding layer will use a callback for each collection kind and each collection, see the Binding class for details. Suppose, for instance, you would like hyperedges to be rendered. In this case, a graph drawing algorithm should iterate over all collections of type hyper and compute some hints on how to render the hyperedge and store this information in the generated_options table of the hyperedge. Then, the binding layer will ask the display layer to run some some code that is able to read key–value pairs passed to it (which are the key–value pairs of the generated_options table) and use this information to nicely draw the hyperedge.

The number t.layer determines in which order the different collection kinds are rendered.

The last parameter, the layer number, is used to specify the order in which the different collection kinds are rendered. The higher the number, the later the collection will be rendered. Thus, if there is a collection kind with layer number 10 and another with layer number 20, all collections of the first kind will be rendered first, followed by all collections of the second kind.

Collections whose layer kinds are non-negative get rendered after the nodes and edges have already been rendered. In contrast, collections with a negative layer number get shown “below” the nodes and edges.

(You cannot call this function directly, it is included for documentation purposes only.)

Parameters: 1. t The table originally passed to declare.

Finds a node by its name. This method should be used by algorithms for which a node name is specified in some option and, thus, needs to be converted to a vertex object during a run of the algorithm.

Parameters: 1. name A node name

Returns: 1. The vertex of the given name in the syntactic digraph or nil.

Generate a new vertex in the syntactic digraph. Calling this method allows algorithms to create vertices that are not present in the original input graph. Using the graph drawing coroutine, this function will pass back control to the display layer in order to render the vertex and, thereby, create precise size information about it.

Note that creating new vertices in the syntactic digraph while the algorithm is already running is a bit at odds with the notion of treating graph drawing as a series of graph transformations: For instance, when a new vertex is created, the graph will (at least temporarily) no longer be connected; even though an algorithm may have requested that it should only be fed connected graphs. Likewise, more complicated requirements like insisting on the graph being a tree also cannot be met.

For these reasons, the following happens, when a new vertex is created using the function:

• 1. The vertex is added to the syntactic digraph.

• 2. It is added to all layouts on the current layout stack. When a graph drawing algorithm is run, it is not necessarily run on the original syntactic digraph. Rather, a sequence / stack of nested layouts may currently be processed and the vertex is added to all of them.

• 3. The vertex is added to both the digraph and the ugraph of the current algorithm.

Parameters: 1. algorithm An algorithm for whose syntactic digraph the node should be added 2. init A table of initial values for the node that is passed to Binding:createVertex, see that function for details.

Returns: 1. The newly created node

Generate a new edge in the syntactic digraph. This method is quite similar to createVertex and has the same effects with respect to the edge: The edge is added to the syntactic digraph and also to all layouts on the layout stack. Furthermore, appropriate edges are added to the digraph and the ugraph of the algorithm currently running.

Parameters: 1. algorithm An algorithm for whose syntactic digraph the node should be added 2. tail A syntactic tail vertex 3. head A syntactic head vertex 4. init A table of initial values for the edge.

The following fields are useful for init:

• init.direction If present, a direction for the edge. Defaults to ”–”. • init.options If present, some options for the edge. • init.generated_options A table that is passed back to the display layer as a list of key-value pairs in the syntax of declare_parameter.

\usegdlibrary{examples} % LaTeX and plain TeX
\usegdlibrary[examples] % ConTeXt

This package presents some examples of how different aspects of the graph drawing engine can be used. In particular, the algorithms of this package are not really meant to be used to layout graphs (although they can be used, in principle); rather you are invited to have a look at their implementation and to adapt them to your needs.

This algorithm is the “Hello World” of graph drawing. The algorithm arranges nodes in a circle (without paying heed to the sizes of the nodes or to the edges). In order to “really” layout nodes in a circle, use simple necklace layout; the present layout is only intended to demonstrate how much (or little) is needed to implement a graph drawing algorithm.

On the display layer (TikZ, that is) the algorithm can now immediately be employed; you just need to say \usegdlibrary{examples.SimpleDemo} at the beginning somewhere.

This algorithm shows how edges can be created by an algorithm. For its job, the algorithm uses the function createEdge, which can be called during the run of the algorithm to create edges in the syntactic graph. The algorithm first does exactly the same as the simple demo layout, then it creates an edge for every node where the new edge to option is set. You will see in the code how this option is declared and how we use it to look up a vertex in the graph by its name.

And the algorithm:

Next comes the declaration of the new option new edge to:

Finally, the algorithm’s code:

This option takes the name of a vertex. An edge leading to this vertex is added to the syntactic digraph.

This algorithm demonstrates how an algorithm can generate new nodes. The input graph should just consist of some nodes (without edges) and each node should have a probability key set. The nodes will then be arranged in a line (as siblings) and a Huffman tree will be constructed “above” these nodes. For the construction of the Huffman tree, new nodes are created and connected.

The file starts with some setups and declarations:

Next comes a setup, where we create the working list of vertices that changes as the Huffman coding method proceeds: