The TikZ and PGF Packages
Manual for version 3.1.10

Graph Drawing

37 Writing Graph Drawing Algorithms in C¶

by Till Tantau

In the present section we have a look at how graph drawing algorithms written in the C programming language (or in C++) can be used in the graph drawing framework.

Warning: Graph drawing algorithms written in C can be incredibly fast if you use the facilities of C correctly. However, C code is much less portable than Lua code in the sense that it has to be compiled for the specific platform used by the user and that it has to be linked dynamically during a run of the TeX program. All of this in possible (and works, as demonstrated by the linking of the ogdf framework), but it is much harder to get right than writing Lua code.

Bottom line, you really should be using this method only if it is really necessary (namely, when Lua code is simply not fast enough).

In the following, I first explain how the link between TeX and C code works, in general. Then, in the subsequent sections, we go over the different kinds of programming languages and frameworks for which there is direct support for such a link.

37.1 How C and TeX Communicate¶

In order to use C code for graph drawing algorithms during a run of the TeX program, there is no need to build a new version of TeX. Rather, it is possible that C code is linked into the TeX executable at runtime. This is made possible by the fact that Lua (which part of LuaTeX\(\dots \)) is able to link C libraries at runtime – provided a strict regime of rules is adhered to:

• 1. When you say require in Lua, it will normally look for a .lua file; but it will also try to find a .so file (a shared C library) as a fallback.

• 2. If it finds such a shared library, Lua(TeX) will try to link this library dynamically at runtime.

• 3. Inside the library, there must be a function (called an entry point) with a special name (it must start with luaopen_ and it must otherwise be the path and name of the library with slashes replaced by underscores).

• 4. This function gets called by Lua, once. Its job is to setup the library so that it can be used by Lua. Mainly, this means that certain C functions get registered in such a way that Lua can call them.

• 5. At this point, control returns to Lua and, now, certain functions have become available on the Lua layer that, when called, actually invoke the C code of our linked library.

For each of the above points, there are some bells and whistles:

• 1. LuaTeX looks at slightly inconvenient places for shared libraries: By default, (currently, 2013) it looks in a lib subdirectory of the directory containing the LuaTeX executable. The logic behind is that the shared libraries depend on the specific architecture of the executable. Thus, unlike normal Lua files, the library needs to be installed “far away” from the actual package of which it is part.

• 2. Certain versions of LuaTeX have a broken handling of filenames of libraries written in C. The TL2013 version of LuaTeX, for instance, crashes when the filename of a shared library does not contain the complete path (while this works for normal file). Hopefully, this, too, will be fixed in future versions.

• 3. On certain platforms, the support for dynamic linking against LuaTeX is broken since the symbol table of the Lua library has been stripped away. Hopefully, this will be fixed soon; in the meantime, a highly fragile workaround is to link in another copy of the Lua library.

• 4. The entry point that is called by Lua requires a certain signature (it takes a Lua state as its only parameter) and must return the number of objects it returns on the Lua stack.

• 5. The registration process of C functions is somewhat tricky and changes from Lua version to Lua version.

• 6. C functions that get called by Lua must follow all sorts of tricky rules in order to communicate with Lua correctly.

Despite the above obstacles, one can use graph drawing algorithms written in C inside Lua, in principle, as follows: One loads an appropriately prepared and located C library using require and this library uses commands like declare to register its own functions into the graph drawing system so that when the run method is called, a C functions gets called instead.

Unfortunately, the above approach is extremely tedious and error-prone and it is “no fun” to access Lua data structures (such as the syntactic digraph) from C. For this reason, I have written some libraries that encapsulate (as much as possible) of this communication between C and Lua. Indeed, when you use these libraries, you can focus entirely on the graph drawing issues and you will not even notice that your code “is talking to Lua”. (Except for the name of the entry point, which is fixed to start with luaopen_ and it is impossible to change this without disrupting a lot inside Lua’s module system).

There are libraries available for simplifying the communication between the graph drawing system and graph drawing algorithms written in

• • C, see Section 37.2,

• • C++, see Section 37.3,

• • Open Graph Drawing Framework, see Section 37.4.

37.2 Writing Graph Drawing Algorithms in C¶

37.2.1 The Hello World of Graph Drawing in C¶

As our first example, as always, the “hello world” of graph drawing simply places nodes on a circle. For this, we implement a function fast_hello_world in a file SimpleDemoC.c. It starts as follows:

