Debian Codegraph @

texmf-dist/doc/generic/pgf/pgfmanual-en-gd-algorithms-in-c.tex

raw
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.