Debian Codegraph @

texmf-dist/doc/generic/pgf/pgfmanual-en-gd-algorithm-layer.tex

raw
1 % Copyright 2019 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster
2 % Copyright 2019 by Till Tantau
3 % Copyright 2019 by Jannis Pohlmann
4 %
5 % This file may be distributed and/or modified
6 %
7 % 1. under the LaTeX Project Public License and/or
8 % 2. under the GNU Free Documentation License.
9 %
10 % See the file doc/generic/pgf/licenses/LICENSE for more details.
11
12
13 \section{The Algorithm Layer}
14 \label{section-gd-algorithm-layer}
15
16 \noindent{\emph{by Till Tantau}}
17
18 \ifluatex
19 \else
20 This section of the manual can only be typeset using Lua\TeX.
21 \expandafter\endinput
22 \fi
23
24
25 \subsection{Overview}
26
27 The present section is addressed at readers interested in implementing new
28 graph drawing algorithms for the graph drawing system. Obviously, in order to
29 do so, you need to have an algorithm in mind and also some programming skills;
30 but fortunately only in the Lua programming language: Even though the graph
31 drawing system was originally developed as an extension of \tikzname, is has
32 been restructured so that the ``algorithm layer'' where you define algorithms
33 is scrupulously separated from \tikzname. In particular, an algorithm declared
34 and implemented on this layer can be used in with every ``display layers'', see
35 Section~\ref{section-gd-display-layer}, without change. Nevertheless, in the
36 following we will use the \tikzname\ display layer and syntax in our examples.
37
38 Normally, new graph drawing algorithms can and must be implemented in the Lua
39 programming language, which is a small, easy-to-learn (and quite beautiful)
40 language integrated into current versions of \TeX. However, as explained in
41 Section~\ref{section-algorithms-in-c}, you can also implement algorithms in C
42 or C++ (and, possibly, in the future also in other languages), but this comes
43 at a great cost concerning portability. In the present section, I assume that
44 you are only interested in writing an algorithm using Lua.
45
46 In the following, after a small ``hello world'' example of graph drawing and a
47 discussion of technical details like how to name files so that \TeX\ will find
48 them, we have a look at the main parts of the algorithm layer:
49 %
50 \begin{itemize}
51 \item Section~\ref{section-gd-namespaces} gives and overview of the
52 available namespaces and also of naming conventions used in the graph
53 drawing system.
54 \item Section~\ref{section-gd-gd-scope} explores what graph drawing scopes
55 ``look like on the algorithm layer''. As the graph of a graph drawing
56 scope is being parsed on the display layer, a lot of information is
57 gathered: The nodes and edges of the graph are identified and the
58 object-oriented model is built, but other information is also
59 collected. For instance, a sequence of \emph{events} is created during
60 the parsing process. As another example, numerous kinds of
61 \emph{collections} may be identified by the parser. The parsed graph
62 together with the event sequence and the collections are all gathered
63 in a single table, called the \emph{scope table} of the current graph
64 drawing scope. Algorithms can access this table to retrieve information
65 that goes beyond the ``pure'' graph model.
66
67 One entry in this table is of particular importance: The
68 \emph{syntactic digraph.} While most graph drawing algorithms are not
69 really interested in the ``details'' of how a graph was specified, for
70 some algorithms it makes a big difference whether you write |a -> b| or
71 |b <- a| in your specification of the graph. These algorithms can
72 access the ``fine details'' of how the input graph was specified
73 through the syntactic digraph; all other algorithms can access their
74 |digraph| or |ugraph| fields and do not have to worry about the
75 difference between |a -> b| and |b <- a|.
76 \item Section~\ref{section-gd-models} explains the object-oriented model of
77 graphs used throughout the graph drawing system. Graph drawing
78 algorithms do not get the ``raw'' specification used by the user to
79 specify a graph (like |{a -> {b,c}}| in the |graph| syntax). Instead,
80 what a graph drawing algorithm sees is ``just'' a graph object that
81 provides methods for accessing the vertices and arcs.
82 \item Section~\ref{section-gd-transformations} explains how the information
83 in the graph drawing scope is processed. One might expect that we
84 simply run the algorithm selected by the user; however, things are more
85 involved in practice. When the layout of a graph needs to be computed,
86 only very few algorithms will actually be able to compute positions for
87 the nodes of \emph{every} graph. For instance, most algorithms
88 implicitly assume that the input graph is connected; algorithms for
89 computing layouts for trees assume that the input is, well, a tree; and
90 so on. For this reason, graph drawing algorithms will not actually need
91 the original input graph as their input, but some \emph{transformed}
92 version of it. Indeed, \emph{all} graph drawing algorithms are treated
93 as graph transformations by the graph drawing engine.
94
95 This section explains how transformations are chosen and which
96 transformations are applied by default.
97 \item Section~\ref{section-gd-interface-to-algorithms} documents the
98 interface-to-algorithm class. This interface encapsulates all that an
99 algorithm ``sees'' of the graph drawing system (apart from the classes
100 in |model| and |lib|).
101 \item Section~\ref{section-gd-examples} provides a number of complete
102 examples that show how graph drawing algorithms can, actually, be
103 implemented.
104 \item Section~\ref{section-gd-libs} documents the different libraries
105 functions that come with the graph drawing engine. For instance, there
106 are library functions for computing the (path) distance of nodes in a
107 graph; a parameter that is needed by some algorithms.
108 \end{itemize}
109
110
111 \subsection{Getting Started}
112
113 In this section, a ``hello world'' example of a graph drawing algorithm is
114 given, followed by an overview of the organization of the whole engine.
115
116
117 \subsubsection{The Hello World of Graph Drawing}
118
119 Let us start our tour of the algorithm layer with a ``hello world'' version of
120 graph drawing: An algorithm that simply places all nodes of a graph in a circle
121 of a fixed radius. Naturally, this is not a particularly impressive or
122 intelligent graph drawing algorithm; but neither is the classical ``hello
123 world''$\dots$\ Here is a minimal version of the needed code (this is not the
124 typical way of formulating the code, but it is the shortest; we will have a
125 look at the more standard and verbose way in a moment):
126 %
127 \begin{codeexample}[code only, tikz syntax=false]
128 pgf.gd.interface.InterfaceToAlgorithms.declare {
129 key = "very simple demo layout",
130 algorithm = {
131 run =
132 function (self)
133 local alpha = (2 * math.pi) / #self.ugraph.vertices
134 for i,vertex in ipairs(self.ugraph.vertices) do
135 vertex.pos.x = math.cos(i * alpha) * 25
136 vertex.pos.y = math.sin(i * alpha) * 25
137 end
138 end
139 }
140 }
141 \end{codeexample}
142 \directlua{
143 pgf.gd.interface.InterfaceToAlgorithms.declare {
144 key = "very simple demo layout",
145 algorithm = {
146 run =
147 function (self)
148 local alpha = (2 * math.pi) / \luaescapestring{#}self.ugraph.vertices
149 for i,vertex in ipairs(self.ugraph.vertices) do
150 vertex.pos.x = math.cos(i * alpha) * 25
151 vertex.pos.y = math.sin(i * alpha) * 25
152 end
153 end
154 }
155 }
156 }
157
158 This code \emph {declares} a new algorithm (|very simple demo layout|) and
159 includes an implementation of the algorithm (through the |run| field of the
160 |algorithm| field). When the |run| method is called, the |self| parameter will
161 contain the to-be-drawn graph in its |ugraph| field. It is now the job of the
162 code to modify the positions of the vertices in this graph (in the example,
163 this is done by assigning values to |vertex.pos.x| and |vertex.pos.y|).
164
165 In order to actually \emph{use} the algorithm, the above code first needs to be
166 executed somehow. For \tikzname, one can just call |\directlua| on it or put it
167 in a file and then use |\directlua| plus |require| (a better alternative) or
168 you put it in a file like |simpledemo.lua| and use |\usegdlibrary{simpledemo}|
169 (undoubtedly the ``best'' way). For another display layer, like a graphical
170 editor, the code could also be executed through the use of |require|.
171
172 Executing the code ``just'' declares the algorithm, this is what the |declare|
173 function does. Inside some internal tables, the algorithm layer will store the
174 fact that a |very simple demo layout| is now available. The algorithm layer
175 will also communicate with the display layer through the binding layer to
176 advertise this fact to the ``user''. In the case of \tikzname, this means that
177 the option key |very simple demo layout| becomes available at this point and we
178 can use it like this:
179 %
180 \begin{codeexample}[]
181 \tikz [very simple demo layout]
182 \graph { f -> c -> e -> a -> {b -> {c, d, f}, e -> b}};
183 \end{codeexample}
184
185 It turns out, that our little algorithm is already more powerful than one might
186 expect. Consider the following example:
187 %
188 \begin{codeexample}[]
189 \tikz [very simple demo layout, componentwise]
190 \graph {
191 1 -> 2 ->[orient=right] 3 -> 1;
192 a -- b --[orient=45] c -- d -- a;
193 };
194 \end{codeexample}
195
196 Note that, in our algorithm, we ``just'' put all nodes on a circle around the
197 origin. Nevertheless, the graph gets decomposed into two connected components,
198 the components are rotated so that the edge from node |2| to node |3| goes from
199 left to right and the edge from |b| to |c| goes up at an angle of $45^\circ$,
200 and the components are placed next to each other so that some spacing is
201 achieved.
202
203 The ``magic'' that achieves all this behind the scenes is called ``graph
204 transformations''. They will heavily pre- and postprocess the input and output
205 of graph drawing algorithms to achieve the above results.
206
207 Naturally, some algorithms may not wish their inputs and/or outputs to be
208 ``tampered'' with. An algorithm can easily configure which transformations
209 should be applied, by passing appropriate options to |declare|.
210
211
212 \subsubsection{Declaring an Algorithm}
213
214 Let us now have a look at how one would ``really'' implement the example
215 algorithm. First of all, we place our algorithm in a separate file called, say,
216 |ExampleLayout.lua|. This way, by putting it in a separate file, all display
217 layers can easily install the algorithm at runtime by saying
218 |require "ExampleLayout"|.
219
220 Next, the |declare| function is needed quite often, so it makes sense to create
221 a short local name for it:
222 %
223 \begin{codeexample}[code only, tikz syntax=false]
224 -- This is the file ExampleLayout.lua
225 local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
226 \end{codeexample}
227
228 The |declare| function is the work-horse of the algorithm layer. It takes a
229 table that contains at least a |key| field, which must be a unique string, and
230 some other fields that specify in more detail what kind of key is declared.
231 Once declared through a call of |declare|, the ``key'' can be used on the
232 display layer.
233
234 For declaring an algorithm, the table passed to |declare| must contain a field
235 |algorithm|. This field, in turn, must (normally) be set to a table that will
236 become the algorithm class. In the above example, our algorithm was so simple
237 that we could place the whole definition of the class inside the call of
238 |declare|, but normally the class is defined in more detail after the call to
239 |declare|:
240 %
241 \begin{codeexample}[code only, tikz syntax=false]
242 local ExampleClass = {} -- A local variable holding the class table
243
244 declare {
245 key = "very simple demo layout",
246 algorithm = ExampleClass
247 }
248
249 function ExampleClass:run ()
250 local alpha = (2 * math.pi) / #self.ugraph.vertices
251 ...
252 end
253 \end{codeexample}
254
255 The effect of the |declare| will be that the table stored in |ExampleClass| is
256 setup to form a class in the sense of object-oriented programming. In
257 particular, a static |new| function is installed.
258
259 Now, whenever the user uses the key |very simple demo layout| on a graph, at
260 some point the graph drawing engine will create a new instance of the
261 |ExampleClass| using |new| and will then call the |run| method of this class.
262 The class can have any number of other methods, but |new| and |run| are the
263 only ones directly called by the graph drawing system.
264
265
266 \subsubsection{The Run Method}
267
268 The |run| method of an algorithm classes lies at the heart of any graph drawing
269 algorithm. This method will be called whenever a graph needs to be laid out.
270 Upon this call, the |self| object will have some important fields set:
271 %
272 \begin{itemize}
273 \item |ugraph| This stands for ``undirected graph'' and is the
274 ``undirected'' version of the to-be-laid out graph. In this graph,
275 whenever there is an arc between $u$ and $v$, there is also an arc
276 between $v$ and $u$. It is obtained by considering the syntactic
277 digraph and then ``forgetting'' about the actual direction of the
278 edges.
279
280 When you have set certain |preconditions| in your algorithm class, like
281 |connected=true|, the |ugraph| will satisfy these conditions. In
282 particular, the |ugraph| typically will not be the underlying
283 undirected graph of the complete syntactic digraph, but rather of some
284 part of it. The use of (sub)layouts will also modify the syntactic
285 digraph is fancy ways.
286
287 Refer to this graph whenever your algorithm is ``most comfortable''
288 with an undirected graph, as is the case for instance for most
289 force-base algorithms.
290 \item |digraph| This stands for ``directed graph'' and is the
291 ``semantically directed'' version of the to-be-laid out graph.
292 Basically, when happens is that reverse edges in the syntactic digraph
293 (an edge like |b <- a|) will yield an |Arc| from |a| to |b| in the
294 |digraph| while they yield a |b| to |a| arc and edge in the syntactic
295 digraph. Also, undirected edges like |a -- b| are replaced by directed
296 edges in both directions between the vertices.
297 \item |scope| The graph drawing scope.
298 \item |layout| The layout object for this graph. This is a collection of
299 kind |layout|.
300 \end{itemize}
301
302
303 \subsubsection{Loading Algorithms on Demand}
304
305 In order to use the |very simple demo layout| on the display layer, |declare|
306 must have been called for this key. However, we just saw that the |declare|
307 function takes the actual class table as parameter and, thus, whenever an
308 algorithm is declared, it is also completely loaded and compiled at this point.
309
310 This is not always desirable. A user may wish to include a number of libraries
311 in order to declare a large number of potentially useful algorithms, but will
312 not actually use all of them. Indeed, at least for large, complex algorithms,
313 it is preferable that the algorithm's code is loaded only when the algorithm is
314 used for the first time.
315
316 Such a ``loading of algorithms on demand'' is supported through the option of
317 setting the |algorithm| field in a |declare| to a string. This string must now
318 be the file name of a Lua file that contains the code of the actual algorithm.
319 When the key is actually used for the first time, this file will be loaded. It
320 must return a table that will be plugged into the |algorithm| field; so
321 subsequent usages of the key will not load the file again.
322
323 The net effect of all this is that you can place implementations of algorithms
324 in files separate from interface files that just contain the |declare| commands
325 for these algorithms. You will typically do this only for rather large
326 algorithms.
327
328 For our example, the code would look like this:
329 %
330 \begin{codeexample}[code only, tikz syntax=false]
331 -- File ExampleLayout.lua
332 local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
333 declare {
334 key = "very simple demo layout",
335 algorithm = "ExampleLayoutImplementation"
336 }
337 \end{codeexample}
338
339 \begin{codeexample}[code only, tikz syntax=false]
340 -- File ExampleLayoutImplementation.lua
341 local ExampleClass = {}
342 function ExampleClass:run ()
343 local alpha = (2 * math.pi) / #self.ugraph.vertices
344 ...
345 end
346 return ExampleClass
347 \end{codeexample}
348
349
350 \subsubsection{Declaring Options}
351
352 Let us now make our example algorithm a bit more ``configurable''. For this, we
353 use |declare| once more, but instead of the |algorithm| field, we use a |type|
354 field. This tells the display layer that the key is not used to select an
355 algorithm, but to configure ``something'' about the graph or about nodes or
356 edges.
357
358 In our example, we may wish to configure the radius of the graph. So, we
359 introduce a |radius| key (actually, this key already exists, so we would not
360 need to declare it, but let us do so anyway for example purposes):
361 %
362 \begin{codeexample}[code only, tikz syntax=false]
363 declare {
364 key = "radius",
365 type = "length",
366 initial = "25pt"
367 }
368 \end{codeexample}
369
370 This tells the display layer that there is now an option called |radius|, that
371 users set it to some ``length'', and that if it is not set at all, then the
372 25pt should be used.
373
374 To access what the user has specified for this key, an algorithm can access the
375 |options| field of a graph, vertex, or arc at the key's name:
376 %
377 \begin{codeexample}[code only, tikz syntax=false]
378 vertex.pos.x = math.cos(i * alpha) * vertex.options.radius
379 vertex.pos.y = math.sin(i * alpha) * vertex.options.radius
380 \end{codeexample}
381
382
383 \subsubsection{Adding Inline Documentation}
384
385 You should always document the keys you |declare|. For this, the |declare|
386 function allows you to add three fields to its argument table:
387 %
388 \begin{itemize}
389 \item |summary| This should be a string that succinctly summarizes the
390 effect this key has. The idea is that this text will be shown as a
391 ``tooltip'' in a graphical editor or will be printed out by a command
392 line tool when a user requests help about the key. You can profit from
393 using Lua's |[[| and |]]| syntax for specifying multi-line strings.
394
395 Also, when the file containing the key is parsed for this manual, this
396 text will be shown.
397 \item |documentation| When present, this field contains a more extensive
398 documentation of the key. It will also be shown in this manual, but
399 typically not as a tool tip.
400 \item |examples| This should either be a single string or an array of
401 strings. Each string should be an example demonstrating how the key is
402 used in \tikzname. They will all be included in the manual, each
403 surrounded by a |codeexample| environment.
404 \end{itemize}
405
406 Let us augment our |radius| key with some documentation. The three dashes
407 before the |declare| are only needed when the declaration is part of this
408 manual and they will trigger an inclusion of the key in the manual.
409 %
410 \begin{codeexample}[code only, tikz syntax=false]
411 ---
412 declare {
413 key = "radius",
414 type = "length",
415 initial = "25pt",
416 summary = [[
417 Specifies the radius of a circle on which the nodes are placed when
418 the |very simple example layout| is used. Each vertex can have a
419 different radius.
420 ]],
421 examples = [[
422 \tikz \graph [very simple example layout, radius=2cm] {
423 a -- b -- c -- d -- e;
424 };
425 ]]
426 }
427 \end{codeexample}
428
429 As a courtesy, all of the strings given in the documentation can start and end
430 with quotation marks, which will be removed. (This helps syntax highlighting
431 with editors that do not recognize the |[[| to |]]| syntax.) Also, the
432 indentation of the strings is removed (we compute the minimum number of leading
433 spaces on any line and remove this many spaces from all lines).
434
435
436 \subsubsection{Adding External Documentation}
437 \label{section-gd-documentation-in}
438
439 As an alternative to inlining documentation, you can also store the
440 documentation of keys in a separate file that is loaded only when the
441 documentation is actually accessed. Since this happens only rarely (for
442 instance, not at all, when \tikzname\ is run, except for this manual), this
443 will save time and space. Also, for C code, it is impractical to store
444 multi-line documentation strings directly in the C file.
445
446 In order to store documentation externally, instead of the |summary|,
447 |documentation|, and |examples| keys, you provide the key |documentation_in|.
448 The |documentation_in| key must be set to a string that is input using
449 |require|.
450
451 In detail, when someone tries to access the |summary|, |documentation|, or
452 |examples| field of a key and these keys are not (yet) defined, the system
453 checks whether the |documentation_in| key is set. If so, we apply |require| to
454 the string stored in this field. The file loaded in this way can now setup the
455 missing fields of the current key and, typically, also of all other keys
456 defined in the same file as the current key. For this purpose, it is advisable
457 to use the |pgf.gd.doc| class:
458
459 \includeluadocumentationof{pgf.gd.doc}
460
461 As a longer example, consider the following declarations:
462 %
463 \begin{codeexample}[code only, tikz syntax=false]
464 ---
465 declare {
466 key = "very simple demo layout",
467 algorithm = ExampleClass,
468 documentation_in = "documentation_file"
469 }
470
471 ---
472 declare {
473 key = "radius",
474 type = "length",
475 initial = "25",
476 documentation_in = "documentation_file"
477 }
478 \end{codeexample}
479
480 The file |documentation_file.lua| would look like this:
481 %
482 \begin{codeexample}[code only, tikz syntax=false]
483 -- File documentation_file.lua
484 local key = require 'pgf.gd.doc'.key
485 local documentation = require 'pgf.gd.doc'.documentation
486 local summary = require 'pgf.gd.doc'.summary
487 local example = require 'pgf.gd.doc'.example
488
489 key "very simple demo layout"
490 documentation "This layout is a very simple layout that, ..."
491
492 key "radius"
493 summary "Specifies the radius of a circle on which the nodes are placed."
494 documentation
495 [[
496 This key can be used together with |very simple example layout|. An
497 important feature is that...
498 ]]
499 example
500 [[
501 \tikz \graph [very simple example layout, radius=2cm]
502 { a -- b -- c -- d -- e; };
503 ]]
504 \end{codeexample}
505
506
507 \subsection{Namespaces and File Names}
508 \label{section-gd-namespaces}
509
510 \subsubsection{Namespaces}
511
512 All parts of the |graphdrawing| library reside in the Lua ``namespace''
513 |pgf.gd|, which is itself a ``sub-namespace'' of |pgf|. For your own
514 algorithms, you are free to place them in whatever namespace you like; only for
515 the official distribution of \pgfname\ everything has been put into the correct
516 namespace.
517
518 Let us now have a more detailed look at these namespaces. A namespace is just a
519 Lua table, and sub-namespaces are just subtables of namespace tables. Following
520 the Java convention, namespaces are in lowercase letters. The following
521 namespaces are part of the core of the graph drawing engine:
522 %
523 \begin{itemize}
524 \item |pgf| This namespace is the main namespace of \pgfname. Other parts
525 of \pgfname\ and \tikzname\ that also employ Lua should put an entry
526 into this table. Since, currently, only the graph drawing engine
527 adheres to this rule, this namespace is declared inside the graph
528 drawing directory, but this will change.
529
530 The |pgf| table is the \emph{only} entry into the global table of Lua
531 generated by the graph drawing engine (or, \pgfname, for that matter).
532 If you intend to extend the graph drawing engine, do not even
533 \emph{think} of polluting the global namespace. You will be fined.
534 \item |pgf.gd| This namespace is the main namespace of the graph drawing
535 engine, including the object-oriented models of graphs and the layout
536 pipeline. Algorithms that are part of the distribution are also inside
537 this namespace, but if you write your own algorithms you do not need
538 place them inside this namespace. (Indeed, you probably should not
539 before they are made part of the official distribution.)
540 \item |pgf.gd.interface| This namespace handles, on the one hand, the
541 communication between the algorithm layer and the binding layer and, on
542 the other hand, the communication between the display layer (\tikzname)
543 and the binding layer.
544 \item |pgf.gd.binding| So-called ``bindings'' between display layers and
545 the graph drawing system reside in this namespace.
546 \item |pgf.gd.lib| Numerous useful classes that ``make an algorithm's your
547 life easier'' are collected in this namespace. Examples are a class for
548 decomposing a graph into connected components or a class for computing
549 the ideal distance between two sibling nodes in a tree, taking all
550 sorts of rotations and separation parameters into account.
551 \item |pgf.gd.model| This namespace contains all Lua classes that are part
552 of the object-oriented model of graphs employed throughout the graph
553 drawing engine. For readers familiar with the model--view--controller
554 pattern: This is the namespace containing the model-part of this
555 pattern.
556 \item |pgf.gd.control| This namespace contains the ``control logic'' of the
557 graph drawing system. It will transform graphs according to rules,
558 disassemble layouts and sublayouts and will call the appropriate
559 algorithms. For readers still familiar with the model--view--controller
560 pattern: This is the namespace containing the control-part of this
561 pattern.
562 \item |pgf.gd.trees| This namespace contains classes that are useful for
563 dealing with graphs that are trees. In particular, it contains a class
564 for computing a spanning tree of an arbitrary connected graph; an
565 operation that is an important preprocessing step for many algorithms.
566
567 In addition to providing ``utility functions for trees'', the namespace
568 \emph{also} includes actual algorithms for computing graph layouts like
569 |pgf.gd.trees.ReingoldTilford1981|. It may seem to be a bit of an
570 ``impurity'' that a namespace mixes utility classes and ``real''
571 algorithms, but experience has shown that it is better to keep things
572 together in this way.
573
574 Concluding the analogy to the model--view--controller pattern, a graph
575 drawing algorithm is, in a loose sense, the ``view'' part of the
576 pattern.
577 \item |pgf.gd.layered| This namespace provides classes and functions for
578 ``layered'' layouts; the Sugiyama layout method being the most
579 well-known one. Again, the namespace contains both algorithms to be
580 used by a user and utility functions.
581 \item |pgf.gd.force| Collects force-based algorithms and, again, also
582 utility functions and classes.
583 \item |pgf.gd.examples| Contains some example algorithms. They are
584 \emph{not} intended to be used directly, rather they should serve as
585 inspirations for readers wishing to implement their own algorithms.
586 \end{itemize}
587
588 There are further namespaces that also reside in the |pgf.gd| namespace, these
589 namespaces are used to organize different graph drawing algorithms into
590 categories.
591
592 In Lua, similarly to Java, when a class |SomeClass| is part of, say, the
593 namespace |pgf.gd.example|, it is customary to put the class's code in a file
594 |SomeClass.lua| and then put this class in a directory |example|, that is a
595 subdirectory of a directory |gd|, which is in turn a subdirectory of a
596 directory |pgf|. When you write \texttt{require "pgf.gd.example.SomeClass"} the
597 so-called \emph{loader} will turn this into a request for the file
598 \texttt{pgf/gd/example/SomeClass.lua} (for Unix systems).
599
600
601 \subsubsection{Defining and Using Namespaces and Classes}
602
603 There are a number of rules concerning the structure and naming of namespaces
604 as well as the naming of files. Let us start with the rules for naming
605 namespaces, classes, and functions. They follow the ``Java convention'':
606 %
607 \begin{enumerate}
608 \item A namespace is a short lowercase |word|.
609 \item A function in a namespace is in
610 |lowercase_with_underscores_between_words|.
611 \item A class name is in |CamelCaseWithAnUppercaseFirstLetter|.
612 \item A class method name is in |camelCaseWithALowercaseFirstLetter|.
613 \end{enumerate}
614
615 From Lua's point of view, every namespace and every class is just a table.
616 However, since these tables will be loaded using Lua's |require| function, each
617 namespace and each class must be placed inside a separate file (unless you
618 modify the |package.loaded| table, but, then, you know what you are doing
619 anyway). Inside such a file, you should first declare a local variable whose
620 name is the name of the namespace or class that you intend to define and then
621 assign a (possibly empty) table to this variable:
622 %
623 \begin{codeexample}[code only, tikz syntax=false]
624 -- File pgf.gd.example.SomeClass.lua:
625 local SomeClass = {}
626 \end{codeexample}
627 %
628 Next, you should add your class to the encompassing namespace. This is achieved
629 as follows:
630 %
631 \begin{codeexample}[code only, tikz syntax=false]
632 require("pgf.gd.example").SomeClass = SomeClass
633 \end{codeexample}
634 %
635 The reason this works is that the |require| will return the table that is the
636 namespace |pgf.gd.example|. So, inside this namespace, the |SomeClass| field
637 will be filled with the table stored in the local variable of the same name --
638 which happens to be the table representing the class.
639
640 At the end of the file, you must write
641 %
642 \begin{codeexample}[code only, tikz syntax=false]
643 return SomeClass
644 \end{codeexample}
645 %
646 This ensures that the table that is defined in this file gets stored by Lua in
647 the right places. Note that you need and should not use Lua's |module| command.
648 The reason is that this command has disappeared in the new version of Lua and
649 that it is not really needed.
650
651 Users of your class can import and use your class by writing:
652 %
653 \begin{codeexample}[code only, tikz syntax=false]
654 ...
655 local SomeClass = require "pgf.gd.examples.SomeClass"
656 ...
657 \end{codeexample}
658
659
660 \subsection{The Graph Drawing Scope}
661 \label{section-gd-gd-scope}
662
663 \includeluadocumentationof{pgf.gd.interface.Scope}
664
665
666 \subsection{The Model Classes}
667 \label{section-gd-models}
668
669 All that a graph drawing algorithm will ``see'' of the graph specified by the
670 user is a ``graph object''. Such an object is an object-oriented model of the
671 user's graph that no longer encodes the specific way in which the user
672 specified the graph; it only encodes which nodes and edges are present. For
673 instance, the \tikzname\ graph specification
674 %
675 \begin{codeexample}[code only]
676 graph { a -- {b, c} }
677 \end{codeexample}
678 %
679 \noindent and the graph specification
680 %
681 \begin{codeexample}[code only]
682 node (a) { a }
683 child { node (b) {b} }
684 child { node (c) {c} }
685 \end{codeexample}
686 %
687 will generate exactly the same graph object.
688
689 \begin{luanamespace}{pgf.gd.}{model}
690 This namespace contains the classes modeling graphs, nodes, and edges.
691 Also, the |Coordinate| class is found here, since coordinates are also part
692 of the modeling.
693 \end{luanamespace}
694
695
696 \subsubsection{Directed Graphs (Digraphs)}
697
698 Inside the graph drawing engine, the only model of a graph that is available
699 treats graphs as
700 %
701 \begin{enumerate}
702 \item directed (all edges have a designated head and a designated tail) and
703 \item simple (there can be at most one edge between any pair of nodes).
704 \end{enumerate}
705 %
706 These two properties may appear to be somewhat at odds with what users can
707 specify as graphs and with what some graph drawing algorithms might expect as
708 input. For instance, suppose a user writes
709 %
710 \begin{codeexample}[code only]
711 graph { a -- b --[red] c, b --[green, bend right] c }
712 \end{codeexample}
713 %
714 In this case, it seems that the input graph for a graph drawing algorithm
715 should actually be an \emph{undirected} graph in which there are
716 \emph{multiple} edges (namely $2$) between |b| and~|c|. Nevertheless, the graph
717 drawing engine will turn the user's input a directed simple graph in ways
718 described later. You do not need to worry that information gets lost during
719 this process: The \emph{syntactic digraph,} which is available to graph drawing
720 algorithms on request, stores all the information about which edges are present
721 in the original input graph.
722
723 The main reasons for only considering directed, simple graphs are speed and
724 simplicity: The implementation of these graphs has been optimized so that all
725 operations on these graphs have a guaranteed running time that is small in
726 practice.
727
728 \includeluadocumentationof{pgf.gd.model.Digraph}
729
730
731 \subsubsection{Vertices}
732
733 \includeluadocumentationof{pgf.gd.model.Vertex}
734
735
736 \subsubsection{Arcs}
737 \label{section-gd-arc-model}
738
739 \includeluadocumentationof{pgf.gd.model.Arc}
740
741
742 \subsubsection{Edges}
743
744 \includeluadocumentationof{pgf.gd.model.Edge}
745
746
747 \subsubsection{Collections}
748
749 \includeluadocumentationof{pgf.gd.model.Collection}
750
751
752 \subsubsection{Coordinates, Paths, and Transformations}
753
754 \includeluadocumentationof{pgf.gd.model.Coordinate}
755 \includeluadocumentationof{pgf.gd.model.Path}
756 \includeluadocumentationof{pgf.gd.lib.Transform}
757
758
759 \subsubsection{Options and Data Storages for Vertices, Arcs, and Digraphs}
760
761 Many objects in the graph drawing system have an |options| table attached to
762 them. These tables will contain the different kinds options specified by the
763 user for the object. For efficiency reasons, many objects may share the same
764 options table (since, more often than not, almost all objects have exactly the
765 same |options| table). For this reason, you cannot store anything in an options
766 table, indeed, you should never attempt to write anything into an options
767 table. Instead, you should use a |Storage|.
768
769 \includeluadocumentationof{pgf.gd.lib.Storage}
770
771
772 \subsubsection{Events}
773
774 \includeluadocumentationof{pgf.gd.lib.Event}
775
776
777 \subsection{Graph Transformations}
778 \label{section-gd-transformations}
779
780 \subsubsection{The Layout Pipeline}
781
782 \includeluadocumentationof{pgf.gd.control.LayoutPipeline}
783
784
785 \subsubsection{Hints For Edge Routing}
786
787 \includeluadocumentationof{pgf.gd.routing.Hints}
788
789
790 \subsection{The Interface To Algorithms}
791 \label{section-gd-interface-to-algorithms}
792
793 \includeluadocumentationof{pgf.gd.interface.InterfaceToAlgorithms}
794
795
796 \subsection{Examples of Implementations of Graph Drawing Algorithms}
797 \label{section-gd-examples}
798
799 \includeluadocumentationof{pgf.gd.examples.library}
800 \includeluadocumentationof{pgf.gd.examples.SimpleDemo}
801 \includeluadocumentationof{pgf.gd.examples.SimpleEdgeDemo}
802 \includeluadocumentationof{pgf.gd.examples.SimpleHuffman}
803
804
805 \subsection{Support Libraries}
806 \label{section-gd-libs}
807
808 The present section lists a number of general-purpose libraries that are used
809 by different algorithms.
810
811 \subsubsection{Basic Functions}
812
813 \includeluadocumentationof{pgf}
814
815 \includeluadocumentationof{pgf.gd.lib}
816
817
818 \subsubsection{Lookup Tables}
819
820 \includeluadocumentationof{pgf.gd.lib.LookupTable}
821
822
823 \subsubsection{Computing Distances in Graphs}
824
825 \emph{Still needs to be ported to digraph classes!}
826
827 %\includeluadocumentationof{pgf.gd.lib.PathLengths}
828
829
830 \subsubsection{Priority Queues}
831
832 \includeluadocumentationof{pgf.gd.lib.PriorityQueue}