As we can see, we first include a special header file of a rather small library that does all the hard work of translating between Lua and C for us (InterfaceFromC). These header files reside in the c subdirectory of the pgf package. Note that we do not have to include the headers of the Lua library; indeed, you do not need access to the source of Lua to use the interface headers. As a side effect, we will, however, have to write struct lua_State instead of the more common lua_State once in our code, namely in the declaration of the entry point; but that is the only downside.

The library InterfaceFromC declares the type pgfgd_SyntacticDigraph. In a moment, we will see that we can setup a key fast simple demo layout such that when this key is used on the display layer, the function fast_hello_world gets called. When it is called, the graph parameter will be a full representation of the to-be-laid-out graph. We can access the fields of the graph and even directly modify some of its fields (in particular, we can modify the pos fields of the vertices). Here is the complete code of the algorithm:

That is all that is needed; the C library will take care of both creating the graph object as all well as of deleting it and of copying back the computed values of the pos fields of the vertices.

Our next task is to setup the key fast simple demo layout. We can (and must) also do this from C, using the following code:

The function luaopen_pgf_gd_examples_c_SimpleDemoC is the function that will be called by Lua (we will come to that). More important for us, at the moment, is the declaration of the key: We use pgfgd_new_key to create a declaration record and then fill the different fields using appropriate function calls. In particular, the call pgfgd_key_algorithm allows us to link the key with a particular C function. The pgfgd_declare will then pass the whole declaration back to Lua, so the effect of the above is essentially the same as if you had written in Lua:

In our algorithm, in addition to the above key, we also use the fast simple demo radius key, which is a simple length key. This key, too, can be declared on the C layer:

We simply add this code to the startup function above.

Now it is time to compile and link the code. For this, you must, well, compile it, link it against the library InterfaceFromC, and build a shared library out of it. Also, you must place it somewhere where LuaTeX will find it. You will find a Makefile that should be able to achieve all of this in the directory pgf/c/graphdrawing/pgf/gd/examples/c, where you will also find the code of the above example.

Now, all you need to do to use it is to write in Lua (after you have loaded the pgf.gd library, of course), would normally be the call

or in TikZ

This should cause LuaTeX to find the shared library, load it, and then call the function in that library with the lengthy name (the name is always luaopen_ followed by the path and filename with slashes replaced by underscores).

Remark: Unfortunately, the above does not work with the TeXLive 2013 versions of LuaTeX due to a bugs that causes the “replace dots by slashes” to fail. For this reason, we currently need to rename our shared library file to

and then say

or in TikZ

In future versions of LuaTeX, things should be “back to normal” in this regard. Also, the bug only concerns shared libraries; you can still create a normal Lua file with a nice name and place at a nice location and the only contents of this file is then the above require command.

Anyway, once we have loaded the shared library we can say:

37.2.2 Documenting Algorithms Written in C¶

In our above example, we included a summary with the keys in the C code. It would be even better if we added a longer documentation and some examples that show how the key works; but this is a bit impracticable in C since multi-line strings are hard to write down in C. The trick is to use the documentation_in field of a key: It allows us to specify the name of a Lua file that should be loaded (using require) to install the missing documentation fields. As explained in Section 36.2.7, this Lua file may make good use the pgf.gd.doc package. Note, also, that for keys documented in this way the documentation can easily be included in this manual through the use of the \includedocumentationof command.

In our example, we would first add the following line twice in the C code (once for each key), assuming that the documentation resides in the file pgf/gd/doc/examples/SimpleDemoC.lua:

Note that since the documentation is a normal Lua file, it will be searched in the usual places Lua files are located (in the texmf trees) and not, like the C shared library, in the special lib subdirectory of the LuaTeX binary.

Here are typical contents of the documentation file:

37.2.3 The Interface From C¶

In the above example, we already saw some of the functions from the library InterfaceFromC that translated from Lua to C for us. For a complete list of all functions available, currently please see graphdrawing/c/pgf/gd/interface/c/InterfaceFromC.h directly.

Currently, the library provides C functions to directly access all aspects of the syntactic digraph and also of the graphs computed by the preprocessing of the layout pipeline. What is missing, however, is access to the tree of (sub)layouts and to collections. Hopefully, these will be added in the future.

37.3 Writing Graph Drawing Algorithms in C++¶

Built on top of the C interface presented in the previous section, there is also a C++ interface available. It encapsulates as much of the C functions as possible in C++ classes. Thus, this interface is mostly there for convenience, it does not offer fundamentally new functionality.

37.3.1 The Hello World of Graph Drawing in C++¶

Let us have a look at how our beloved hello world of graph drawing looks in C++. Although it is still possible to put graph drawing algorithms inside functions, it is more natural in C++ to turn them into methods of a class. Thus, we start the code of SimpleDemoCPlusPlus.c++ as follows:

