summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/doc/text-en/pgfmanual-en-gd-usage-pgf.tex
blob: be04bb93d455905af121df268fd739a51ad385d0 (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
% Copyright 2010-2019 by Renée Ahrens
% Copyright 2010-2019 by Olof Frahm
% Copyright 2010-2019 by Jens Kluttig
% Copyright 2010-2019 by Matthias Schulz
% Copyright 2010-2019 by Stephan Schuster
% Copyright 2019 by Jannis Pohlmann
% Copyright 2019 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{Using Graph Drawing in PGF}
\label{section-gd-pgf}

{\noindent {\emph{by Till Tantau}}}

\begin{purepgflibrary}{graphdrawing}
    This package provides the core support for graph drawing inside \pgfname.
    It does so by providing \pgfname\ macros for controlling the graph drawing
    system, but also implements the binding to the graph drawing system (see
    Section~\ref{section-gd-binding-layer} for details on bindings).
\end{purepgflibrary}

\ifluatex
\else
    This section of the manual can only be typeset using Lua\TeX.
    \expandafter\endinput
\fi


\subsection{Overview}

Just like everywhere else in \pgfname, \tikzname\ is ``just a convenient
syntax'' in the context of graph drawing. The ``hard work'' of binding the
internal representations of nodes and edges with the graph drawing system
written in Lua is not done by \tikzname, but rather by a set of macros that are
part of the basic \pgfname\ layer.

The documentation of the \pgfname\ part of the graph drawing system that is
presented in the following includes only those macros that other \TeX\ packages
could conceivably call in order to use the graph drawing system without using
\tikzname; for instance, for efficiency reasons. (The internal callback
functions defined in the |graphdrawing| library that are part of the binding
between \pgfname\ and the graph drawing system are not documented, should not
be called, and may change in the future.)


\subsection{How Graph Drawing in PGF Works}

The core idea behind graph drawing in \pgfname\ is that inside special
\emph{graph drawing scopes} whenever \pgfname\ creates a node, we intercept
this node creation and \emph{do not} immediately place the node. Rather, we
pass it down to Lua part of the graph drawing system via calls to appropriate
methods of the (Lua) class |InterfaceToDisplay|. The effect will be that the
nodes are ``tucked away'' in some internal tables. For edges, we introduce a
special command called |\pgfgdedge| that tells the graph drawing system that
there is an edge between two tucked-away nodes. Then, at the end of the graph
drawing scope, a graph drawing algorithm written in Lua starts to work on the
graph by computing new positions for the nodes. Once the algorithm has
finished, the graph drawing system starts sending back the nodes and edges to
\pgfname\ via the methods of the class |BindingToPGF|. These methods reinsert
some code into the \TeX\ output stream that finally places the nodes at their
final positions. Note that graph drawing algorithms are perfectly oblivious to
all of this; indeed, the graph drawing algorithms can even be used
independently of \TeX.

Let us have a look at a simple example to see what happens when a graph is
specified:
%
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}}]
\tikz[tree layout]
  \graph {root [as=Hello] -> World[fill=blue!20]};
\end{codeexample}

The key |tree layout| internally calls the key |request scope and layout|,
which in turn calls the macro |\pgfgdbeginscope|, which starts a graph drawing
scope inside the graph drawing system. Once this macro has been called, until
the next call of |\pgfgdendscope|, all nodes that are created actually get
passed down to the graph drawing engine. This is implemented on the lowest
layer, namely by directly intercepting nodes freshly created using |\pgfnode|.
In our example, this happens in two places: For the |root| node and for the
|World| node. The |graphs| library and \tikzname\ internally call the
|\pgfnode| macro for these two nodes (after a large number of internal syntax
translations, but the graph drawing system does not care about them).

Note that the node boxes will have been fully created before they are passed
down to the graph drawing engine -- only their final position is not yet fixed.
It is not possible to modify the size of nodes inside the graph drawing engine,
but you can create new nodes in certain situations.

