diff options
author | Karl Berry <karl@freefriends.org> | 2014-02-27 00:01:50 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2014-02-27 00:01:50 +0000 |
commit | 90ae413a94da014dbf7a6a8ab584f7c668483a5a (patch) | |
tree | 4e0528a2b2fb2004988e7fc804ea2f1354f1f5d5 /Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithms-in-c.tex | |
parent | 800cc56380d1edfe567a6a66bef13e8950eb2b0c (diff) |
pgf 3.0.0
git-svn-id: svn://tug.org/texlive/trunk@33057 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithms-in-c.tex')
-rw-r--r-- | Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithms-in-c.tex | 898 |
1 files changed, 898 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithms-in-c.tex b/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithms-in-c.tex new file mode 100644 index 00000000000..09dfc3c4f09 --- /dev/null +++ b/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithms-in-c.tex @@ -0,0 +1,898 @@ +% Copyright 2012 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 + +\ifgdccodebasic\else +In order to typeset this section, LuaTeX\ must be able to link C code +at runtime and the graph drawing C libraries must be installed on your +system. You will find the sources in the |c| subdirectory of the +installation, where you will also find example Makefiles. +\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 vesions 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 sharded 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}[] +\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}[] +\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}[] +\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. |