As can be seen, we do not only include the interface from C++, but also that from C (since, currently, not all functionality of the C library is encapsulated in C++).

The interesting part is the struct FastLayout, which will contain our algorithm (you could just as well have used a class instead of a struct). It is derived from two classes: First, from a declarations class and, secondly, from a runner class. Both of them, just like everything else from the interface, reside in the namespace scripting. This name was chosen since the main purpose of the interface is to provide “scripting facilities” to C code through the use of Lua.

We are currently interested in the class runner. This class has a virtual function run that gets called when, on the Lua side, someone has selected the algorithm represented by the class. Thus, we place our algorithm in this method:

The run method has access to the member variable parameters, which contains all sorts of information concerning the to-be-drawn graph. In particular, the syntactic_digraph field gives us access to the syntactic digraph structure that was already available in the interface from plain C. However, we can also see that a template function like option allows us to access the graph’s option table in a simple way.

As for C code, our next task is to setup a key that, when used on the TikZ layer, will run our algorithm. For this, we can use an object derived from a declarations. In our example, the FastLayout is both derived from a runner (since it contains an algorithm) and also from declarations (since it also contains the code necessary for declaring this algorithm). If you prefer, you can split this into two classes. A declarations object must override the declare method. This method gets a script object as input, which is the “representation” of Lua inside the C++ code:

For each key that we wish to declare, we call the script’s declare method once. This method takes a key object as input, which can be configured through a sequence of calls to different member functions (like summary or algorithm). Most of these member functions are rather self-explaining; only algorithm is a bit trickier: It does not take a function as input, but rather an object of type runner and it will call the run method of this object whenever the algorithm is run.

Lastly, we also need to write the entry point:

Note that it is the job of the interface classes to free the passed declarations object. For this reason, you really need to call new and cannot pass the address of a temporary object.

As before, because of the bug in some LuaTeX versions, to actually load the library at runtime, we need to rename it to

and then say

or in TikZ

We can now use it:

37.3.2 The Interface From C++¶

The header graphdrawing/c/pgf/gd/interface/c/InterfaceFromC++.h contains, as the name suggest, the interface from C++. A complete documentation is still missing, but let us go over the main ideas:

Runners. Algorithms are represented by objects of type runner. An algorithm will overwrite the run method, as we saw in the example, and it should modify the parameters of the runner object.

In addition to the run method, there are also two more virtual methods, called bridge and unbrigde. The first is called before the run method is called and the second afterwards. The idea is that another framework, such as ogdf, can implement a new class ogdf_runner that overrides these two methods in order to transform the Lua/C representation of the input graph into an ogdf representation prior to the run method being called. The run method can then access additional member variables that store the graph representations in ogdf form (or another form, depending on the framework). The unbridge method allows the framework to translate back.

Although a runner object must be created for every algorithm, an algorithm can also reside in a function. The class function_runner is a simple wrapper that turns a function into such an object.

Keys. A key object is a temporary object that is passed to the declare method of a script. It represents the table that is passed to the Lua function declare. In order to make setting its field easy, for each field name there is a corresponding function (like summary) that takes the string that should be set to this field and returns the key object once more, so that we can chain calls.

The algorithm method gets a runner object as parameter and will store a pointer to this object inside Lua. Each time the algorithm is used, this object will be used to “run” the algorithm, that is, the methods prepare, bridge, run, and unbridge will be called in that order. Since the object is reused each time, only one object is needed; but this object may not be freed prematurely. Indeed, you will normally create the object using new once and will then never delete it.

A typical idiom you may find in the code is

This code is seen inside the declare method of objects that are both declarations and runners. They register “themselves” via the above code. Note, however, that this requires that the this pointer is not a temporary object. (The typing rules of C++ make it hard for this situation to happen, but it can be achieved.)

Reading options. Once options have been declared, your C++ algorithms will wish to read them back. For this, the parameters field of a runner object provides a number of templated methods:

• • The option_is_set method returns true if the passed option has been set and can be cast to the type of the template. So, option_is_set("node distance") will return true if the node distance key has been set for the graph as a whole (currently, there is no way to read the options of a vertex or an edge from C++, use the C methods instead).

• • The option function comes in two flavours: First, it takes a single option name and just returns the option’s value. If, however, the option has not been set or has another type, some sort of null value is returned. So, option("node distance") will return the configured node distance as a double. When an option has an initial value, this call will always return a sensible value.

  The second flavour of option allows you to pass a reference to an object in which the option’s value should be stored and the function will return true if the option is set (and, thus, something was written into the reference). This is the “safest” way to access an option:

  copy