In contrast, the single edge of the graph that is created by the |->| command
is not fully created before it is passed down to the graph drawing system. This
would not really make sense since before the final positions of the nodes are
fixed, we cannot even begin to compute the length of this edge, let alone where
it should start or end. For this reason, on the upper \tikzname\ layer, the
normal edge creation that would be caused by |->| via |new ->| is suppressed.
Instead, the command |\pgfgdedge| is called. Similarly, inside a graph drawing
scope, \tikzname\ will suppress both the |edge| and the |edge from parent|
command and cause |\pgfgdedge| to be called instead.

An overview of what happens is illustrated by the following call graph:

\bigskip

\begin{tikzpicture}[
    class name/.style={draw,minimum size=20pt, fill=blue!20},
    object node/.style={draw,minimum size=15pt, fill=yellow!20},
    p/.style={->,>={Stealth[round,sep]}},
    livespan/.style={very thick},
    xscale=0.8,
]
    % class names above
    \node (tikz) at (0,4) [class name] {\tikzname\ layer (\TeX)};
    \node (tex) at (6,4) [class name] {\pgfname\ layer (\TeX)};
    \node (interface) at (13,4) [class name] {Display layer (Lua)};
    % lines from the class names to the bottom of the picture
    \draw[livespan] (tikz) -- (0,-6.5);
    \draw[livespan] (tex) -- (6,-6.5);
    \draw[livespan] (interface) -- (13,-6.5);
    % first command: \graph{  -- generates new graph in lua interface
    \node (tikz-begin-graph) at (0,3) [object node] {|\graph[... layout]{|}; %}
    \node (tex-begin-graph) at (6,3) [object node] {|\pgfgdbeginscope|};
    \node (interface-new-graph) at (13,3) [object node] {|beginGraphDrawingScope(|...|)|};
    \draw [p] (tikz-begin-graph.east) -- (tex-begin-graph.west);
    \draw [p] (tex-begin-graph.east) -- (interface-new-graph.west);
    % second command: a -> b   -- generates two nodes in lua
    % and one edge
    \node (tikz-node) at (0,2) [object node] {|a -> b;|};
    \node (tex-node) at (6,2) [object node, double copy shadow] {|\pgfnode|};
    \draw[p] (tikz-node.east) -- (tex-node.west);

    \node (interface-add-node) at (13,2) [object node, double copy shadow] {|createVertex(|...|)|};
    \draw[p] (tex-node.east) -- (interface-add-node.west);

    \node (tex-add-edge) at (6,1) [object node, double copy shadow] {|\pgfgdedge|};
    \node (interface-add-edge) at (13,1) [object node, double copy shadow] {|createEdge(|...|)|};
    \draw[p] (tikz-node.east) -- (1.5,2) -- (1.5,1) -- (tex-add-edge.west);
    \draw[p] (tex-add-edge.east) -- (interface-add-edge.west);

    % scope ends -- cloes graph, layouts it and draws it
    \node (tikz-end) at (0,0) [object node] {|};|};
    \node (tex-end) at (6,0) [object node] {|\pgfgdendscope|};
    \node (interface-draw-graph) at (13,0) [object node] {|runGraphDrawingAlgorithm()|};
    \node (interface-finish-graph) at (13,-2) [object node] {|endGraphDrawingScope()|};

    \node (invoke-algorithm) at (15.5,-1) [object node] {invoke algorithm};
    \draw[p] (tikz-end.east) -- (tex-end.west);
    \draw[p] (tex-end.east) -- (interface-draw-graph.west);
    \draw[p] (interface-draw-graph.east) -| (invoke-algorithm.20);
    \draw[p] (tex-end.east) -- (9.5,0) -- (9.5,-2) -- (interface-finish-graph.west);

    % begin shipout
    \node (tex-begin-shipout) at (6,-3) [object node] {|\pgfgdcallbackbeginshipout|};

    \node (tex-puttexbox) at (6,-4) [object node, double copy shadow] {|\pgfgdcallbackrendernode|};
    \node (tex-putedge) at (6,-5) [object node, double copy shadow] {|\pgfgddefaultedgecallback|};

    \node (tex-end-shipout) at (6,-6) [object node] {|\pgfgdcallbackendshipout|};

    \draw [p] (interface-finish-graph.-170) |- (tex-begin-shipout.east);
    \draw [p] (interface-finish-graph.-170) |- (tex-puttexbox.east);
    \draw [p] (interface-finish-graph.-170) |- (tex-putedge.east);
    \draw [p] (interface-finish-graph.-170) |- (tex-end-shipout.east);
    %(interface-finish-graph.east) -- (12.5,-2) -- (12.5,-4) -- (sys-puttexbox.west);

    % put edge
    %(interface-finish-graph.east) -- (12.5,-2) -- (12.5,-5) -- (sys-put-edge.west);
    % end shipout
    %(interface-finish-graph.east) -- (12.5,-2) -- (12.5,-6) -- (sys-end-shipout.west);
