summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithms-in-c.tex
blob: 09dfc3c4f09ab4d5e7842f35f28d758807fed3bf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
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.