diff options
Diffstat (limited to 'graphics/pgf/base/doc/pgfmanual-en-gd-algorithms-in-c.tex')
-rw-r--r-- | graphics/pgf/base/doc/pgfmanual-en-gd-algorithms-in-c.tex | 864 |
1 files changed, 864 insertions, 0 deletions
diff --git a/graphics/pgf/base/doc/pgfmanual-en-gd-algorithms-in-c.tex b/graphics/pgf/base/doc/pgfmanual-en-gd-algorithms-in-c.tex new file mode 100644 index 0000000000..305752fc44 --- /dev/null +++ b/graphics/pgf/base/doc/pgfmanual-en-gd-algorithms-in-c.tex @@ -0,0 +1,864 @@ +% Copyright 2018 by Till Tantau +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Free Documentation License. +% +% See the file doc/generic/pgf/licenses/LICENSE for more details. + + +\section{Writing Graph Drawing Algorithms in C} +\label{section-algorithms-in-c} + +\noindent{\emph{by Till Tantau}} +\bigskip +\ifluatex +\else + This section of the manual can only be typeset using Lua\TeX. + \expandafter\endinput +\fi + +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. + +\begin{quote} + \emph{Warning:} Graph drawing algorithms written in C can be incredibly + fast if you use the facilities of C correctly. \emph{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 \textsc{ogdf} framework), but + it is \emph{much} harder to get right than writing Lua code. + + Bottom line, \emph{you really should be using this method only if it is + really necessary (namely, when Lua code is simply not fast enough).} +\end{quote} + +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. + + +\subsection{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 Lua\TeX$\dots$) is able to +link C libraries at runtime -- provided a strict regime of rules is adhered to: +% +\begin{enumerate} + \item 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. + \item If it finds such a shared library, Lua(\TeX) will try to link this + library dynamically at runtime. + \item 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). + \item 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. + \item 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. +\end{enumerate} + +For each of the above points, there are some bells and whistles: +% +\begin{enumerate} + \item Lua\TeX\ looks at slightly inconvenient places for shared libraries: + By default, (currently, 2013) it looks in a |lib| subdirectory of the + directory containing the Lua\TeX\ 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. + \item Certain versions of Lua\TeX\ have a broken handling of filenames of + libraries written in C. The TL2013 version of Lua\TeX, 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. + \item On certain platforms, the support for dynamic linking against + Lua\TeX\ 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. + \item 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. + \item The registration process of C functions is somewhat tricky and + changes from Lua version to Lua version. + \item C functions that get called by Lua must follow all sorts of tricky + rules in order to communicate with Lua correctly. +\end{enumerate} + +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 +% +\begin{itemize} + \item C, see Section~\ref{section-gd-c}, + \item C++, see Section~\ref{section-gd-c++}, + \item Open Graph Drawing Framework, see + Section~\ref{section-gd-ogdf-interface}. +\end{itemize} + + +\subsection{Writing Graph Drawing Algorithms in C} +\label{section-gd-c} + +\subsubsection{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: +% +\begin{codeexample}[code only, tikz syntax=false] +#include <pgf/gd/interface/c/InterfaceFromC.h> +#include <math.h> + +static void fast_hello_world (pgfgd_SyntacticDigraph* graph) { + ... +} +\end{codeexample} + +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 \emph{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: +% +\begin{codeexample}[code only, tikz syntax=false] +static void fast_hello_world (pgfgd_SyntacticDigraph* graph) { + double angle = 6.28318530718 / graph->vertices.length; + double radius = pgfgd_tonumber(graph->options, "fast simple demo radius"); + + int i; + for (i = 0; i < graph->vertices.length; i++) { + pgfgd_Vertex* v = graph->vertices.array[i]; + v->pos.x = cos(angle*i) * radius; + v->pos.y = sin(angle*i) * radius; + } +} +\end{codeexample} + +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: +% +\begin{codeexample}[code only, tikz syntax=false] +int luaopen_pgf_gd_examples_c_SimpleDemoC (struct lua_State *state) { + + pgfgd_Declaration* d = pgfgd_new_key ("fast simple demo layout"); + pgfgd_key_summary (d, "The C version of the hello world of graph drawing"); + pgfgd_key_algorithm (d, fast_hello_world); + pgfgd_key_add_precondition (d, "connected"); + pgfgd_key_add_precondition (d, "tree"); + pgfgd_declare (state, d) + pgfgd_free_key (d); +\end{codeexample} + +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: +% +\begin{codeexample}[code only, tikz syntax=false] +declare { + key = "fast simple demo layout", + summary = "The C version of the hello world of graph drawing", + preconditions = { + connected = true, + tree = true, + }, + algorithm = { + run = -- something magic we cannot express in Lua + } +} +\end{codeexample} + +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: +% +\begin{codeexample}[code only, tikz syntax=false] + d = pgfgd_new_key ("fast simple demo radius"); + pgfgd_key_summary (d, "A radius value for the hello world of graph drawing"); + pgfgd_key_type (d, "length"); + pgfgd_key_initial (d, "1cm"); + pgfgd_declare (state, d); + pgfgd_free_key (d); + + return 0; +} +\end{codeexample} + +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 Lua\TeX\ 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 +% +\begin{codeexample}[code only, tikz syntax=false] +require 'pgf.gd.examples.c.SimpleDemoC' +\end{codeexample} +% +or in \tikzname +% +\begin{codeexample}[code only] +\usegdlibrary {examples.c.SimpleDemoC} +\end{codeexample} + +This should cause Lua\TeX\ 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). + +\emph{Remark:} Unfortunately, the above does not work with the \TeX Live 2013 +versions of Lua\TeX\ 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 +% +\begin{codeexample}[code only, tikz syntax=false] +pgf_gd_examples_c_SimpleDemoC.so +\end{codeexample} +% +and then say +% +\begin{codeexample}[code only, tikz syntax=false] +require 'pgf_gd_examples_c_SimpleDemoC' +\end{codeexample} +% +or in \tikzname +% +\begin{codeexample}[code only] +\usegdlibrary {pgf_gd_examples_c_SimpleDemoC} +\end{codeexample} + +In future versions of Lua\TeX, 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: +% +\begin{codeexample}[code only] +\tikz \graph [fast simple demo layout, fast simple demo radius=1.25cm] +{ a -> b -> c -> d -> e -> a }; +\end{codeexample} + + +\subsubsection{Documenting Algorithms Written in C} +\label{section-gd-documenting-c-algos} + +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~\ref{section-gd-documentation-in}, 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|: +% +\begin{codeexample}[code only, tikz syntax=false] + pgfgd_key_documentation_in (d, "pgf.gd.doc.examples.SimpleDemoC"); +\end{codeexample} + +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 Lua\TeX\ binary. + +Here are typical contents of the documentation file: +% +\begin{codeexample}[code only, tikz syntax=false] +-- File pgf/gd/doc/examples/SimpleDemoC.lua +local key = require 'pgf.gd.doc'.key +local documentation = require 'pgf.gd.doc'.documentation +local summary = require 'pgf.gd.doc'.summary +local example = require 'pgf.gd.doc'.example + +key "fast simple demo layout" +documentation +[[ +This layout is used... +]] +example +[[ +\tikz \graph [fast simple example layout] +{ a -- b -- c -- d -- e; }; +]] + +key "fast simple demo radius" +documentation +[[ +The radius parameter is used to ... +]] +example +[[ +\tikz \graph [fast simple demo layout, fast simple demo radius=1.25cm] +{ a -> b -> c -> d -> e -> a }; +]] +\end{codeexample} + + +\subsubsection{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. + + +\subsection{Writing Graph Drawing Algorithms in C++} +\label{section-gd-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. + + +\subsubsection{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: +% +\begin{codeexample}[code only, tikz syntax=false] +#include <pgf/gd/interface/c/InterfaceFromC++.h> +#include <pgf/gd/interface/c/InterfaceFromC.h> + +#include <math.h> + +struct FastLayout : scripting::declarations, scripting::runner { + ... +} +\end{codeexample} + +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: +% +\begin{codeexample}[code only, tikz syntax=false] +void run () { + pgfgd_SyntacticDigraph* graph = parameters->syntactic_digraph; + + double angle = 6.28318530718 / graph->vertices.length; + double radius = parameters->option<double>("fast simple demo radius c++"); + + for (int i = 0; i < graph->vertices.length; i++) { + pgfgd_Vertex* v = graph->vertices.array[i]; + v->pos.x = cos(angle*i) * radius; + v->pos.y = sin(angle*i) * radius; + } +} +\end{codeexample} + +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 +\tikzname\ 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: +% +\begin{codeexample}[code only, tikz syntax=false] +void declare(scripting::script s) { + using namespace scripting; + + s.declare(key ("fast simple demo layout c++") + .summary ("The C++ version of the hello world of graph drawing") + .precondition ("connected") + .precondition ("tree") + .algorithm (this)); + + s.declare(key ("fast simple demo radius c++") + .summary ("A radius value for the hello world of graph drawing") + .type ("length") + .initial ("1cm")); +} +\end{codeexample} + +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: +% +\begin{codeexample}[code only, tikz syntax=false] +extern "C" int luaopen_pgf_gd_examples_c_SimpleDemoCPlusPlus (struct lua_State *state) { + scripting::script s (state); + s.declare (new FastLayout); + return 0; +} +\end{codeexample} + +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 Lua\TeX\ versions, to actually load the +library at runtime, we need to rename it to +% +\begin{codeexample}[code only, tikz syntax=false] +pgf_gd_examples_c_SimpleDemoCPlusPlus.so +\end{codeexample} +% +and then say +% +\begin{codeexample}[code only, tikz syntax=false] +require 'pgf_gd_examples_c_SimpleDemoCPlusPlus' +\end{codeexample} +% +or in \tikzname +% +\begin{codeexample}[code only] +\usegdlibrary {pgf_gd_examples_c_SimpleDemoCPlusPlus} +\end{codeexample} + +We can now use it: +% +\begin{codeexample}[code only] +\tikz \graph [fast simple demo layout c++, fast simple demo radius c++=1.25cm] +{ a -> b -> c -> d -> e -> a }; +\end{codeexample} + + +\subsubsection{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: + + +\medskip +\noindent\textbf{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 +\textsc{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 \textsc{ogdf} representation prior to the |run| method being called. The +|run| method can then access additional member variables that store the graph +representations in \textsc{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. + + +\medskip +\noindent\textbf{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 +% +\begin{codeexample}[code only, tikz syntax=false] +s.declare (key (...) + .algorithm(this) + ...); +\end{codeexample} +% +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.) + + +\medskip +\noindent\textbf{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: +% +\begin{itemize} + \item The |option_is_set| method returns |true| if the passed option has + been set \emph{and} can be cast to the type of the template. So, + |option_is_set<double>("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). + \item 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<double>("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: + % +\begin{codeexample}[code only, tikz syntax=false] +double dist; +if (parameters->option ("node distance", dist)) + ... +\end{codeexample} + + 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. + \item 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: + % +\begin{codeexample}[code only, tikz syntax=false] +class MyClass { +public: + void setMyDistance (double distance); +... +}; +... + +MyClass m; +parameters->configure_option("node distance", &MyClass::setMyDistance, m); +\end{codeexample} + % + If the option has not been set or does not have the correct type, the + member function is not called. +\end{itemize} + + +\medskip +\noindent\textbf{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 \emph{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. + + +\medskip +\noindent\textbf{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. + + +\subsection{Writing Graph Drawing Algorithms Using OGDF} +\label{section-gd-ogdf-interface} + +Built on top of the C++ interface, a small interface allows you to easily link +algorithms written for the \textsc{ogdf} (Open Graph Drawing Framework) with +graph drawing in Lua. + + +\subsubsection{The Hello World of Graph Drawing in OGDF -- From Scratch} + +We start with some startup code: +% +\begin{codeexample}[code only, tikz syntax=false] +#include <pgf/gd/ogdf/c/InterfaceFromOGDF.h> +#include <math.h> + +using namespace ogdf; +using namespace scripting; +\end{codeexample} + +Note that the interface from \textsc{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 \textsc{ogdf}: +% +\begin{codeexample}[code only, tikz syntax=false] +struct FastLayoutOGDF : declarations, ogdf_runner { + + void run () { + double angle = 6.28318530718 / graph.numberOfNodes(); + double radius = parameters->option<double>("my radius ogdf"); + + int i = 0; + for (node v = graph.firstNode(); v; v=v->succ(), i++) { + graph_attributes.x(v) = cos(angle*i) * radius; + graph_attributes.y(v) = sin(angle*i) * radius; + } + } +\end{codeexample} + +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: +% +\begin{codeexample}[code only, tikz syntax=false] + void declare(script s) { + using namespace scripting; + + s.declare(key ("fast simple demo layout ogdf") + .summary ("The OGDF version of the hello world of graph drawing") + .precondition ("connected") + .algorithm (this)); + + s.declare(key ("my radius ogdf") + .summary ("A radius value for the hello world of graph drawing") + .type ("length") + .initial ("1cm")); + } +}; +\end{codeexample} + +Finally, we need the entry point, which is also ``as usual'': +% +\begin{codeexample}[code only, tikz syntax=false] +extern "C" int luaopen_pgf_gd_examples_c_SimpleDemoOGDF (struct lua_State *state) { + script (state).declare (new FastLayoutOGDF); + return 0; +} +\end{codeexample} + +Yet again, we need to rename the resulting shared library and then say +|require| on it. We can now use it: +% +\begin{codeexample}[code only] +\tikz \graph [fast simple demo layout ogdf, my radius ogdf=1cm] +{ a -> b -> c -> d -> e -> a }; +\end{codeexample} + + +\subsubsection{The Hello World of Graph Drawing in OGDF -- Adapting Existing Classes} + +In the previous example we implemented a graph drawing algorithm using +\textsc{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: +% +\begin{codeexample}[code only, tikz syntax=false] +// File HelloWorldLayout.h +#include <ogdf/module/LayoutModule.h> + +class HelloWorldLayout : puplic ogdf::LayoutModule { +public: + + virtual void call(ogdf::GraphAttributes &GA) + { + using namespace ogdf; + + const Graph &graph = GA.constGraph(); + double angle = 6.28318530718 / graph.numberOfNodes(); + int i = 0; + for (node v = graph.firstNode(); v; v=v->succ(), i++) { + GA.x(v) = cos(angle*i) * radius; + GA.y(v) = sin(angle*i) * radius; + } + } + + void setRadius (double r) { radius = r; } + +private: + + double radius; +}; +\end{codeexample} + +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: +% +\begin{codeexample}[code only, tikz syntax=false] +void run () +{ + HelloWorldLayout layout; + parameters->configure_option("HelloWorldLayout.radius", &HelloWorldLayout::setRadius, layout); + layout.call(graph_attributes); +} +\end{codeexample} + +Next, we need to write the declarations code. This is very similar to the +``from scratch'' version: +% +\begin{codeexample}[code only, tikz syntax=false] +void declare(script s) { + using namespace scripting; + + s.declare(key ("HelloWorldLayout") + .summary ("The OGDF version of the hello world of graph drawing") + .precondition ("connected") + .algorithm (this)); + + s.declare(key ("HelloWorldLayout.radius") + .summary ("A radius value for the hello world of graph drawing") + .type ("length") + .alias ("radius")); +} +\end{codeexample} + +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 Lua\TeX. +% +\begin{codeexample}[code only, tikz syntax=false] +// File HelloWorldLayout_script.c++ + +#include <pgf/gd/ogdf/c/InterfaceFromOGDF.h> +#include <HelloWorldLayout.h> + +using namespace ogdf; +using namespace scripting; + +struct HelloWorldLayout_script : declarations, ogdf_runner { + void run () { ... see above ... } + void declare (script s) { ... see above ... } +}; + +extern "C" int luaopen_my_path_HelloWorldLayout_script (struct lua_State *state) { + script (state).declare (new HelloWorldLayout_script); + return 0; +} +\end{codeexample} + + +\subsubsection{Documenting OGDF Algorithms} + +As explained in Section~\ref{section-gd-documenting-c-algos}, 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 \textsc{ogdf} algorithms. + +I strongly recommend making use of this feature since, currently, the +documentation of many \textsc{ogdf} classes is sketchy at best and using +\tikzname\ examples seems to be a good way of explaining the effect of the +different parameters algorithms offer. + + +\subsubsection{The Interface From OGDF} + +The support for \textsc{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 \textsc{ogdf}, but I expect this to be the +case only rarely. |