\end{tikzpicture}
\medskip

The above diagram glosses over the fact that the display layer does not
actually call any of the macros of \TeX\ directly, but uses a so called
\emph{binding} (see the class |BindingToPGF|). However, this will not be
important for the present section since you cannot access the binding directly.


\subsubsection{Graph Drawing Scopes}
\label{section-gd-scopes}

When the graph drawing system is active, some pretty basic things inside
\pgfname\ change -- such as the fact that nodes are no longer created in the
normal manner. For this reason, the graph drawing system must be switched on
and of explicitly through opening and closing a so called \emph{graph drawing
scope}. These scopes can, in principle, be nested, namely a graph contains a
node that contains some text that in turn contains a subpicture that contains a
drawing of a graph. However, this is \emph{not} the same as subgraphs nodes and
sublayouts, which are all part of the same graph drawing scope. Normally, graph
drawing scopes are not nested.

Graph drawing scopes are created using the following commands:

\begin{command}{\pgfgdbeginscope}
    This macro starts a \TeX\ scope inside which the following things happen:
    %
    \begin{enumerate}
        \item The display layer method |beginGraphDrawingScope| is called,
            which created a new graph drawing scope inside the graph drawing
            system and places it on top of an internal stack. From now on, all
            subsequent interface calls will refer to this scope until
            |\pgfgdendscope| is called, which will pop the scope once more.
        \item Inside the \TeX\ scope, nodes are not placed immediately. Rather,
            |\pgfpositionnodelater|, see
            Section~\ref{section-shapes-deferred-node-positioning}, is used to
            call |InterfaceToDisplay.createVertex| for all nodes created inside
            the scope. This will cause them to be put inside some internal
            table.
        \item Some additional \meta{code} is executed, which has been set using
            the following command:
            %
            \begin{command}{\pgfgdaddspecificationhook\marg{code}}
                This command adds the \meta{code} to the code that is executed
                whenever a graph drawing scope starts. For instance, the
                \tikzname\ library |graphdrawing| uses this macro to add some
                \meta{code} that will redirect the |edge| and
                |edge from parent| path commands to |\pgfgdedge|.
            \end{command}
        \item |\pgftransformreset| is called.
        \item The following \TeX-if is set to true:
            {
                \let\ifpgfgdgraphdrawingscopeactive=\relax
                \begin{textoken}{\ifpgfgdgraphdrawingscopeactive}
                    Will be true inside a graph drawing scope.
                \end{textoken}
            }
    \end{enumerate}
    %
    The above has a number of consequences for what can happen inside a graph
    drawing scope:
    %
    \begin{itemize}
        \item Since nodes are not actually created before the end of the scope,
            you cannot reference these nodes. Thus, you cannot write
            %
