summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-usage-pgf.tex
blob: 095e3f771a480f11a96298a937b4b3bbcc62499c (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
% Copyright 2010-2011 by Renée Ahrens
% Copyright 2010-2011 by Olof Frahm
% Copyright 2010-2011 by Jens Kluttig
% Copyright 2010-2011 by Matthias Schulz
% Copyright 2010-2011 by Stephan Schuster
% Copyright 2011 by Jannis Pohlmann
% Copyright 2011 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 graph drawing
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}[]
\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
|graph| 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={->,>=spaced stealth'},
    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 graph
    drawing 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 syntatic 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 ``auxilliary'' 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} 
  \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\'ezier coordintes), and
  |--cycle|. 

  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 goverened 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 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 behaviour of the layout keys in \pgfname\ (and
only there, other display layers need to implement their own
behaviour) 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}[]
\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}[]
\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}[]
\tikz [tree layout]
  \node {root}
  child { node {left child} }
  child { node {right child} };
\end{codeexample}
  Or even more succinctly:
\begin{codeexample}[]
\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 alogrithmic 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 availble 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}