This post is part of a series of articles about PGF/TikZ and its new graph drawing features on which I am working as part of my graduate thesis.

In the previous post I wrote about motivations for using computer tools to draw graphs. I described the problems with older and current versions of PGF/TikZ. The essence of that post was to show that the current PGF/TikZ syntax for graphs is too verbose and that manual node positioning is impractical. I concluded by explaining that a solution for this is in development. 

In this post I will present some of the graph-related features of the upcoming version of PGF/TikZ. As mentioned in part 1, these are:

  • A new, drastically simplified graph syntax that is as powerful as the verbose old syntax.
  • A couple of basic node positioning (or: placement) strategies such as circular placement or grid placement.
  • The new graph drawing subsystem for automatic graph drawing algorithms based on the Lua scripting language.

As part of my graduate thesis I implemented a set of algorithms for force-directed and layered drawings of graphs. These work remarkably well with a lot of graphs that I collected from lecture notes, books and research papers. I will present these algorithms in a separate post, the third and last of this series.

The new, simplified graph syntax supported by TikZ

TikZ is the graphics language that comes bundled with PGF. In the upcoming version it includes a new syntax for specifying and drawing graphs. First, let us remember the old syntax though (copied from the previous post):

\usemodule[tikz]
\starttext
\starttikzpicture[every path/.style={>=latex},every node/.style={draw,circle}]
  \node            (a) at (0,0)  { A };
  \node            (b) at (2,0)  { B };
  \node            (c) at (2,-2) { C };
  \node[rectangle] (d) at (0,-2) { D };
  \draw[->] (a) edge (b);
  \draw[->] (a) edge (c);
  \draw[->] (b) edge (c);
  \draw[<-] (c) edge (d);
\stoptikzpicture
\stoptext

Remember the problems: manual node positioning, verbose declaration of nodes and edges. Here’s the result once again:

Now, let’s take a look at the new syntax using the same example:

\usemodule[tikz]
\usetikzlibrary[graphs]
\starttext
\startTEXpage
\starttikzpicture
  \graph [no placement,nodes={draw,circle},edges={>=latex}] {
    A [at={(0,0)}] -> {
      B [at={(2,0)}] -> C [at={(2,-2)}],
      C -> D [at={(0,-2)},rectangle]
    }
  };
\stoptikzpicture
\stopTEXpage
\stoptext

The main differences compared to the old notation are:

  • The graph is declared with the \graph macro which executes all TikZ options in the /graphs scope, making the definition of options possible that are not visible to other elements in the TikZ environment (such as nodes={} instead of every node/.style={}).
  • Nodes no longer need to be declared with the \node macro. Instead, simply typing their value is often sufficient. Name names may contain spaces as well as special characters, so things like x_i -> x_j are possible too (in combination with the math nodes graph option these nodes would be typeset just like in a math environment). A third notation is name_text, where name is the internal name to be used when defining edges and text is a string that is displayd inside the node. Again, this text may include special characters and spaces e.g. for formulas.
  • The manual positioning with the at option is a bit more verbose but there are ways around this as you will learn soon.
  • Note that TikZ options can be passed to nodes as well as edges by using the [] syntax.
  • Nodes can be combined in chains (e.g. A -> B -> C) and groups (e.g. { A, B }). Groups are particularly interesting as edges entering or leaving a group are (often, not always) duplicated and re-routed to/from the individual nodes in the group. Also, groups can be assigned TikZ options as well, allowing all nodes or edges in the group to be altered at once (e.g. by changing the color of the nodes A and B to red with { [red] A, B }).

This new syntax has plenty of other features, some of which are still in development (e.g. yesterday we discussed a new syntax for edge labels). All of these features are explained along with helpful examples in about 50 extra pages in the updated manual that we will ship with the next release.

Basic node positioning strategies

In the above example, I chose to set no placement to avoid automatic node positioning. In the upcoming version, TikZ supports various placement strategies including:

  • Cartesian placement (from left to right, with nodes in the same group being placed at the same level),
  • circular placement (nodes are placed on a circle),
  • grid placement (nodes are placed in a N * M grid where the number of columns or rows can be configured by the user), and
  • no placement (for manual positioning)

Here is an example using circular placement and grid placement:

\usemodule[tikz]
\usetikzlibrary[graphs]
\starttext
\startTEXpage
\starttikzpicture
  \startscope
    \graph [circular placement,nodes={draw,circle}] {
      a, b, c, d, e, f,
    };
  \stopscope
  \startscope[xshift=2cm,yshift=1cm]
    \graph [grid placement,n=6,nodes={draw}] {
      a, b, c, d, e, f,
    };
  \stopscope