\begin{codeexample}[code only]
\tikz [spring layout] {
  \node (a) {a};
  \node (b) {b};
  \draw (a) -- (b);
}
\end{codeexample}
            %
            The problem is that we cannot connect |(a)| and |(b)| via a
            straight line since these nodes do not exist at that point (they
            are available only deeply inside the Lua).
        \item In order to create edges between nodes inside a graph drawing
            scope, you need to call the |\pgfgdedge| command, described below.
    \end{itemize}

    Additionally, when \tikzname\ is used, the following things also happen:
    %
    \begin{itemize}
        \item If the |graphs| library has been loaded, the default positioning
            mechanisms of this library are switched off, leaving the
            positioning to the graph drawing engine. Also, when an edge is
            created by the |graphs| library, this is signalled to the
            |graphdrawing| library. (To be more precise: The keys |new ->| and
            so on are redefined so that they call |\pgfgdedge| instead of
            creating an edge.
        \item The |edge| path command is modified so that it also calls
            |\pgfgdedge| instead of immediately creating any edges.
        \item The |edge from parent| path command is modified so that is also
            calls |\pgfgdedge|.
        \item The keys |append after command| and |prefix after command| keys
            are modified so that they are executed only via |late options| when
            the node has ``reached its final parking position''.
    \end{itemize}

    Note that inside a graph drawing scope you first have to open a (main)
    layout scope (using the |\pgfgdbeginlayout| command described later on)
    before you can add nodes and edges to the scope.
\end{command}

\begin{command}{\pgfgdendscope}
    This macro is used to end a graph drawing scope. It must be given on the
    same \TeX\ grouping level as the corresponding |\pgfgdbeginscope|. When the
    macro is called, it triggers a lot of new calls:
    %
    \begin{enumerate}
        \item The special treatment of newly created boxes is ended. Nodes are
            once more created normally.
        \item The effects of the \meta{code} that was inserted via the
            specification hook command also ends (provided it had no global
            effects).
        \item We call |InterfaceToDisplay.runGraphDrawingAlgorithm|. This will
            cause the algorithm(s) for the graph to be executed (since a graph
            can have sublayouts, several algorithms may be run). See
            Section~\ref{section-gd-layout-scopes} below.
        \item Next, we call |InterfaceToDisplay.endGraphDrawingScope|. This
            causes all nodes that were intercepted during the graph drawing
            scope to be reinserted into the output stream at the positions that
            were computed for them. Also, for each edge that was requested via
            |\pgfgdedge|, the callback macro is called (see below).
    \end{enumerate}
\end{command}

Inside a graph drawing scope, nodes are automatically passed down to the graph
drawing engine, while for edges a command has to be called explicitly:

\begin{command}{\pgfgdedge\marg{first node}\marg{second node}\marg{edge direction}\marg{edge options}\marg{edge nodes}}
    This command is used to tell the graph drawing engine that there is an edge
    between \meta{first node} and \meta{second node} in your graph. The
    ``kind'' of connection is indicated by \meta{direction}, which may be one
    of the following:
    %
    \begin{itemize}
        \item |->| indicates a directed edge (also known as an arc) from
            \meta{first node} to \meta{second node}.
        \item |--| indicates an undirected edge between \meta{first node} and
            \meta{second node},
        \item |<-| indicates a directed edge from \meta{second node} to
            \meta{first node}, but with the ``additional hint'' that this is a
            ``backward'' edge. A graph drawing algorithm may  or may not take
            this hint into account.
        \item |<->| indicates a bi-directed edge between \meta{first node} and
            \meta{second node}.
        \item |-!-| indicates that the edge from \meta{first node} to
            \meta{second node} is ``missing''.
    \end{itemize}
    %
    Note that in all cases, the syntactic digraph will contain an arc from
    \meta{first node} to \meta{second node}, regardless of the value of
    \meta{direction}. The \meta{direction} is ``just'' a ``semantic
    annotation''.

    The parameters \meta{edge options} and \meta{edge nodes} are a bit more
    tricky. When an edge between two vertices of a graph is created via
    |\pgfgdedge|, nothing is actually done immediately. After all, without
    knowing the final positions of the nodes \meta{first node} and \meta{second
    node}, there is no way of creating the actual drawing commands for the
    edge. Thus, the actual drawing of the edge is done only when the graph
    drawing algorithm is done (namely in the macro |\pgfgdedgecallback|, see
    later).

    Because of this ``delayed'' drawing of edges, options that influence the
    edge must be retained until the moment when the edge is actually drawn.
    Parameters \meta{edge options} and \meta{edge nodes} store such options.

    Let us start with \meta{edge options}. This parameter should be set to a
    list of key--value pairs like
    %
\begin{codeexample}[code only]
/tikz/.cd, color=red, very thick, orient=down
\end{codeexample}
    %
    Some of these options may be of interest to the graph drawing algorithm
    (like the last option) while others will only be important during the
    drawing of edge (like the first option). The options that are important for
    the graph drawing algorithm must be pushed onto the graph drawing system's
    option stack.

    The tricky part is that options that are of interest to the graph drawing
    algorithm must be executed \emph{before} the algorithm starts, but the
    options as a whole are usually only executed during the drawing of the
    edges, which is \emph{after} the algorithm has finished. To overcome this
    problem, the following happens:

    The options in \meta{edge options} are executed ``tentatively'' inside
    |\pgfgdedge|. However, this execution is done in a ``heavily guarded
    sandbox'' where all effects of the options (like changing the color or the
    line width) do not propagate beyond the sandbox. Only the changes of the
    graph drawing edge parameters leave the sandbox. These parameters are then
    passed down to the graph drawing system.

    Later, when the edge is drawn using |\pgfgdedgecallback|, the options
    \meta{edge options} are available once more and then they are executed
    normally.

    Note that when the options in \meta{edge options} are executed, no path is
    preset. Thus, you typically need to start it with, say, |/tikz/.cd|. Also
    note that the sandbox is not perfect and changing global values will have
    an effect outside the sandbox. Indeed, ``putting things in a sandbox'' just
    means that the options are executed inside a \TeX\ scope inside an
    interrupted path inside a \TeX\ box that is thrown away immediately.

    The text in \meta{edge nodes} is some ``auxiliary'' text that is simply
    stored away and later directed to |\pgfgdedgecallback|. This is used for
    instance by \tikzname\ to store its node labels.
\end{command}

\begin{command}{\pgfgdsetedgecallback\marg{macro}}
    This command allows you to change the \meta{macro} that gets called form
    inside the graph drawing system at the end of the creation of a graph, when
    the nodes have been positioned. The \meta{macro} will be called once for
    each edge with the following parameters:
    %
    \begin{quote}
        \meta{macro}\marg{first node}\marg{second node}\marg{direction}\marg{edge options}\marg{edge nodes}\\
        \marg{algorithm-generated options}\marg{bend information}\marg{animations}
    \end{quote}

    The first five parameters are the original values that were passed down to
    the |\pgfgdedge| command.

    The \meta{algorithm-generated options} have been ``computed by the
    algorithm''. For instance, an algorithm might have determined, say, flow
    capacities for edges and it might now wish to communicate this information
    back to the upper layers. These options should be executed with the path
    |/graph drawing|.

    The parameter \meta{bend information} contains algorithmically-computed
    information concerning how the edge should bend. This will be a text like
    |(10pt,20pt)--(30pt,40pt)| in \tikzname-syntax and may include the path
    commands |--|,  |..| (followed by Bézier coordinates), and |--cycle|.

    The parameter \meta{animations} contains algorithmically-generated
    animation commands (calls to |\pgfanimateattribute|. The |whom| will be set
    to |pgf@gd|.

    The default \meta{macro} simply draws a line between the nodes. When the
    |graphdrawing| library of the \tikzname\ layer is loaded, a more fancy
    \meta{macro} is used that takes all of the parameters into account.
\end{command}


\subsection{Layout Scopes}
\label{section-gd-layout-scopes}

As described in Section~\ref{section-gd-sublayouts}, the graph drawing engine
does not always apply only a single algorithm. Rather, several different
algorithm may be applied to different parts of the graph. How this happens,
exactly, is governed by a hierarchy of layouts, which are setup using the
commands |\pgfgdbeginlayout| and |\pgfgdendlayout|.

\begin{command}{\pgfgdbeginlayout}
    This command first starts a new \TeX\ scope and then informs the display
    layer that a new (sub)layout should be started. For each graph there may be
    a hierarchy of layouts, each of which contains a certain number of vertices
    and edges. This hierarchy is created through calls to this macros and the
    corresponding calls of |\pgfgdendlayout|. For each graph drawing scope
    there has to be exactly one main layout that encompasses all nodes and
    edges and also all sublayouts. Thus, after a graph drawing scope has been
    opened, a layout scope also needs to be opened almost immediately.

    For each layout created via this macro, a graph drawing algorithm will be
    run later on the subgraph of all nodes that make up the layout. Which
    algorithm is run for the layout is dictated by which layout key (one of the
    |... layout| keys) is ``in force'' when the macro is called. Thus, using a
    layout key for selecting an algorithm must always be done \emph{before} the
    layout is started. (However, see the discussion of layout keys in the next
    subsection for more details on what really happens.)

    A vertex can be part of several layouts, either because they are nested or
    because they overlap (this happens when a node is later on added to another
    layout by calling |\pgfgdsetlatenodeoption|). This means that it is not
    immediately obvious how conflicts arising from the different ways different
    algorithms ``would like to place nodes'' should be resolved. The method for
    this resolving is detailed in Section~\ref{section-gd-layout-resolve}.
\end{command}

\begin{command}{\pgfgdendlayout}
    This command ends the \TeX\ scope of the current layout. Once closed, no
    nodes or edges can be added to a layout.
\end{command}

\begin{command}{\pgfgdsetlatenodeoption\marg{node name}}
    This command can only be called when the node named \meta{node name} has
    already been created inside the current graph drawing scope. The effect of
    calling this macro will be that all options currently on the graph drawing
    system's option stack will be added to the node's option, possibly
    overwriting the original option settings. Furthermore, the node will become
    part of all layouts currently on the option stack. This means that you can
    use this command to add a node to several layouts that are not included in
    one another.
\end{command}


\subsection{Layout Keys}

\emph{Layout keys} are keys like |tree layout| or |layered layout| that are
used to select a specific graph drawing algorithm. From the graph drawing
system's point of view, these keys ``just'' select an algorithm and when
several layout keys are used in a row, the last one would ``win''; just as when
you say |orient=90| directly followed by |orient=0|, the result is that the
|orient| key is set to |0| because the last key ``wins''.

Unfortunately, if keys like |tree layout| were ``just'' to select an algorithm,
we would still need a key or some special syntax to actually start a
(sub)layout. In early versions of the system this was exactly what people had
to do and this was somewhat awkward. Because of this problem, the behavior of
the layout keys in \pgfname\ (and only there, other display layers need to
implement their own behavior) is now a bit more involved. When you use a key
like |tree layout| (more precisely, any key that was declared as an algorithm
key on the algorithm layer of the graph drawing system) in any scope in
\pgfname, the following happens:
%
\begin{enumerate}
    \item The graph drawing system is told that a specific algorithm has been
        selected (the Reingold--Tilford-algorithm in this case; this
        information was communicated to the graph drawing system during the
        declaration of the algorithm). Being ``told'' about this means that a
        special entry is pushed onto the current options stack of the graph
        drawing system.
    \item An internal ``request'' for a ``scope and a layout'' is made. This
        has several effects:
    \item We first test whether we are already inside a layout scope. If not,
        we use |\pgfgdbeginscope| to open a graph drawing scope. This scope
        will be closed appropriately (see |\pgfgdsetrequestcallback| for
        details).
    \item Next, a layout scope is opened using |\pgfgdbeginlayout|. It will
        also be closed appropriately.
\end{enumerate}

The net effect of the above is that the first use of a layout key in a picture
starts both a graph drawing scope and also a main layout, while subsequent uses
of layout keys inside a picture will only open sublayouts.

\begin{command}{\pgfgdsetrequestcallback\marg{macro}}
    This command sets up \meta{macro} as the macro that is called whenever a
    layout key ``requests'' that a layout and, possibly, a graph drawing scope
    is opened. When \meta{macro} is called, it gets two parameters, the
    \meta{begin code} and the \meta{end code}. In addition to whatever setup
    the \meta{macro} would like to do, it should execute the \meta{begin code}
    at the beginning of a \TeX\ scope (the code will open graph drawing and
    layout scopes) and the \meta{end code} at the end of the same \TeX\ scope.

    The need for this slightly strange macro arises from the fact that in
    \tikzname\ we often write things like |[spring layout,node sep=2cm]|. The
    point is that when the |spring layout| key is executed, we do \emph{not}
    wish to open a layout scope immediately. Rather, this should happen only
    after the option |nodes sep=2cm| has been executed. For this reason,
    \tikzname\ sets up a special \meta{macro} that ``delays'' the execution of
    the \meta{begin code} until the end of the opening of the next scope.

    Because of this, in \tikzname\ layout keys can only be used as an option
    when a \tikzname\ scope is started. Thus, you can pass them to |\tikz|, to
    |{tikzpicture}|, to |\scoped|, to |{scope}|, to |graph|, and to |{graph}|.
    For instance, the |tree layout| option can be used in the following ways:
    %
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}}]
\tikz [tree layout] \graph        {1 -> {b,c}};
\tikz \graph [tree layout]        {2 -> {b,c}};
\tikz \path graph [tree layout]   {3 -> {b,c}};

