| 1 |
% Copyright 2018 by Till Tantau |
| 2 |
% |
| 3 |
% This file may be distributed and/or modified |
| 4 |
% |
| 5 |
% 1. under the LaTeX Project Public License and/or |
| 6 |
% 2. under the GNU Free Documentation License. |
| 7 |
% |
| 8 |
% See the file doc/generic/pgf/licenses/LICENSE for more details. |
| 9 |
|
| 10 |
|
| 11 |
\section{Writing Graph Drawing Algorithms in C} |
| 12 |
\label{section-algorithms-in-c} |
| 13 |
|
| 14 |
\noindent{\emph{by Till Tantau}} |
| 15 |
\bigskip |
| 16 |
\ifluatex |
| 17 |
\else |
| 18 |
This section of the manual can only be typeset using Lua\TeX. |
| 19 |
\expandafter\endinput |
| 20 |
\fi |
| 21 |
|
| 22 |
In the present section we have a look at how graph drawing |
| 23 |
algorithms written in the C programming language (or in C++) can be |
| 24 |
used in the graph drawing framework. |
| 25 |
|
| 26 |
\begin{quote} |
| 27 |
\emph{Warning:} Graph drawing algorithms written in C can be incredibly |
| 28 |
fast if you use the facilities of C correctly. \emph{However,} C code is |
| 29 |
much less portable than Lua code in the sense that it has to be compiled |
| 30 |
for the specific platform used by the user and that it has to be linked |
| 31 |
dynamically during a run of the \TeX\ program. All of this in possible (and |
| 32 |
works, as demonstrated by the linking of the \textsc{ogdf} framework), but |
| 33 |
it is \emph{much} harder to get right than writing Lua code. |
| 34 |
|
| 35 |
Bottom line, \emph{you really should be using this method only if it is |
| 36 |
really necessary (namely, when Lua code is simply not fast enough).} |
| 37 |
\end{quote} |
| 38 |
|
| 39 |
In the following, I first explain how the link between \TeX\ and C code works, |
| 40 |
in general. Then, in the subsequent sections, we go over the different kinds of |
| 41 |
programming languages and frameworks for which there is direct support for such |
| 42 |
a link. |
| 43 |
|
| 44 |
|
| 45 |
\subsection{How C and \TeX\ Communicate} |
| 46 |
|
| 47 |
In order to use C code for graph drawing algorithms during a run of the \TeX\ |
| 48 |
program, there is no need to build a new version of \TeX. Rather, it is |
| 49 |
possible that C code is linked into the \TeX\ executable at runtime. This is |
| 50 |
made possible by the fact that Lua (which part of Lua\TeX$\dots$) is able to |
| 51 |
link C libraries at runtime -- provided a strict regime of rules is adhered to: |
| 52 |
% |
| 53 |
\begin{enumerate} |
| 54 |
\item When you say |require| in Lua, it will normally look for a |.lua| |
| 55 |
file; but it will also try to find a |.so| file (a shared C library) as |
| 56 |
a fallback. |
| 57 |
\item If it finds such a shared library, Lua(\TeX) will try to link this |
| 58 |
library dynamically at runtime. |
| 59 |
\item Inside the library, there must be a function (called an entry point) |
| 60 |
with a special name (it must start with |luaopen_| and it must |
| 61 |
otherwise be the path and name of the library with slashes replaced by |
| 62 |
underscores). |
| 63 |
\item This function gets called by Lua, once. Its job is to setup the |
| 64 |
library so that it can be used by Lua. Mainly, this means that certain |
| 65 |
C functions get registered in such a way that Lua can call them. |
| 66 |
\item At this point, control returns to Lua and, now, certain functions |
| 67 |
have become available on the Lua layer that, when called, actually |
| 68 |
invoke the C code of our linked library. |
| 69 |
\end{enumerate} |
| 70 |
|
| 71 |
For each of the above points, there are some bells and whistles: |
| 72 |
% |
| 73 |
\begin{enumerate} |
| 74 |
\item Lua\TeX\ looks at slightly inconvenient places for shared libraries: |
| 75 |
By default, (currently, 2013) it looks in a |lib| subdirectory of the |
| 76 |
directory containing the Lua\TeX\ executable. The logic behind is that |
| 77 |
the shared libraries depend on the specific architecture of the |
| 78 |
executable. Thus, unlike normal Lua files, the library needs to be |
| 79 |
installed ``far away'' from the actual package of which it is part. |
| 80 |
\item Certain versions of Lua\TeX\ have a broken handling of filenames of |
| 81 |
libraries written in C. The TL2013 version of Lua\TeX, for instance, |
| 82 |
crashes when the filename of a shared library does not contain the |
| 83 |
complete path (while this works for normal file). Hopefully, this, too, |
| 84 |
will be fixed in future versions. |
| 85 |
\item On certain platforms, the support for dynamic linking against |
| 86 |
Lua\TeX\ is broken since the symbol table of the Lua library has been |
| 87 |
stripped away. Hopefully, this will be fixed soon; in the meantime, a |
| 88 |
highly fragile workaround is to link in another copy of the Lua |
| 89 |
library. |
| 90 |
\item The entry point that is called by Lua requires a certain signature |
| 91 |
(it takes a Lua state as its only parameter) and must return the number |
| 92 |
of objects it returns on the Lua stack. |
| 93 |
\item The registration process of C functions is somewhat tricky and |
| 94 |
changes from Lua version to Lua version. |
| 95 |
\item C functions that get called by Lua must follow all sorts of tricky |
| 96 |
rules in order to communicate with Lua correctly. |
| 97 |
\end{enumerate} |
| 98 |
|
| 99 |
Despite the above obstacles, one can use graph drawing algorithms written in C |
| 100 |
inside Lua, in principle, as follows: One loads an appropriately prepared and |
| 101 |
located C library using |require| and this library uses commands like |declare| |
| 102 |
to register its own functions into the graph drawing system so that when the |
| 103 |
|run| method is called, a C functions gets called instead. |
| 104 |
|
| 105 |
Unfortunately, the above approach is extremely tedious and error-prone and it |
| 106 |
is ``no fun'' to access Lua data structures (such as the syntactic digraph) |
| 107 |
from C. For this reason, I have written some libraries that encapsulate (as |
| 108 |
much as possible) of this communication between C and Lua. Indeed, when you use |
| 109 |
these libraries, you can focus entirely on the graph drawing issues and you |
| 110 |
will not even notice that your code ``is talking to Lua''. (Except for the name |
| 111 |
of the entry point, which is fixed to start with |luaopen_| and it is |
| 112 |
impossible to change this without disrupting a lot inside Lua's module system). |
| 113 |
|
| 114 |
There are libraries available for simplifying the communication between the |
| 115 |
graph drawing system and graph drawing algorithms written in |
| 116 |
% |
| 117 |
\begin{itemize} |
| 118 |
\item C, see Section~\ref{section-gd-c}, |
| 119 |
\item C++, see Section~\ref{section-gd-c++}, |
| 120 |
\item Open Graph Drawing Framework, see |
| 121 |
Section~\ref{section-gd-ogdf-interface}. |
| 122 |
\end{itemize} |
| 123 |
|
| 124 |
|
| 125 |
\subsection{Writing Graph Drawing Algorithms in C} |
| 126 |
\label{section-gd-c} |
| 127 |
|
| 128 |
\subsubsection{The Hello World of Graph Drawing in C} |
| 129 |
|
| 130 |
As our first example, as always, the ``hello world'' of graph drawing simply |
| 131 |
places nodes on a circle. For this, we implement a function |fast_hello_world| |
| 132 |
in a file |SimpleDemoC.c|. It starts as follows: |
| 133 |
% |
| 134 |
\begin{codeexample}[code only, tikz syntax=false] |
| 135 |
#include <pgf/gd/interface/c/InterfaceFromC.h> |
| 136 |
#include <math.h> |
| 137 |
|
| 138 |
static void fast_hello_world (pgfgd_SyntacticDigraph* graph) { |
| 139 |
... |
| 140 |
} |
| 141 |
\end{codeexample} |
| 142 |
|
| 143 |
As we can see, we first include a special header file of a rather small library |
| 144 |
that does all the hard work of translating between Lua and C for us |
| 145 |
(|InterfaceFromC|). These header files reside in the |c| subdirectory of the |
| 146 |
|pgf| package. Note that we do \emph{not} have to include the headers of the |
| 147 |
Lua library; indeed, you do not need access to the source of Lua to use the |
| 148 |
interface headers. As a side effect, we will, however, have to write |
| 149 |
|struct lua_State| instead of the more common |lua_State| once in our code, |
| 150 |
namely in the declaration of the entry point; but that is the only downside. |
| 151 |
|
| 152 |
The library |InterfaceFromC| declares the type |pgfgd_SyntacticDigraph|. In a |
| 153 |
moment, we will see that we can setup a key |fast simple demo layout| such that |
| 154 |
when this key is used on the display layer, the function |fast_hello_world| |
| 155 |
gets called. When it is called, the |graph| parameter will be a full |
| 156 |
representation of the to-be-laid-out graph. We can access the fields of the |
| 157 |
graph and even directly modify some of its fields (in particular, we can modify |
| 158 |
the |pos| fields of the vertices). Here is the complete code of the algorithm: |
| 159 |
% |
| 160 |
\begin{codeexample}[code only, tikz syntax=false] |
| 161 |
static void fast_hello_world (pgfgd_SyntacticDigraph* graph) { |
| 162 |
double angle = 6.28318530718 / graph->vertices.length; |
| 163 |
double radius = pgfgd_tonumber(graph->options, "fast simple demo radius"); |
| 164 |
|
| 165 |
int i; |
| 166 |
for (i = 0; i < graph->vertices.length; i++) { |
| 167 |
pgfgd_Vertex* v = graph->vertices.array[i]; |
| 168 |
v->pos.x = cos(angle*i) * radius; |
| 169 |
v->pos.y = sin(angle*i) * radius; |
| 170 |
} |
| 171 |
} |
| 172 |
\end{codeexample} |
| 173 |
|
| 174 |
That is all that is needed; the C library will take care of both creating the |
| 175 |
|graph| object as all well as of deleting it and of copying back the computed |
| 176 |
values of the |pos| fields of the vertices. |
| 177 |
|
| 178 |
Our next task is to setup the key |fast simple demo layout|. We can (and must) |
| 179 |
also do this from C, using the following code: |
| 180 |
% |
| 181 |
\begin{codeexample}[code only, tikz syntax=false] |
| 182 |
int luaopen_pgf_gd_examples_c_SimpleDemoC (struct lua_State *state) { |
| 183 |
|
| 184 |
pgfgd_Declaration* d = pgfgd_new_key ("fast simple demo layout"); |
| 185 |
pgfgd_key_summary (d, "The C version of the hello world of graph drawing"); |
| 186 |
pgfgd_key_algorithm (d, fast_hello_world); |
| 187 |
pgfgd_key_add_precondition (d, "connected"); |
| 188 |
pgfgd_key_add_precondition (d, "tree"); |
| 189 |
pgfgd_declare (state, d) |
| 190 |
pgfgd_free_key (d); |
| 191 |
\end{codeexample} |
| 192 |
|
| 193 |
The function |luaopen_pgf_gd_examples_c_SimpleDemoC| is the function that will |
| 194 |
be called by Lua (we will come to that). More important for us, at the moment, |
| 195 |
is the declaration of the key: We use |pgfgd_new_key| to create a declaration |
| 196 |
record and then fill the different fields using appropriate function calls. In |
| 197 |
particular, the call |pgfgd_key_algorithm| allows us to link the key with a |
| 198 |
particular C function. The |pgfgd_declare| will then pass the whole declaration |
| 199 |
back to Lua, so the effect of the above is essentially the same as if you had |
| 200 |
written in Lua: |
| 201 |
% |
| 202 |
\begin{codeexample}[code only, tikz syntax=false] |
| 203 |
declare { |
| 204 |
key = "fast simple demo layout", |
| 205 |
summary = "The C version of the hello world of graph drawing", |
| 206 |
preconditions = { |
| 207 |
connected = true, |
| 208 |
tree = true, |
| 209 |
}, |
| 210 |
algorithm = { |
| 211 |
run = -- something magic we cannot express in Lua |
| 212 |
} |
| 213 |
} |
| 214 |
\end{codeexample} |
| 215 |
|
| 216 |
In our algorithm, in addition to the above key, we also use the |
| 217 |
|fast simple demo radius| key, which is a simple length key. This key, too, can |
| 218 |
be declared on the C layer: |
| 219 |
% |
| 220 |
\begin{codeexample}[code only, tikz syntax=false] |
| 221 |
d = pgfgd_new_key ("fast simple demo radius"); |
| 222 |
pgfgd_key_summary (d, "A radius value for the hello world of graph drawing"); |
| 223 |
pgfgd_key_type (d, "length"); |
| 224 |
pgfgd_key_initial (d, "1cm"); |
| 225 |
pgfgd_declare (state, d); |
| 226 |
pgfgd_free_key (d); |
| 227 |
|
| 228 |
return 0; |
| 229 |
} |
| 230 |
\end{codeexample} |
| 231 |
|
| 232 |
We simply add this code to the startup function above. |
| 233 |
|
| 234 |
Now it is time to compile and link the code. For this, you must, well, compile |
| 235 |
it, link it against the library |InterfaceFromC|, and build a shared library |
| 236 |
out of it. Also, you must place it somewhere where Lua\TeX\ will find it. You |
| 237 |
will find a Makefile that should be able to achieve all of this in the |
| 238 |
directory |pgf/c/graphdrawing/pgf/gd/examples/c|, where you will also find the |
| 239 |
code of the above example. |
| 240 |
|
| 241 |
Now, all you need to do to use it is to write in Lua (after you have loaded the |
| 242 |
|pgf.gd| library, of course), would normally be the call |
| 243 |
% |
| 244 |
\begin{codeexample}[code only, tikz syntax=false] |
| 245 |
require 'pgf.gd.examples.c.SimpleDemoC' |
| 246 |
\end{codeexample} |
| 247 |
% |
| 248 |
or in \tikzname |
| 249 |
% |
| 250 |
\begin{codeexample}[code only] |
| 251 |
\usegdlibrary {examples.c.SimpleDemoC} |
| 252 |
\end{codeexample} |
| 253 |
|
| 254 |
This should cause Lua\TeX\ to find the shared library, load it, and then call |
| 255 |
the function in that library with the lengthy name (the name is always |
| 256 |
|luaopen_| followed by the path and filename with slashes replaced by |
| 257 |
underscores). |
| 258 |
|
| 259 |
\emph{Remark:} Unfortunately, the above does not work with the \TeX Live 2013 |
| 260 |
versions of Lua\TeX\ due to a bugs that causes the ``replace dots by slashes'' |
| 261 |
to fail. For this reason, we currently need to rename our shared library file |
| 262 |
to |
| 263 |
% |
| 264 |
\begin{codeexample}[code only, tikz syntax=false] |
| 265 |
pgf_gd_examples_c_SimpleDemoC.so |
| 266 |
\end{codeexample} |
| 267 |
% |
| 268 |
and then say |
| 269 |
% |
| 270 |
\begin{codeexample}[code only, tikz syntax=false] |
| 271 |
require 'pgf_gd_examples_c_SimpleDemoC' |
| 272 |
\end{codeexample} |
| 273 |
% |
| 274 |
or in \tikzname |
| 275 |
% |
| 276 |
\begin{codeexample}[code only] |
| 277 |
\usegdlibrary {pgf_gd_examples_c_SimpleDemoC} |
| 278 |
\end{codeexample} |
| 279 |
|
| 280 |
In future versions of Lua\TeX, things should be ``back to normal'' in this |
| 281 |
regard. Also, the bug only concerns shared libraries; you can still create a |
| 282 |
normal Lua file with a nice name and place at a nice location and the only |
| 283 |
contents of this file is then the above |require| command. |
| 284 |
|
| 285 |
Anyway, once we have loaded the shared library we can say: |
| 286 |
% |
| 287 |
\begin{codeexample}[code only] |
| 288 |
\tikz \graph [fast simple demo layout, fast simple demo radius=1.25cm] |
| 289 |
{ a -> b -> c -> d -> e -> a }; |
| 290 |
\end{codeexample} |
| 291 |
|
| 292 |
|
| 293 |
\subsubsection{Documenting Algorithms Written in C} |
| 294 |
\label{section-gd-documenting-c-algos} |
| 295 |
|
| 296 |
In our above example, we included a summary with the keys in the C code. It |
| 297 |
would be even better if we added a longer documentation and some examples that |
| 298 |
show how the key works; but this is a bit impracticable in C since multi-line |
| 299 |
strings are hard to write down in~C. The trick is to use the |documentation_in| |
| 300 |
field of a key: It allows us to specify the name of a Lua file that should be |
| 301 |
loaded (using |require|) to install the missing documentation fields. As |
| 302 |
explained in Section~\ref{section-gd-documentation-in}, this Lua file may make |
| 303 |
good use the |pgf.gd.doc| package. Note, also, that for keys documented in this |
| 304 |
way the documentation can easily be included in this manual through the use of |
| 305 |
the |\includedocumentationof| command. |
| 306 |
|
| 307 |
In our example, we would first add the following line twice in the C code (once |
| 308 |
for each key), assuming that the documentation resides in the file |
| 309 |
|pgf/gd/doc/examples/SimpleDemoC.lua|: |
| 310 |
% |
| 311 |
\begin{codeexample}[code only, tikz syntax=false] |
| 312 |
pgfgd_key_documentation_in (d, "pgf.gd.doc.examples.SimpleDemoC"); |
| 313 |
\end{codeexample} |
| 314 |
|
| 315 |
Note that since the documentation is a normal Lua file, it will be searched in |
| 316 |
the usual places Lua files are located (in the texmf trees) and not, like the C |
| 317 |
shared library, in the special |lib| subdirectory of the Lua\TeX\ binary. |
| 318 |
|
| 319 |
Here are typical contents of the documentation file: |
| 320 |
% |
| 321 |
\begin{codeexample}[code only, tikz syntax=false] |
| 322 |
-- File pgf/gd/doc/examples/SimpleDemoC.lua |
| 323 |
local key = require 'pgf.gd.doc'.key |
| 324 |
local documentation = require 'pgf.gd.doc'.documentation |
| 325 |
local summary = require 'pgf.gd.doc'.summary |
| 326 |
local example = require 'pgf.gd.doc'.example |
| 327 |
|
| 328 |
key "fast simple demo layout" |
| 329 |
documentation |
| 330 |
[[ |
| 331 |
This layout is used... |
| 332 |
]] |
| 333 |
example |
| 334 |
[[ |
| 335 |
\tikz \graph [fast simple example layout] |
| 336 |
{ a -- b -- c -- d -- e; }; |
| 337 |
]] |
| 338 |
|
| 339 |
key "fast simple demo radius" |
| 340 |
documentation |
| 341 |
[[ |
| 342 |
The radius parameter is used to ... |
| 343 |
]] |
| 344 |
example |
| 345 |
[[ |
| 346 |
\tikz \graph [fast simple demo layout, fast simple demo radius=1.25cm] |
| 347 |
{ a -> b -> c -> d -> e -> a }; |
| 348 |
]] |
| 349 |
\end{codeexample} |
| 350 |
|
| 351 |
|
| 352 |
\subsubsection{The Interface From C} |
| 353 |
|
| 354 |
In the above example, we already saw some of the functions from the library |
| 355 |
|InterfaceFromC| that translated from Lua to C for us. For a complete list of |
| 356 |
all functions available, currently please see |
| 357 |
|graphdrawing/c/pgf/gd/interface/c/InterfaceFromC.h| directly. |
| 358 |
|
| 359 |
Currently, the library provides C functions to directly access all aspects of |
| 360 |
the syntactic digraph and also of the graphs computed by the preprocessing of |
| 361 |
the layout pipeline. What is missing, however, is access to the tree of |
| 362 |
(sub)layouts and to collections. Hopefully, these will be added in the future. |
| 363 |
|
| 364 |
|
| 365 |
\subsection{Writing Graph Drawing Algorithms in C++} |
| 366 |
\label{section-gd-c++} |
| 367 |
|
| 368 |
Built on top of the C interface presented in the previous section, there is |
| 369 |
also a C++ interface available. It encapsulates as much of the C functions as |
| 370 |
possible in C++ classes. Thus, this interface is mostly there for convenience, |
| 371 |
it does not offer fundamentally new functionality. |
| 372 |
|
| 373 |
|
| 374 |
\subsubsection{The Hello World of Graph Drawing in C++} |
| 375 |
|
| 376 |
Let us have a look at how our beloved hello world of graph drawing looks in |
| 377 |
C++. Although it is still possible to put graph drawing algorithms inside |
| 378 |
functions, it is more natural in C++ to turn them into methods of a class. |
| 379 |
Thus, we start the code of |SimpleDemoCPlusPlus.c++| as follows: |
| 380 |
% |
| 381 |
\begin{codeexample}[code only, tikz syntax=false] |
| 382 |
#include <pgf/gd/interface/c/InterfaceFromC++.h> |
| 383 |
#include <pgf/gd/interface/c/InterfaceFromC.h> |
| 384 |
|
| 385 |
#include <math.h> |
| 386 |
|
| 387 |
struct FastLayout : scripting::declarations, scripting::runner { |
| 388 |
... |
| 389 |
} |
| 390 |
\end{codeexample} |
| 391 |
|
| 392 |
As can be seen, we do not only include the interface from C++, but also that |
| 393 |
from C (since, currently, not all functionality of the C library is |
| 394 |
encapsulated in C++). |
| 395 |
|
| 396 |
The interesting part is the |struct FastLayout|, which will contain our |
| 397 |
algorithm (you could just as well have used a |class| instead of a |struct|). |
| 398 |
It is derived from two classes: First, from a |declarations| class and, |
| 399 |
secondly, from a |runner| class. Both of them, just like everything else from |
| 400 |
the interface, reside in the namespace |scripting|. This name was chosen since |
| 401 |
the main purpose of the interface is to provide ``scripting facilities'' to C |
| 402 |
code through the use of Lua. |
| 403 |
|
| 404 |
We are currently interested in the class |runner|. This class has a virtual |
| 405 |
function |run| that gets called when, on the Lua side, someone has selected the |
| 406 |
algorithm represented by the class. Thus, we place our algorithm in this |
| 407 |
method: |
| 408 |
% |
| 409 |
\begin{codeexample}[code only, tikz syntax=false] |
| 410 |
void run () { |
| 411 |
pgfgd_SyntacticDigraph* graph = parameters->syntactic_digraph; |
| 412 |
|
| 413 |
double angle = 6.28318530718 / graph->vertices.length; |
| 414 |
double radius = parameters->option<double>("fast simple demo radius c++"); |
| 415 |
|
| 416 |
for (int i = 0; i < graph->vertices.length; i++) { |
| 417 |
pgfgd_Vertex* v = graph->vertices.array[i]; |
| 418 |
v->pos.x = cos(angle*i) * radius; |
| 419 |
v->pos.y = sin(angle*i) * radius; |
| 420 |
} |
| 421 |
} |
| 422 |
\end{codeexample} |
| 423 |
|
| 424 |
The |run| method has access to the member variable |parameters|, which contains |
| 425 |
all sorts of information concerning the to-be-drawn graph. In particular, the |
| 426 |
|syntactic_digraph| field gives us access to the syntactic digraph structure |
| 427 |
that was already available in the interface from plain~C. However, we can also |
| 428 |
see that a template function like |option| allows us to access the graph's |
| 429 |
option table in a simple way. |
| 430 |
|
| 431 |
As for C code, our next task is to setup a key that, when used on the |
| 432 |
\tikzname\ layer, will run our algorithm. For this, we can use an object |
| 433 |
derived from a |declarations|. In our example, the |FastLayout| is both derived |
| 434 |
from a |runner| (since it contains an algorithm) and also from |declarations| |
| 435 |
(since it also contains the code necessary for declaring this algorithm). If |
| 436 |
you prefer, you can split this into two classes. A |declarations| object must |
| 437 |
override the |declare| method. This method gets a |script| object as input, |
| 438 |
which is the ``representation'' of Lua inside the C++ code: |
| 439 |
% |
| 440 |
\begin{codeexample}[code only, tikz syntax=false] |
| 441 |
void declare(scripting::script s) { |
| 442 |
using namespace scripting; |
| 443 |
|
| 444 |
s.declare(key ("fast simple demo layout c++") |
| 445 |
.summary ("The C++ version of the hello world of graph drawing") |
| 446 |
.precondition ("connected") |
| 447 |
.precondition ("tree") |
| 448 |
.algorithm (this)); |
| 449 |
|
| 450 |
s.declare(key ("fast simple demo radius c++") |
| 451 |
.summary ("A radius value for the hello world of graph drawing") |
| 452 |
.type ("length") |
| 453 |
.initial ("1cm")); |
| 454 |
} |
| 455 |
\end{codeexample} |
| 456 |
|
| 457 |
For each key that we wish to declare, we call the script's |declare| method |
| 458 |
once. This method takes a |key| object as input, which can be configured |
| 459 |
through a sequence of calls to different member functions (like |summary| or |
| 460 |
|algorithm|). Most of these member functions are rather self-explaining; only |
| 461 |
|algorithm| is a bit trickier: It does not take a function as input, but rather |
| 462 |
an object of type |runner| and it will call the |run| method of this object |
| 463 |
whenever the algorithm is run. |
| 464 |
|
| 465 |
Lastly, we also need to write the entry point: |
| 466 |
% |
| 467 |
\begin{codeexample}[code only, tikz syntax=false] |
| 468 |
extern "C" int luaopen_pgf_gd_examples_c_SimpleDemoCPlusPlus (struct lua_State *state) { |
| 469 |
scripting::script s (state); |
| 470 |
s.declare (new FastLayout); |
| 471 |
return 0; |
| 472 |
} |
| 473 |
\end{codeexample} |
| 474 |
|
| 475 |
Note that it is the job of the interface classes to free the passed |
| 476 |
|declarations| object. For this reason, you really need to call |new| and |
| 477 |
cannot pass the address of a temporary object. |
| 478 |
|
| 479 |
As before, because of the bug in some Lua\TeX\ versions, to actually load the |
| 480 |
library at runtime, we need to rename it to |
| 481 |
% |
| 482 |
\begin{codeexample}[code only, tikz syntax=false] |
| 483 |
pgf_gd_examples_c_SimpleDemoCPlusPlus.so |
| 484 |
\end{codeexample} |
| 485 |
% |
| 486 |
and then say |
| 487 |
% |
| 488 |
\begin{codeexample}[code only, tikz syntax=false] |
| 489 |
require 'pgf_gd_examples_c_SimpleDemoCPlusPlus' |
| 490 |
\end{codeexample} |
| 491 |
% |
| 492 |
or in \tikzname |
| 493 |
% |
| 494 |
\begin{codeexample}[code only] |
| 495 |
\usegdlibrary {pgf_gd_examples_c_SimpleDemoCPlusPlus} |
| 496 |
\end{codeexample} |
| 497 |
|
| 498 |
We can now use it: |
| 499 |
% |
| 500 |
\begin{codeexample}[code only] |
| 501 |
\tikz \graph [fast simple demo layout c++, fast simple demo radius c++=1.25cm] |
| 502 |
{ a -> b -> c -> d -> e -> a }; |
| 503 |
\end{codeexample} |
| 504 |
|
| 505 |
|
| 506 |
\subsubsection{The Interface From C++} |
| 507 |
|
| 508 |
The header |graphdrawing/c/pgf/gd/interface/c/InterfaceFromC++.h| contains, as |
| 509 |
the name suggest, the interface from C++. A complete documentation is still |
| 510 |
missing, but let us go over the main ideas: |
| 511 |
|
| 512 |
|
| 513 |
\medskip |
| 514 |
\noindent\textbf{Runners.} |
| 515 |
Algorithms are represented by objects of type |runner|. An algorithm will |
| 516 |
overwrite the |run| method, as we saw in the example, and it should modify the |
| 517 |
|parameters| of the runner object. |
| 518 |
|
| 519 |
In addition to the |run| method, there are also two more virtual methods, |
| 520 |
called |bridge| and |unbrigde|. The first is called before the |run| method is |
| 521 |
called and the second afterwards. The idea is that another framework, such as |
| 522 |
\textsc{ogdf}, can implement a new class |ogdf_runner| that overrides these two |
| 523 |
methods in order to transform the Lua/C representation of the input graph into |
| 524 |
an \textsc{ogdf} representation prior to the |run| method being called. The |
| 525 |
|run| method can then access additional member variables that store the graph |
| 526 |
representations in \textsc{ogdf} form (or another form, depending on the |
| 527 |
framework). The |unbridge| method allows the framework to translate back. |
| 528 |
|
| 529 |
Although a |runner| object must be created for every algorithm, an algorithm |
| 530 |
can also reside in a function. The class |function_runner| is a simple wrapper |
| 531 |
that turns a function into such an object. |
| 532 |
|
| 533 |
|
| 534 |
\medskip |
| 535 |
\noindent\textbf{Keys.} |
| 536 |
A key object is a temporary object that is passed to the |declare| method of a |
| 537 |
script. It represents the table that is passed to the Lua function |declare|. |
| 538 |
In order to make setting its field easy, for each field name there is a |
| 539 |
corresponding function (like |summary|) that takes the string that should be |
| 540 |
set to this field and returns the key object once more, so that we can chain |
| 541 |
calls. |
| 542 |
|
| 543 |
The |algorithm| method gets a runner object as parameter and will store a |
| 544 |
pointer to this object inside Lua. Each time the algorithm is used, this object |
| 545 |
will be used to ``run'' the algorithm, that is, the methods |prepare|, |
| 546 |
|bridge|, |run|, and |unbridge| will be called in that order. Since the object |
| 547 |
is reused each time, only one object is needed; but this object may not be |
| 548 |
freed prematurely. Indeed, you will normally create the object using |new| once |
| 549 |
and will then never delete it. |
| 550 |
|
| 551 |
A typical idiom you may find in the code is |
| 552 |
% |
| 553 |
\begin{codeexample}[code only, tikz syntax=false] |
| 554 |
s.declare (key (...) |
| 555 |
.algorithm(this) |
| 556 |
...); |
| 557 |
\end{codeexample} |
| 558 |
% |
| 559 |
This code is seen inside the |declare| method of objects that are both |
| 560 |
declarations and runners. They register ``themselves'' via the above code. |
| 561 |
Note, however, that this requires that the |this| pointer is not a temporary |
| 562 |
object. (The typing rules of C++ make it hard for this situation to happen, but |
| 563 |
it can be achieved.) |
| 564 |
|
| 565 |
|
| 566 |
\medskip |
| 567 |
\noindent\textbf{Reading options.} Once options have been declared, your C++ |
| 568 |
algorithms will wish to read them back. For this, the |parameters| field of a |
| 569 |
runner object provides a number of templated methods: |
| 570 |
% |
| 571 |
\begin{itemize} |
| 572 |
\item The |option_is_set| method returns |true| if the passed option has |
| 573 |
been set \emph{and} can be cast to the type of the template. So, |
| 574 |
|option_is_set<double>("node distance")| will return true if the |
| 575 |
|node distance| key has been set for the graph as a whole (currently, |
| 576 |
there is no way to read the options of a vertex or an edge from C++, |
| 577 |
use the C methods instead). |
| 578 |
\item The |option| function comes in two flavours: First, it takes a single |
| 579 |
option name and just returns the option's value. If, however, the |
| 580 |
option has not been set or has another type, some sort of null value is |
| 581 |
returned. So, |option<double>("node distance")| will return the |
| 582 |
configured node distance as a double. When an option has an initial |
| 583 |
value, this call will always return a sensible value. |
| 584 |
|
| 585 |
The second flavour of |option| allows you to pass a reference to an |
| 586 |
object in which the option's value should be stored and the function |
| 587 |
will return true if the option is set (and, thus, something was written |
| 588 |
into the reference). This is the ``safest'' way to access an option: |
| 589 |
% |
| 590 |
\begin{codeexample}[code only, tikz syntax=false] |
| 591 |
double dist; |
| 592 |
if (parameters->option ("node distance", dist)) |
| 593 |
... |
| 594 |
\end{codeexample} |
| 595 |
|
| 596 |
Caution must be taken for |char*| options: The returned string must be |
| 597 |
explicitly freed; it will be a copy of the string stored in the Lua |
| 598 |
table. |
| 599 |
\item The |configure_option| method is used to set a member of an object |
| 600 |
based on the value of a certain option. For this, you must pass a |
| 601 |
pointer to a member function that sets the member. Here is an example: |
| 602 |
% |
| 603 |
\begin{codeexample}[code only, tikz syntax=false] |
| 604 |
class MyClass { |
| 605 |
public: |
| 606 |
void setMyDistance (double distance); |
| 607 |
... |
| 608 |
}; |
| 609 |
... |
| 610 |
|
| 611 |
MyClass m; |
| 612 |
parameters->configure_option("node distance", &MyClass::setMyDistance, m); |
| 613 |
\end{codeexample} |
| 614 |
% |
| 615 |
If the option has not been set or does not have the correct type, the |
| 616 |
member function is not called. |
| 617 |
\end{itemize} |
| 618 |
|
| 619 |
|
| 620 |
\medskip |
| 621 |
\noindent\textbf{Factories and modules.} |
| 622 |
A Lua key is normally either a Boolean, a double, or a string. However, in C++, |
| 623 |
we may also sometimes wish Lua users to configure which C function is used to |
| 624 |
achieve something. One could do this using strings or numbers and then use |
| 625 |
search algorithms or a long |switch|, but this would neither be flexible nor |
| 626 |
elegant. |
| 627 |
|
| 628 |
Instead, it is possible to store \emph{factories} in Lua keys. A factory is a |
| 629 |
class derived from |factory| that implements the virtual function |make|. This |
| 630 |
function will return a new object of a template type. You can store such a |
| 631 |
factory in a key. |
| 632 |
|
| 633 |
The |make| method of a parameters object allows you to invoke the factory |
| 634 |
stored in a key. (If no factory is stored in it, |null| is returned). |
| 635 |
|
| 636 |
The |configure_module| method is akin to |configure_option|, only the result of |
| 637 |
applying the factory is passed to the member function of the class. |
| 638 |
|
| 639 |
|
| 640 |
\medskip |
| 641 |
\noindent\textbf{Scripts.} |
| 642 |
A ``script'' is the abstraction of the communication between Lua and C++. From |
| 643 |
C++'s point of view, the script object offers different |declare| methods that |
| 644 |
allow us to ``make objects and function scriptable'' in the sense that they can |
| 645 |
then be called and configured from Lua. The script must be initialized with a |
| 646 |
Lua state and will be bound to that state (basically, the script only stores |
| 647 |
this single pointer). |
| 648 |
|
| 649 |
When you call |declare|, you either pass a single key object (which is then |
| 650 |
declared on the Lua layer) or you pass a |declarations| object, whose virtual |
| 651 |
|declare| method is then called. The |declarations| objects are used to bundle |
| 652 |
several declarations into a single one. |
| 653 |
|
| 654 |
|
| 655 |
\subsection{Writing Graph Drawing Algorithms Using OGDF} |
| 656 |
\label{section-gd-ogdf-interface} |
| 657 |
|
| 658 |
Built on top of the C++ interface, a small interface allows you to easily link |
| 659 |
algorithms written for the \textsc{ogdf} (Open Graph Drawing Framework) with |
| 660 |
graph drawing in Lua. |
| 661 |
|
| 662 |
|
| 663 |
\subsubsection{The Hello World of Graph Drawing in OGDF -- From Scratch} |
| 664 |
|
| 665 |
We start with some startup code: |
| 666 |
% |
| 667 |
\begin{codeexample}[code only, tikz syntax=false] |
| 668 |
#include <pgf/gd/ogdf/c/InterfaceFromOGDF.h> |
| 669 |
#include <math.h> |
| 670 |
|
| 671 |
using namespace ogdf; |
| 672 |
using namespace scripting; |
| 673 |
\end{codeexample} |
| 674 |
|
| 675 |
Note that the interface from \textsc{ogdf} resides in the |ogdf| folder, not in |
| 676 |
the |interface| folder. |
| 677 |
|
| 678 |
Like in the plain C++ interface, we must now subclass the |runner| class and |
| 679 |
the |declarations| class. Also like the plain C++ interface, we can use |
| 680 |
multiple inheritance. The difference lies in the fact that we do not directly |
| 681 |
subclass form |runner|, but rather from |ogdf_runner|. This class implements |
| 682 |
the complicated ``bridging'' or ``translation'' process between the world of |
| 683 |
|InterfaceFromC++| and \textsc{ogdf}: |
| 684 |
% |
| 685 |
\begin{codeexample}[code only, tikz syntax=false] |
| 686 |
struct FastLayoutOGDF : declarations, ogdf_runner { |
| 687 |
|
| 688 |
void run () { |
| 689 |
double angle = 6.28318530718 / graph.numberOfNodes(); |
| 690 |
double radius = parameters->option<double>("my radius ogdf"); |
| 691 |
|
| 692 |
int i = 0; |
| 693 |
for (node v = graph.firstNode(); v; v=v->succ(), i++) { |
| 694 |
graph_attributes.x(v) = cos(angle*i) * radius; |
| 695 |
graph_attributes.y(v) = sin(angle*i) * radius; |
| 696 |
} |
| 697 |
} |
| 698 |
\end{codeexample} |
| 699 |
|
| 700 |
As can be seen, in a subclass of |ogdf_runner|, the |run| method will have |
| 701 |
access to a member called |graph| and to another member called |
| 702 |
|graph_attributes|. These will have been setup with the graph from the Lua |
| 703 |
layer and, after the algorithm has run, the information stored in the |x| and |
| 704 |
|y| fields of the graph attributes and also the bend information of the edges |
| 705 |
will be written back automatically. |
| 706 |
|
| 707 |
Next, we need to declare the algorithm. This is done as in the plain |
| 708 |
C++ interface: |
| 709 |
% |
| 710 |
\begin{codeexample}[code only, tikz syntax=false] |
| 711 |
void declare(script s) { |
| 712 |
using namespace scripting; |
| 713 |
|
| 714 |
s.declare(key ("fast simple demo layout ogdf") |
| 715 |
.summary ("The OGDF version of the hello world of graph drawing") |
| 716 |
.precondition ("connected") |
| 717 |
.algorithm (this)); |
| 718 |
|
| 719 |
s.declare(key ("my radius ogdf") |
| 720 |
.summary ("A radius value for the hello world of graph drawing") |
| 721 |
.type ("length") |
| 722 |
.initial ("1cm")); |
| 723 |
} |
| 724 |
}; |
| 725 |
\end{codeexample} |
| 726 |
|
| 727 |
Finally, we need the entry point, which is also ``as usual'': |
| 728 |
% |
| 729 |
\begin{codeexample}[code only, tikz syntax=false] |
| 730 |
extern "C" int luaopen_pgf_gd_examples_c_SimpleDemoOGDF (struct lua_State *state) { |
| 731 |
script (state).declare (new FastLayoutOGDF); |
| 732 |
return 0; |
| 733 |
} |
| 734 |
\end{codeexample} |
| 735 |
|
| 736 |
Yet again, we need to rename the resulting shared library and then say |
| 737 |
|require| on it. We can now use it: |
| 738 |
% |
| 739 |
\begin{codeexample}[code only] |
| 740 |
\tikz \graph [fast simple demo layout ogdf, my radius ogdf=1cm] |
| 741 |
{ a -> b -> c -> d -> e -> a }; |
| 742 |
\end{codeexample} |
| 743 |
|
| 744 |
|
| 745 |
\subsubsection{The Hello World of Graph Drawing in OGDF -- Adapting Existing Classes} |
| 746 |
|
| 747 |
In the previous example we implemented a graph drawing algorithm using |
| 748 |
\textsc{ogdf} for use with Lua ``from scratch''. In particular, the whole |
| 749 |
algorithm was contained in the |run| method of our main class. In practice, |
| 750 |
however, graph drawing algorithms are typically placed in classes that ``know |
| 751 |
nothing about scripting''. For instance, our hello world of graph drawing might |
| 752 |
actually be implemented like this: |
| 753 |
% |
| 754 |
\begin{codeexample}[code only, tikz syntax=false] |
| 755 |
// File HelloWorldLayout.h |
| 756 |
#include <ogdf/module/LayoutModule.h> |
| 757 |
|
| 758 |
class HelloWorldLayout : public ogdf::LayoutModule { |
| 759 |
public: |
| 760 |
|
| 761 |
virtual void call(ogdf::GraphAttributes &GA) |
| 762 |
{ |
| 763 |
using namespace ogdf; |
| 764 |
|
| 765 |
const Graph &graph = GA.constGraph(); |
| 766 |
double angle = 6.28318530718 / graph.numberOfNodes(); |
| 767 |
int i = 0; |
| 768 |
for (node v = graph.firstNode(); v; v=v->succ(), i++) { |
| 769 |
GA.x(v) = cos(angle*i) * radius; |
| 770 |
GA.y(v) = sin(angle*i) * radius; |
| 771 |
} |
| 772 |
} |
| 773 |
|
| 774 |
void setRadius (double r) { radius = r; } |
| 775 |
|
| 776 |
private: |
| 777 |
|
| 778 |
double radius; |
| 779 |
}; |
| 780 |
\end{codeexample} |
| 781 |
|
| 782 |
Now, what we actually want to do is to ``make this class scriptable''. For |
| 783 |
this, we setup a new class whose |run| method will produce a new |
| 784 |
|HelloWorldLayout|, configure it, and then run it. Here is this run method: |
| 785 |
% |
| 786 |
\begin{codeexample}[code only, tikz syntax=false] |
| 787 |
void run () |
| 788 |
{ |
| 789 |
HelloWorldLayout layout; |
| 790 |
parameters->configure_option("HelloWorldLayout.radius", &HelloWorldLayout::setRadius, layout); |
| 791 |
layout.call(graph_attributes); |
| 792 |
} |
| 793 |
\end{codeexample} |
| 794 |
|
| 795 |
Next, we need to write the declarations code. This is very similar to the |
| 796 |
``from scratch'' version: |
| 797 |
% |
| 798 |
\begin{codeexample}[code only, tikz syntax=false] |
| 799 |
void declare(script s) { |
| 800 |
using namespace scripting; |
| 801 |
|
| 802 |
s.declare(key ("HelloWorldLayout") |
| 803 |
.summary ("The OGDF version of the hello world of graph drawing") |
| 804 |
.precondition ("connected") |
| 805 |
.algorithm (this)); |
| 806 |
|
| 807 |
s.declare(key ("HelloWorldLayout.radius") |
| 808 |
.summary ("A radius value for the hello world of graph drawing") |
| 809 |
.type ("length") |
| 810 |
.alias ("radius")); |
| 811 |
} |
| 812 |
\end{codeexample} |
| 813 |
|
| 814 |
Two remarks are in order: First, it is customary to name the keys for the |
| 815 |
display system the same way as the classes. Second, the different configuration |
| 816 |
options of the algorithm are named with the class name followed by the option |
| 817 |
name. This makes it clear who, exactly, is being configured. However, these |
| 818 |
keys should then also get an |alias| field set, which will cause an automatic |
| 819 |
forwarding of the key to something more ``user friendly'' like just |radius|. |
| 820 |
|
| 821 |
It remains to put the above methods in a ``script'' file. It is this file that, |
| 822 |
when compiled, must be linked at runtime against Lua\TeX. |
| 823 |
% |
| 824 |
\begin{codeexample}[code only, tikz syntax=false] |
| 825 |
// File HelloWorldLayout_script.c++ |
| 826 |
|
| 827 |
#include <pgf/gd/ogdf/c/InterfaceFromOGDF.h> |
| 828 |
#include <HelloWorldLayout.h> |
| 829 |
|
| 830 |
using namespace ogdf; |
| 831 |
using namespace scripting; |
| 832 |
|
| 833 |
struct HelloWorldLayout_script : declarations, ogdf_runner { |
| 834 |
void run () { ... see above ... } |
| 835 |
void declare (script s) { ... see above ... } |
| 836 |
}; |
| 837 |
|
| 838 |
extern "C" int luaopen_my_path_HelloWorldLayout_script (struct lua_State *state) { |
| 839 |
script (state).declare (new HelloWorldLayout_script); |
| 840 |
return 0; |
| 841 |
} |
| 842 |
\end{codeexample} |
| 843 |
|
| 844 |
|
| 845 |
\subsubsection{Documenting OGDF Algorithms} |
| 846 |
|
| 847 |
As explained in Section~\ref{section-gd-documenting-c-algos}, we can add |
| 848 |
external documentation to algorithms written in C and, using the |
| 849 |
|documentation_in| method of the |key| class, we can use the exact same method |
| 850 |
to document \textsc{ogdf} algorithms. |
| 851 |
|
| 852 |
I strongly recommend making use of this feature since, currently, the |
| 853 |
documentation of many \textsc{ogdf} classes is sketchy at best and using |
| 854 |
\tikzname\ examples seems to be a good way of explaining the effect of the |
| 855 |
different parameters algorithms offer. |
| 856 |
|
| 857 |
|
| 858 |
\subsubsection{The Interface From OGDF} |
| 859 |
|
| 860 |
The support for \textsc{ogdf} offered inside |InterfaceFromOGDF.h| is just the |
| 861 |
class |ogdf_runner| we saw already in the example. In addition, there is also a |
| 862 |
wrapper class |ogdf_function_runner| that allows you to wrap an algorithm |
| 863 |
implemented in a function that uses \textsc{ogdf}, but I expect this to be the |
| 864 |
case only rarely. |