double dist;
if (parameters->option ("node distance", dist))
...


  Caution must be taken for char* options: The returned string must be explicitly freed; it will be a copy of the string stored in the Lua table.

• • The configure_option method is used to set a member of an object based on the value of a certain option. For this, you must pass a pointer to a member function that sets the member. Here is an example:

  copy
class MyClass {
public:
void setMyDistance (double distance);
...
};
...

MyClass m;
parameters->configure_option("node distance", &MyClass::setMyDistance, m);


  If the option has not been set or does not have the correct type, the member function is not called.

Factories and modules. A Lua key is normally either a Boolean, a double, or a string. However, in C++, we may also sometimes wish Lua users to configure which C function is used to achieve something. One could do this using strings or numbers and then use search algorithms or a long switch, but this would neither be flexible nor elegant.

Instead, it is possible to store factories in Lua keys. A factory is a class derived from factory that implements the virtual function make. This function will return a new object of a template type. You can store such a factory in a key.

The make method of a parameters object allows you to invoke the factory stored in a key. (If no factory is stored in it, null is returned).

The configure_module method is akin to configure_option, only the result of applying the factory is passed to the member function of the class.

Scripts. A “script” is the abstraction of the communication between Lua and C++. From C++’s point of view, the script object offers different declare methods that allow us to “make objects and function scriptable” in the sense that they can then be called and configured from Lua. The script must be initialized with a Lua state and will be bound to that state (basically, the script only stores this single pointer).

When you call declare, you either pass a single key object (which is then declared on the Lua layer) or you pass a declarations object, whose virtual declare method is then called. The declarations objects are used to bundle several declarations into a single one.

37.4 Writing Graph Drawing Algorithms Using OGDF¶

Built on top of the C++ interface, a small interface allows you to easily link algorithms written for the ogdf (Open Graph Drawing Framework) with graph drawing in Lua.

37.4.1 The Hello World of Graph Drawing in OGDF – From Scratch¶

We start with some startup code:

Note that the interface from ogdf resides in the ogdf folder, not in the interface folder.

Like in the plain C++ interface, we must now subclass the runner class and the declarations class. Also like the plain C++ interface, we can use multiple inheritance. The difference lies in the fact that we do not directly subclass form runner, but rather from ogdf_runner. This class implements the complicated “bridging” or “translation” process between the world of InterfaceFromC++ and ogdf:

As can be seen, in a subclass of ogdf_runner, the run method will have access to a member called graph and to another member called graph_attributes. These will have been setup with the graph from the Lua layer and, after the algorithm has run, the information stored in the x and y fields of the graph attributes and also the bend information of the edges will be written back automatically.

Next, we need to declare the algorithm. This is done as in the plain C++ interface:

Finally, we need the entry point, which is also “as usual”:

Yet again, we need to rename the resulting shared library and then say require on it. We can now use it:

37.4.2 The Hello World of Graph Drawing in OGDF – Adapting Existing Classes¶

In the previous example we implemented a graph drawing algorithm using ogdf for use with Lua “from scratch”. In particular, the whole algorithm was contained in the run method of our main class. In practice, however, graph drawing algorithms are typically placed in classes that “know nothing about scripting”. For instance, our hello world of graph drawing might actually be implemented like this:

Now, what we actually want to do is to “make this class scriptable”. For this, we setup a new class whose run method will produce a new HelloWorldLayout, configure it, and then run it. Here is this run method:

Next, we need to write the declarations code. This is very similar to the “from scratch” version:

Two remarks are in order: First, it is customary to name the keys for the display system the same way as the classes. Second, the different configuration options of the algorithm are named with the class name followed by the option name. This makes it clear who, exactly, is being configured. However, these keys should then also get an alias field set, which will cause an automatic forwarding of the key to something more “user friendly” like just radius.

It remains to put the above methods in a “script” file. It is this file that, when compiled, must be linked at runtime against LuaTeX.

37.4.3 Documenting OGDF Algorithms¶

As explained in Section 37.2.2, we can add external documentation to algorithms written in C and, using the documentation_in method of the key class, we can use the exact same method to document ogdf algorithms.

I strongly recommend making use of this feature since, currently, the documentation of many ogdf classes is sketchy at best and using TikZ examples seems to be a good way of explaining the effect of the different parameters algorithms offer.

37.4.4 The Interface From OGDF¶

The support for ogdf offered inside InterfaceFromOGDF.h is just the class ogdf_runner we saw already in the example. In addition, there is also a wrapper class ogdf_function_runner that allows you to wrap an algorithm implemented in a function that uses ogdf, but I expect this to be the case only rarely.