\begin{tikzpicture}[tree layout]
  \graph                          {4 -> {b,c}};
\end{tikzpicture}

\begin{tikzpicture}
  \scoped [tree layout] \graph    {5 -> {b,c}};

  \begin{scope}[tree layout, xshift=1.5cm]
    \graph                        {6 -> {b,c}};
  \end{scope}
\end{tikzpicture}
\end{codeexample}

    You can \emph{not} use layout keys with a single node or on a path. In
    particular, to typeset a tree given in the |child| syntax somewhere inside
    a |{tikzpicture}|, you must prefix it with the |\scoped| command:
    %
\begin{codeexample}[preamble={\usetikzlibrary{graphdrawing}
\usegdlibrary{trees}}]
\begin{tikzpicture}
  \scoped [tree layout]
    \node {root}
    child { node {left child} }
    child { node {right child} };
\end{tikzpicture}
\end{codeexample}
    %
    Naturally, the above could have been written more succinctly as
    %
\begin{codeexample}[preamble={\usetikzlibrary{graphdrawing}
\usegdlibrary{trees}}]
\tikz [tree layout]
  \node {root}
  child { node {left child} }
  child { node {right child} };
\end{codeexample}
    %
    Or even more succinctly:
    %
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}}]
\tikz \graph [tree layout] { root -- {left child, right child} };
\end{codeexample}
    %
