summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/doc/pgfmanual-en-gd-algorithms-in-c.tex
diff options
context:
space:
mode:
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.tex864
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.