\stoptikzpicture
\stopTEXpage
\stoptext

There are various options for these placement strategies. Together with a set of standard graphs (complete graphs, complete bipartite graphs, circles, grids etc.) that can be created using keywords such as subgraph K_n or subgraph Grid_n, these already cover a number of use cases.

The original problem, however, remains: how to find a good layout for arbitrary trees, state machines, automata, flow charts and graphs compiled from large sets of data? This is where the new graph drawing subsystem of PGF/TikZ comes into play.

The Lua-based graph drawing subsystem of PGF

Lua is a powerful, light-weight scripting language often used to extend complex software systems such as computer games. It combines elements of procedural, functional and object-oriented programming and is similar to other modern languages like Ruby or Python in that regard. The major differences are that it ships a rudimentary standard library only and that only a few basic data types are provided by default. All other complex data types need to be built on top of the table data type which is a mixture of an array and a hash table.

LuaTeX is an enhanced distribution of the TeX typesetting system that embeds Lua as a scripting and extension language. One of its features is that there is a TeX macro to execute Lua code directly from TeX: \directlua. This can be used to process TeX data with Lua scripts and pass data between these two layers (TeX and Lua). 

Combining the power of LuaTeX with algorithms available for automatic graph positioning (or: graph drawing) might be a good idea. At least that’s what Till —- author/maintainer of PGF/TikZ and supervisor of my undergraduate and graduate theses —- and a group of students thought before they went on to implement a graph drawing interface between TikZ, PGF and Lua. Later when I started my graduate thesis I picked this up and continued to improve and complete it.

Today, this graph drawing subsystem is closed to being stable. It offers TikZ options to select and configure the graph drawing algorithms available in the PGF repository as well as data structures and algorithms to help with implementing new drawing algorithms.

Implementing a new algorithm is as simple as creating a .lua file in the PGF tree and implementing a single function (although I am about to change this so that a class needs to be implemented rather than a function). After that, users can select your algorithm and if you create another file in the PGF tree, you can even specify graph, node and edge parameters for them to configure.

Creating a new algorithm

Again, in order to create a new graph drawing algorithm, all you need to do is create a .lua file in the PGF tree. The graph drawing subsystem resides in the generic/pgf/graphdrawing directory which is divided into two subdirectories called algorithms and core. The core directory contains all the internals and data structures while the algorithms directory holds all the graph drawing algorithms. The algorithms tree is further subdivided into directories for the different classes of algorithms, namely force (for force-based algorithms), layered (for layered drawing algorithms), trees (for graph drawing algorithms related to trees) and misc (for stuff we didn’t know how to classify it).

To demonstrate the procedure of creating a new algorithm, we are going to create a new misc algorithm by creating a file

generic/pgf/graphdrawing/algorithms/misc/pgfgd-algorithm-simple-demo.lua

with the following content:

pgf.module("pgf.graphdrawing")
 
--- A trivial node placing algorithm for demonstration purposes.
--
-- All nodes are positioned on a circle with a user-defined radius.
--
function drawGraphAlgorithm_simple_demo(graph)
  local radius = tonumber(graph:getOption("/graph drawing/simple demo/radius"))
  local nodeCount = table.count_pairs(graph.nodes)
  local alpha = (2 * math.pi) / nodeCount
  local i = 0
  for node in table.value_iter(graph.nodes) do
    -- the interesting part...
    local node_radius = tonumber(node:getOption('/graph drawing/simple demo/node radius') or radius)
    node.pos:set{x = node_radius * math.cos(i * alpha)}
    node.pos:set{y = node_radius * math.sin(i * alpha)}
    i = i + 1
  end
end

Let us quickly walk through the code to get an understanding of the concepts involved:

  • The first line tells PGF to import the graph drawing Lua module. This makes all data structures and functions of the graph drawing available in the script.
  • The function drawGraphAlgorithm_simple_demo() is the entry point to our algorithm. In PGF/TikZ the algorithm will be known by a more readable name: simple demo. The Lua file and the function have to be named consistently to make this work.
  • The function takes a single argument called graph. This is an instance of the Graph class shipped with PGF/TikZ. It holds nodes and edges and provides a number of useful methods to manipulate them, iterate over them etc.
  • Our algorithm places nodes in a circle with a user-defined radius. Thus, in the first line of the algorithm, the /graph drawing/simple demo/radius option is retrieved from the graph object. This option is defined in a different file but we’ll get to that later.
  • Once we have the radius, we can count the nodes, iterate over all of them and place them on the circle where they belong. Note that all values are assumed to be in points, so if the desired radius is 1cm, the value of radius would be something like 28.35.