\end{command}


\subsection{Parameters}
\label{section-gd-parameters}

When a graph drawing algorithm starts working, a set of options, called ``graph
drawing parameters'' or just ``parameters'' can influence the way the algorithm
works. For instance, a graph drawing parameter might be the average distance
between vertices which the algorithm should take into account. Another example
might be the fact the certain nodes are special nodes and that a certain edge
should have a large label.

These graph drawing parameters are different from ``usual'' \pgfname\ options:
An algorithmic parameter influences the way the algorithm works, while usual
options influence the way the result looks like. For instance, the fact that a
node is red is not a graph drawing parameter, while the shape of a node might
be an graph drawing parameter.

The possible graph parameters are declared by the algorithmic layer through the
|declare| method; you cannot declare parameters on the \pgfname\ layer since
this would not be compatible across different display systems.

Users use a graph parameter in the same way as a normal key. The difference is
that each time a key representing a graph drawing parameter is used, a special
function of the graph drawing system's interface is called to ``push'' the
parameter onto an internal option stack (and elements are popped from this
stack whenever the \TeX\ scope closes in which the key was used).

The net effect of all of this is that the graph drawing system keeps track of a
stack of option in parallel to \TeX. You cannot, however, access the current
values of graph drawing parameters from \TeX\ since they are tucked away deep
inside the graph drawing system.


\subsection{Events}

\emph{Events} are used to pass information from the parser about the syntactic
structure of a graph to graph drawing algorithms. Consider, for instance, a
graph that is actually a tree in which some node ``misses'' its first child. In
this case, the information that the child is missing is neither part of any
node (because the node is missing, after all) nor is it an option of the whole
graph. However, events are created by the parser the allow an algorithm to
reconstruct the fact that the child is missing. Naturally, graph drawing
algorithms may choose to ignore events and most will.

Most of the creation and handling of events is done automatically. The only
reason you might wish to use the following commands is when you write a
``parser extension'' together with a new graph drawing algorithm. For instance,
you might come up with new options that, when used, trigger events.

\begin{command}{\pgfgdevent\marg{kind}\marg{parameter}}
    Calls |createEvent| of the graph drawing system's interface class. This
    creates a new |Event| object on the Lua layer whose |kind| field is set to
    \meta{kind} and the |parameters| field to \meta{parameter}. You must be
    inside a graph drawing scope to use this command.
\end{command}

\begin{command}{\pgfgdbegineventgroup\marg{parameter}}
    Starts an event group. This just means that an |Event| of kind |begin| is
    created with the given \meta{parameter}.
\end{command}

\begin{command}{\pgfgdendeventgroup}
    Ends an event group. This is done by adding an event of kind |end| without
    any parameters to the event string.