Basically, everything a graph drawing algorithm is supposed to do is take a graph and set the positions of all nodes to something that makes sense. (This is not entirely correct. Some algorithms may also want to bend edges so that they don’t cross nodes etc. but this is not covered here.)

Defining algorithm parameters for graphs, nodes and edges

I promised to talk about how to define and pass parameters which will lead us to the final syntax for using the algorithm in TikZ. Each class of algorithms (force, layered, misc etc.) forms a so-called TikZ library (graphdrawing.force, graphdrawing.layered, graphdrawing.misc etc.). This way people are not forced to load everything. Instead, they can choose what to include and what not to include in their TeX document. For misc algorithms, this library is defined in the following file:

generic/pgf/graphdrawing/algorithms/misc/pgflibrarygraphdrawing.misc.code.tex

This is where graph, node and edge parameters are defined. For our simple algorithm this would look as follows:

\pgfgddeclarealgorithmkey{simple demo}{simple demo}{algorithm=simple demo}
 
\pgfgdset{
  simple demo/.cd,
  radius/.graph parameter=evaluate math expression,
  radius/.parameter initial=4cm,
  node radius/.node parameter=evaluate math expression
}

The above lines define:

  • A graph drawing algorithm called simple demo. The first argument for \pgfgddeclarealgorithmkey is the name of the algorithm in PGF/TikZ. The second argument is the algorithm family. Sometimes different algorithms take the same parameters and this way the parameters can be defined once and be re-used in all of these algorithms. We do not need this in our simple case and so the family key is set to the algorithm name. The third and last parameter can be used to execute any kind of code allowed in PGF keys. We want to set the graph drawing algorithm to simple demo, which will make PGF/TikZ load our Lua file. We could also set default values for parameters here.
  • Inside the \pgfgdset call we first switch into the algorithm family. Then, we define two parameters: one to be passed to the \graph macro and the other to be passed to nodes using the [] option syntax. Both parameters may be complex mathematical expressions (with optional units). By using evaluate math expression, we leave it to PGF/TikZ to resolve the expression and convert it into points. The general rule to follow here is to leave all parsing to PGF/TikZ and pass values down to the algorithm that are ready to be used in Lua. The radius parameter has a default value set to 4cm which is automatically passed to the algorithm unless the user defines a custom value in the description of the graph.

This is it. There are other ways to define algorithms, families of algorithms and algorithm parameters and those will be covered in detail in the updated PGF manual. In order to understand the basic idea of the graph drawing subsystem, the above information should be sufficient.

Using the new algorithm

Having written a simple graph drawing algorithm the next, obvious question is: how to use it? An brief explanation follows, again using a basic example:

\usemodule[tikz]
\usetikzlibrary[graphs,graphdrawing,graphdrawing.misc]
\starttext
\startTEXpage
\starttikzpicture
  \graph [simple demo={radius=1cm},nodes={draw,circle}] {
    a -> b -> c -> d [simple demo={node radius=2cm}] -> e -> a
  };
\stoptikzpicture
\stopTEXpage
\stoptext

Again, we have to load the graphs library for the graph syntax. We also need to load the graphdrawing library which will pull in graph drawing subsystem. Finally, we need to load graphdrawing.misc to have access to the simple demo algorithm and its parameters.

We select the algorithm by typing \graphs [simple demo]. The part where the radius is set to 1cm can be omitted if the default value proves to be fine. The node d is altered to have a different radius by setting the corresponding node parameter to 2cm. Here is the result:

And that’s it.

Conclusion

With this graph drawing framwork in place we have plenty of opportunities to implement various kinds of graph drawing algorithms and experiment with new ideas. Creating an algorithm and making it available in TikZ is easy once you get used to it, making PGF/TikZ one of the most flexible and developer-friendly graph drawing systems out there.

In the next post

In my next article I will demonstrate the algorithms that were implemented as part of my graduate thesis. These algorithms are comparable with those shipped with Graphviz and Mathematica and are useful for many graphs and work well with grids, symmetric graphs, flow charts, flow networks and state machines/automata. Stay tuned!