\end{command}

\begin{command}{\pgfgdeventgroup\marg{parameters}}
    Starts an event group just like |\pgfgdbegineventgroup|, but adds a
    corresponding closing |end| event at the end of the current \TeX\ group
    (using |\aftergroup|).
\end{command}


\subsection{Subgraph Nodes}

\begin{command}{\pgfgdsubgraphnode\marg{name}\marg{node options}\marg{node text}}
    A subgraph node is a node that ``surrounds'' the nodes of a subgraph. The
    special property of a subgraph node opposed to a normal node is that it is
    created only after the subgraph has been laid out. However, the difference
    to a collection like |hyper| is that the node is available immediately as a
    normal node in the sense that you can connect edges to it.

    What happens internally is that subgraph nodes get ``registered''
    immediately both on the \pgfname\ level and on the Lua level, but the
    actual node is only created inside the layout pipeline using a callback.
    The actual node creation happens when the innermost layout in which the
    subgraph node is declared has finished.

    When you create a subgraph node using this macro, you also start a
    collection (of an internal kind) that stores the subgraph. All following
    nodes in the current \TeX\ scope will become part of this collection.

    The \meta{name} is the node name by which you can refer to this node in the
    following. The \meta{node options} are normal \pgfname\ options (like |red|
    or |draw| or |circle|) that will influence the appearance when it is
    created later on. The \meta{node text} is the text that will be passed to
    |\pgfnode| upon creation of the node.

    See |InterfaceToDisplay.pushSubgraphVertex| for more details.
\end{command}