| 1 |
% Copyright 2010-2019 by Renée Ahrens |
| 2 |
% Copyright 2010-2019 by Olof Frahm |
| 3 |
% Copyright 2010-2019 by Jens Kluttig |
| 4 |
% Copyright 2010-2019 by Matthias Schulz |
| 5 |
% Copyright 2010-2019 by Stephan Schuster |
| 6 |
% Copyright 2019 by Jannis Pohlmann |
| 7 |
% Copyright 2019 by Till Tantau |
| 8 |
% |
| 9 |
% This file may be distributed and/or modified |
| 10 |
% |
| 11 |
% 1. under the LaTeX Project Public License and/or |
| 12 |
% 2. under the GNU Free Documentation License. |
| 13 |
% |
| 14 |
% See the file doc/generic/pgf/licenses/LICENSE for more details. |
| 15 |
|
| 16 |
|
| 17 |
\section{Using Graph Drawing in PGF} |
| 18 |
\label{section-gd-pgf} |
| 19 |
|
| 20 |
{\noindent {\emph{by Till Tantau}}} |
| 21 |
|
| 22 |
\begin{purepgflibrary}{graphdrawing} |
| 23 |
This package provides the core support for graph drawing inside \pgfname. |
| 24 |
It does so by providing \pgfname\ macros for controlling the graph drawing |
| 25 |
system, but also implements the binding to the graph drawing system (see |
| 26 |
Section~\ref{section-gd-binding-layer} for details on bindings). |
| 27 |
\end{purepgflibrary} |
| 28 |
|
| 29 |
\ifluatex |
| 30 |
\else |
| 31 |
This section of the manual can only be typeset using Lua\TeX. |
| 32 |
\expandafter\endinput |
| 33 |
\fi |
| 34 |
|
| 35 |
|
| 36 |
\subsection{Overview} |
| 37 |
|
| 38 |
Just like everywhere else in \pgfname, \tikzname\ is ``just a convenient |
| 39 |
syntax'' in the context of graph drawing. The ``hard work'' of binding the |
| 40 |
internal representations of nodes and edges with the graph drawing system |
| 41 |
written in Lua is not done by \tikzname, but rather by a set of macros that are |
| 42 |
part of the basic \pgfname\ layer. |
| 43 |
|
| 44 |
The documentation of the \pgfname\ part of the graph drawing system that is |
| 45 |
presented in the following includes only those macros that other \TeX\ packages |
| 46 |
could conceivably call in order to use the graph drawing system without using |
| 47 |
\tikzname; for instance, for efficiency reasons. (The internal callback |
| 48 |
functions defined in the |graphdrawing| library that are part of the binding |
| 49 |
between \pgfname\ and the graph drawing system are not documented, should not |
| 50 |
be called, and may change in the future.) |
| 51 |
|
| 52 |
|
| 53 |
\subsection{How Graph Drawing in PGF Works} |
| 54 |
|
| 55 |
The core idea behind graph drawing in \pgfname\ is that inside special |
| 56 |
\emph{graph drawing scopes} whenever \pgfname\ creates a node, we intercept |
| 57 |
this node creation and \emph{do not} immediately place the node. Rather, we |
| 58 |
pass it down to Lua part of the graph drawing system via calls to appropriate |
| 59 |
methods of the (Lua) class |InterfaceToDisplay|. The effect will be that the |
| 60 |
nodes are ``tucked away'' in some internal tables. For edges, we introduce a |
| 61 |
special command called |\pgfgdedge| that tells the graph drawing system that |
| 62 |
there is an edge between two tucked-away nodes. Then, at the end of the graph |
| 63 |
drawing scope, a graph drawing algorithm written in Lua starts to work on the |
| 64 |
graph by computing new positions for the nodes. Once the algorithm has |
| 65 |
finished, the graph drawing system starts sending back the nodes and edges to |
| 66 |
\pgfname\ via the methods of the class |BindingToPGF|. These methods reinsert |
| 67 |
some code into the \TeX\ output stream that finally places the nodes at their |
| 68 |
final positions. Note that graph drawing algorithms are perfectly oblivious to |
| 69 |
all of this; indeed, the graph drawing algorithms can even be used |
| 70 |
independently of \TeX. |
| 71 |
|
| 72 |
Let us have a look at a simple example to see what happens when a graph is |
| 73 |
specified: |
| 74 |
% |
| 75 |
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing} |
| 76 |
\usegdlibrary{trees}}] |
| 77 |
\tikz[tree layout] |
| 78 |
\graph {root [as=Hello] -> World[fill=blue!20]}; |
| 79 |
\end{codeexample} |
| 80 |
|
| 81 |
The key |tree layout| internally calls the key |request scope and layout|, |
| 82 |
which in turn calls the macro |\pgfgdbeginscope|, which starts a graph drawing |
| 83 |
scope inside the graph drawing system. Once this macro has been called, until |
| 84 |
the next call of |\pgfgdendscope|, all nodes that are created actually get |
| 85 |
passed down to the graph drawing engine. This is implemented on the lowest |
| 86 |
layer, namely by directly intercepting nodes freshly created using |\pgfnode|. |
| 87 |
In our example, this happens in two places: For the |root| node and for the |
| 88 |
|World| node. The |graphs| library and \tikzname\ internally call the |
| 89 |
|\pgfnode| macro for these two nodes (after a large number of internal syntax |
| 90 |
translations, but the graph drawing system does not care about them). |
| 91 |
|
| 92 |
Note that the node boxes will have been fully created before they are passed |
| 93 |
down to the graph drawing engine -- only their final position is not yet fixed. |
| 94 |
It is not possible to modify the size of nodes inside the graph drawing engine, |
| 95 |
but you can create new nodes in certain situations. |
| 96 |
|
| 97 |
In contrast, the single edge of the graph that is created by the |->| command |
| 98 |
is not fully created before it is passed down to the graph drawing system. This |
| 99 |
would not really make sense since before the final positions of the nodes are |
| 100 |
fixed, we cannot even begin to compute the length of this edge, let alone where |
| 101 |
it should start or end. For this reason, on the upper \tikzname\ layer, the |
| 102 |
normal edge creation that would be caused by |->| via |new ->| is suppressed. |
| 103 |
Instead, the command |\pgfgdedge| is called. Similarly, inside a graph drawing |
| 104 |
scope, \tikzname\ will suppress both the |edge| and the |edge from parent| |
| 105 |
command and cause |\pgfgdedge| to be called instead. |
| 106 |
|
| 107 |
An overview of what happens is illustrated by the following call graph: |
| 108 |
|
| 109 |
\bigskip |
| 110 |
|
| 111 |
\begin{tikzpicture}[ |
| 112 |
class name/.style={draw,minimum size=20pt, fill=blue!20}, |
| 113 |
object node/.style={draw,minimum size=15pt, fill=yellow!20}, |
| 114 |
p/.style={->,>={Stealth[round,sep]}}, |
| 115 |
livespan/.style={very thick}, |
| 116 |
xscale=0.8, |
| 117 |
] |
| 118 |
% class names above |
| 119 |
\node (tikz) at (0,4) [class name] {\tikzname\ layer (\TeX)}; |
| 120 |
\node (tex) at (6,4) [class name] {\pgfname\ layer (\TeX)}; |
| 121 |
\node (interface) at (13,4) [class name] {Display layer (Lua)}; |
| 122 |
% lines from the class names to the bottom of the picture |
| 123 |
\draw[livespan] (tikz) -- (0,-6.5); |
| 124 |
\draw[livespan] (tex) -- (6,-6.5); |
| 125 |
\draw[livespan] (interface) -- (13,-6.5); |
| 126 |
% first command: \graph{ -- generates new graph in lua interface |
| 127 |
\node (tikz-begin-graph) at (0,3) [object node] {|\graph[... layout]{|}; %} |
| 128 |
\node (tex-begin-graph) at (6,3) [object node] {|\pgfgdbeginscope|}; |
| 129 |
\node (interface-new-graph) at (13,3) [object node] {|beginGraphDrawingScope(|...|)|}; |
| 130 |
\draw [p] (tikz-begin-graph.east) -- (tex-begin-graph.west); |
| 131 |
\draw [p] (tex-begin-graph.east) -- (interface-new-graph.west); |
| 132 |
% second command: a -> b -- generates two nodes in lua |
| 133 |
% and one edge |
| 134 |
\node (tikz-node) at (0,2) [object node] {|a -> b;|}; |
| 135 |
\node (tex-node) at (6,2) [object node, double copy shadow] {|\pgfnode|}; |
| 136 |
\draw[p] (tikz-node.east) -- (tex-node.west); |
| 137 |
|
| 138 |
\node (interface-add-node) at (13,2) [object node, double copy shadow] {|createVertex(|...|)|}; |
| 139 |
\draw[p] (tex-node.east) -- (interface-add-node.west); |
| 140 |
|
| 141 |
\node (tex-add-edge) at (6,1) [object node, double copy shadow] {|\pgfgdedge|}; |
| 142 |
\node (interface-add-edge) at (13,1) [object node, double copy shadow] {|createEdge(|...|)|}; |
| 143 |
\draw[p] (tikz-node.east) -- (1.5,2) -- (1.5,1) -- (tex-add-edge.west); |
| 144 |
\draw[p] (tex-add-edge.east) -- (interface-add-edge.west); |
| 145 |
|
| 146 |
% scope ends -- closes graph, layouts it and draws it |
| 147 |
\node (tikz-end) at (0,0) [object node] {|};|}; |
| 148 |
\node (tex-end) at (6,0) [object node] {|\pgfgdendscope|}; |
| 149 |
\node (interface-draw-graph) at (13,0) [object node] {|runGraphDrawingAlgorithm()|}; |
| 150 |
\node (interface-finish-graph) at (13,-2) [object node] {|endGraphDrawingScope()|}; |
| 151 |
|
| 152 |
\node (invoke-algorithm) at (15.5,-1) [object node] {invoke algorithm}; |
| 153 |
\draw[p] (tikz-end.east) -- (tex-end.west); |
| 154 |
\draw[p] (tex-end.east) -- (interface-draw-graph.west); |
| 155 |
\draw[p] (interface-draw-graph.east) -| (invoke-algorithm.20); |
| 156 |
\draw[p] (tex-end.east) -- (9.5,0) -- (9.5,-2) -- (interface-finish-graph.west); |
| 157 |
|
| 158 |
% begin shipout |
| 159 |
\node (tex-begin-shipout) at (6,-3) [object node] {|\pgfgdcallbackbeginshipout|}; |
| 160 |
|
| 161 |
\node (tex-puttexbox) at (6,-4) [object node, double copy shadow] {|\pgfgdcallbackrendernode|}; |
| 162 |
\node (tex-putedge) at (6,-5) [object node, double copy shadow] {|\pgfgddefaultedgecallback|}; |
| 163 |
|
| 164 |
\node (tex-end-shipout) at (6,-6) [object node] {|\pgfgdcallbackendshipout|}; |
| 165 |
|
| 166 |
\draw [p] (interface-finish-graph.-170) |- (tex-begin-shipout.east); |
| 167 |
\draw [p] (interface-finish-graph.-170) |- (tex-puttexbox.east); |
| 168 |
\draw [p] (interface-finish-graph.-170) |- (tex-putedge.east); |
| 169 |
\draw [p] (interface-finish-graph.-170) |- (tex-end-shipout.east); |
| 170 |
%(interface-finish-graph.east) -- (12.5,-2) -- (12.5,-4) -- (sys-puttexbox.west); |
| 171 |
|
| 172 |
% put edge |
| 173 |
%(interface-finish-graph.east) -- (12.5,-2) -- (12.5,-5) -- (sys-put-edge.west); |
| 174 |
% end shipout |
| 175 |
%(interface-finish-graph.east) -- (12.5,-2) -- (12.5,-6) -- (sys-end-shipout.west); |
| 176 |
\end{tikzpicture} |
| 177 |
\medskip |
| 178 |
|
| 179 |
The above diagram glosses over the fact that the display layer does not |
| 180 |
actually call any of the macros of \TeX\ directly, but uses a so called |
| 181 |
\emph{binding} (see the class |BindingToPGF|). However, this will not be |
| 182 |
important for the present section since you cannot access the binding directly. |
| 183 |
|
| 184 |
|
| 185 |
\subsubsection{Graph Drawing Scopes} |
| 186 |
\label{section-gd-scopes} |
| 187 |
|
| 188 |
When the graph drawing system is active, some pretty basic things inside |
| 189 |
\pgfname\ change -- such as the fact that nodes are no longer created in the |
| 190 |
normal manner. For this reason, the graph drawing system must be switched on |
| 191 |
and of explicitly through opening and closing a so called \emph{graph drawing |
| 192 |
scope}. These scopes can, in principle, be nested, namely a graph contains a |
| 193 |
node that contains some text that in turn contains a subpicture that contains a |
| 194 |
drawing of a graph. However, this is \emph{not} the same as subgraphs nodes and |
| 195 |
sublayouts, which are all part of the same graph drawing scope. Normally, graph |
| 196 |
drawing scopes are not nested. |
| 197 |
|
| 198 |
Graph drawing scopes are created using the following commands: |
| 199 |
|
| 200 |
\begin{command}{\pgfgdbeginscope} |
| 201 |
This macro starts a \TeX\ scope inside which the following things happen: |
| 202 |
% |
| 203 |
\begin{enumerate} |
| 204 |
\item The display layer method |beginGraphDrawingScope| is called, |
| 205 |
which created a new graph drawing scope inside the graph drawing |
| 206 |
system and places it on top of an internal stack. From now on, all |
| 207 |
subsequent interface calls will refer to this scope until |
| 208 |
|\pgfgdendscope| is called, which will pop the scope once more. |
| 209 |
\item Inside the \TeX\ scope, nodes are not placed immediately. Rather, |
| 210 |
|\pgfpositionnodelater|, see |
| 211 |
Section~\ref{section-shapes-deferred-node-positioning}, is used to |
| 212 |
call |InterfaceToDisplay.createVertex| for all nodes created inside |
| 213 |
the scope. This will cause them to be put inside some internal |
| 214 |
table. |
| 215 |
\item Some additional \meta{code} is executed, which has been set using |
| 216 |
the following command: |
| 217 |
% |
| 218 |
\begin{command}{\pgfgdaddspecificationhook\marg{code}} |
| 219 |
This command adds the \meta{code} to the code that is executed |
| 220 |
whenever a graph drawing scope starts. For instance, the |
| 221 |
\tikzname\ library |graphdrawing| uses this macro to add some |
| 222 |
\meta{code} that will redirect the |edge| and |
| 223 |
|edge from parent| path commands to |\pgfgdedge|. |
| 224 |
\end{command} |
| 225 |
\item |\pgftransformreset| is called. |
| 226 |
\item The following \TeX-if is set to true: |
| 227 |
{ |
| 228 |
\let\ifpgfgdgraphdrawingscopeactive=\relax |
| 229 |
\begin{textoken}{\ifpgfgdgraphdrawingscopeactive} |
| 230 |
Will be true inside a graph drawing scope. |
| 231 |
\end{textoken} |
| 232 |
} |
| 233 |
\end{enumerate} |
| 234 |
% |
| 235 |
The above has a number of consequences for what can happen inside a graph |
| 236 |
drawing scope: |
| 237 |
% |
| 238 |
\begin{itemize} |
| 239 |
\item Since nodes are not actually created before the end of the scope, |
| 240 |
you cannot reference these nodes. Thus, you cannot write |
| 241 |
% |
| 242 |
\begin{codeexample}[code only] |
| 243 |
\tikz [spring layout] { |
| 244 |
\node (a) {a}; |
| 245 |
\node (b) {b}; |
| 246 |
\draw (a) -- (b); |
| 247 |
} |
| 248 |
\end{codeexample} |
| 249 |
% |
| 250 |
The problem is that we cannot connect |(a)| and |(b)| via a |
| 251 |
straight line since these nodes do not exist at that point (they |
| 252 |
are available only deeply inside the Lua). |
| 253 |
\item In order to create edges between nodes inside a graph drawing |
| 254 |
scope, you need to call the |\pgfgdedge| command, described below. |
| 255 |
\end{itemize} |
| 256 |
|
| 257 |
Additionally, when \tikzname\ is used, the following things also happen: |
| 258 |
% |
| 259 |
\begin{itemize} |
| 260 |
\item If the |graphs| library has been loaded, the default positioning |
| 261 |
mechanisms of this library are switched off, leaving the |
| 262 |
positioning to the graph drawing engine. Also, when an edge is |
| 263 |
created by the |graphs| library, this is signalled to the |
| 264 |
|graphdrawing| library. (To be more precise: The keys |new ->| and |
| 265 |
so on are redefined so that they call |\pgfgdedge| instead of |
| 266 |
creating an edge. |
| 267 |
\item The |edge| path command is modified so that it also calls |
| 268 |
|\pgfgdedge| instead of immediately creating any edges. |
| 269 |
\item The |edge from parent| path command is modified so that is also |
| 270 |
calls |\pgfgdedge|. |
| 271 |
\item The keys |append after command| and |prefix after command| keys |
| 272 |
are modified so that they are executed only via |late options| when |
| 273 |
the node has ``reached its final parking position''. |
| 274 |
\end{itemize} |
| 275 |
|
| 276 |
Note that inside a graph drawing scope you first have to open a (main) |
| 277 |
layout scope (using the |\pgfgdbeginlayout| command described later on) |
| 278 |
before you can add nodes and edges to the scope. |
| 279 |
\end{command} |
| 280 |
|
| 281 |
\begin{command}{\pgfgdendscope} |
| 282 |
This macro is used to end a graph drawing scope. It must be given on the |
| 283 |
same \TeX\ grouping level as the corresponding |\pgfgdbeginscope|. When the |
| 284 |
macro is called, it triggers a lot of new calls: |
| 285 |
% |
| 286 |
\begin{enumerate} |
| 287 |
\item The special treatment of newly created boxes is ended. Nodes are |
| 288 |
once more created normally. |
| 289 |
\item The effects of the \meta{code} that was inserted via the |
| 290 |
specification hook command also ends (provided it had no global |
| 291 |
effects). |
| 292 |
\item We call |InterfaceToDisplay.runGraphDrawingAlgorithm|. This will |
| 293 |
cause the algorithm(s) for the graph to be executed (since a graph |
| 294 |
can have sublayouts, several algorithms may be run). See |
| 295 |
Section~\ref{section-gd-layout-scopes} below. |
| 296 |
\item Next, we call |InterfaceToDisplay.endGraphDrawingScope|. This |
| 297 |
causes all nodes that were intercepted during the graph drawing |
| 298 |
scope to be reinserted into the output stream at the positions that |
| 299 |
were computed for them. Also, for each edge that was requested via |
| 300 |
|\pgfgdedge|, the callback macro is called (see below). |
| 301 |
\end{enumerate} |
| 302 |
\end{command} |
| 303 |
|
| 304 |
Inside a graph drawing scope, nodes are automatically passed down to the graph |
| 305 |
drawing engine, while for edges a command has to be called explicitly: |
| 306 |
|
| 307 |
\begin{command}{\pgfgdedge\marg{first node}\marg{second node}\marg{edge direction}\marg{edge options}\marg{edge nodes}} |
| 308 |
This command is used to tell the graph drawing engine that there is an edge |
| 309 |
between \meta{first node} and \meta{second node} in your graph. The |
| 310 |
``kind'' of connection is indicated by \meta{direction}, which may be one |
| 311 |
of the following: |
| 312 |
% |
| 313 |
\begin{itemize} |
| 314 |
\item |->| indicates a directed edge (also known as an arc) from |
| 315 |
\meta{first node} to \meta{second node}. |
| 316 |
\item |--| indicates an undirected edge between \meta{first node} and |
| 317 |
\meta{second node}, |
| 318 |
\item |<-| indicates a directed edge from \meta{second node} to |
| 319 |
\meta{first node}, but with the ``additional hint'' that this is a |
| 320 |
``backward'' edge. A graph drawing algorithm may or may not take |
| 321 |
this hint into account. |
| 322 |
\item |<->| indicates a bi-directed edge between \meta{first node} and |
| 323 |
\meta{second node}. |
| 324 |
\item |-!-| indicates that the edge from \meta{first node} to |
| 325 |
\meta{second node} is ``missing''. |
| 326 |
\end{itemize} |
| 327 |
% |
| 328 |
Note that in all cases, the syntactic digraph will contain an arc from |
| 329 |
\meta{first node} to \meta{second node}, regardless of the value of |
| 330 |
\meta{direction}. The \meta{direction} is ``just'' a ``semantic |
| 331 |
annotation''. |
| 332 |
|
| 333 |
The parameters \meta{edge options} and \meta{edge nodes} are a bit more |
| 334 |
tricky. When an edge between two vertices of a graph is created via |
| 335 |
|\pgfgdedge|, nothing is actually done immediately. After all, without |
| 336 |
knowing the final positions of the nodes \meta{first node} and \meta{second |
| 337 |
node}, there is no way of creating the actual drawing commands for the |
| 338 |
edge. Thus, the actual drawing of the edge is done only when the graph |
| 339 |
drawing algorithm is done (namely in the macro |\pgfgdedgecallback|, see |
| 340 |
later). |
| 341 |
|
| 342 |
Because of this ``delayed'' drawing of edges, options that influence the |
| 343 |
edge must be retained until the moment when the edge is actually drawn. |
| 344 |
Parameters \meta{edge options} and \meta{edge nodes} store such options. |
| 345 |
|
| 346 |
Let us start with \meta{edge options}. This parameter should be set to a |
| 347 |
list of key--value pairs like |
| 348 |
% |
| 349 |
\begin{codeexample}[code only] |
| 350 |
/tikz/.cd, color=red, very thick, orient=down |
| 351 |
\end{codeexample} |
| 352 |
% |
| 353 |
Some of these options may be of interest to the graph drawing algorithm |
| 354 |
(like the last option) while others will only be important during the |
| 355 |
drawing of edge (like the first option). The options that are important for |
| 356 |
the graph drawing algorithm must be pushed onto the graph drawing system's |
| 357 |
option stack. |
| 358 |
|
| 359 |
The tricky part is that options that are of interest to the graph drawing |
| 360 |
algorithm must be executed \emph{before} the algorithm starts, but the |
| 361 |
options as a whole are usually only executed during the drawing of the |
| 362 |
edges, which is \emph{after} the algorithm has finished. To overcome this |
| 363 |
problem, the following happens: |
| 364 |
|
| 365 |
The options in \meta{edge options} are executed ``tentatively'' inside |
| 366 |
|\pgfgdedge|. However, this execution is done in a ``heavily guarded |
| 367 |
sandbox'' where all effects of the options (like changing the color or the |
| 368 |
line width) do not propagate beyond the sandbox. Only the changes of the |
| 369 |
graph drawing edge parameters leave the sandbox. These parameters are then |
| 370 |
passed down to the graph drawing system. |
| 371 |
|
| 372 |
Later, when the edge is drawn using |\pgfgdedgecallback|, the options |
| 373 |
\meta{edge options} are available once more and then they are executed |
| 374 |
normally. |
| 375 |
|
| 376 |
Note that when the options in \meta{edge options} are executed, no path is |
| 377 |
preset. Thus, you typically need to start it with, say, |/tikz/.cd|. Also |
| 378 |
note that the sandbox is not perfect and changing global values will have |
| 379 |
an effect outside the sandbox. Indeed, ``putting things in a sandbox'' just |
| 380 |
means that the options are executed inside a \TeX\ scope inside an |
| 381 |
interrupted path inside a \TeX\ box that is thrown away immediately. |
| 382 |
|
| 383 |
The text in \meta{edge nodes} is some ``auxiliary'' text that is simply |
| 384 |
stored away and later directed to |\pgfgdedgecallback|. This is used for |
| 385 |
instance by \tikzname\ to store its node labels. |
| 386 |
\end{command} |
| 387 |
|
| 388 |
\begin{command}{\pgfgdsetedgecallback\marg{macro}} |
| 389 |
This command allows you to change the \meta{macro} that gets called form |
| 390 |
inside the graph drawing system at the end of the creation of a graph, when |
| 391 |
the nodes have been positioned. The \meta{macro} will be called once for |
| 392 |
each edge with the following parameters: |
| 393 |
% |
| 394 |
\begin{quote} |
| 395 |
\meta{macro}\marg{first node}\marg{second node}\marg{direction}\marg{edge options}\marg{edge nodes}\\ |
| 396 |
\marg{algorithm-generated options}\marg{bend information}\marg{animations} |
| 397 |
\end{quote} |
| 398 |
|
| 399 |
The first five parameters are the original values that were passed down to |
| 400 |
the |\pgfgdedge| command. |
| 401 |
|
| 402 |
The \meta{algorithm-generated options} have been ``computed by the |
| 403 |
algorithm''. For instance, an algorithm might have determined, say, flow |
| 404 |
capacities for edges and it might now wish to communicate this information |
| 405 |
back to the upper layers. These options should be executed with the path |
| 406 |
|/graph drawing|. |
| 407 |
|
| 408 |
The parameter \meta{bend information} contains algorithmically-computed |
| 409 |
information concerning how the edge should bend. This will be a text like |
| 410 |
|(10pt,20pt)--(30pt,40pt)| in \tikzname-syntax and may include the path |
| 411 |
commands |--|, |..| (followed by Bézier coordinates), and |--cycle|. |
| 412 |
|
| 413 |
The last parameter \meta{animations} contains algorithmically-generated |
| 414 |
animation commands (calls to |\pgfanimateattribute|). The |whom| |
| 415 |
will be set to |pgf@gd|. |
| 416 |
|
| 417 |
The default \meta{macro} simply draws a line between the nodes. When the |
| 418 |
|graphdrawing| library of the \tikzname\ layer is loaded, a more fancy |
| 419 |
\meta{macro} is used that takes all of the parameters into account. |
| 420 |
\end{command} |
| 421 |
|
| 422 |
|
| 423 |
\subsection{Layout Scopes} |
| 424 |
\label{section-gd-layout-scopes} |
| 425 |
|
| 426 |
As described in Section~\ref{section-gd-sublayouts}, the graph drawing engine |
| 427 |
does not always apply only a single algorithm. Rather, several different |
| 428 |
algorithm may be applied to different parts of the graph. How this happens, |
| 429 |
exactly, is governed by a hierarchy of layouts, which are setup using the |
| 430 |
commands |\pgfgdbeginlayout| and |\pgfgdendlayout|. |
| 431 |
|
| 432 |
\begin{command}{\pgfgdbeginlayout} |
| 433 |
This command first starts a new \TeX\ scope and then informs the display |
| 434 |
layer that a new (sub)layout should be started. For each graph there may be |
| 435 |
a hierarchy of layouts, each of which contains a certain number of vertices |
| 436 |
and edges. This hierarchy is created through calls to this macros and the |
| 437 |
corresponding calls of |\pgfgdendlayout|. For each graph drawing scope |
| 438 |
there has to be exactly one main layout that encompasses all nodes and |
| 439 |
edges and also all sublayouts. Thus, after a graph drawing scope has been |
| 440 |
opened, a layout scope also needs to be opened almost immediately. |
| 441 |
|
| 442 |
For each layout created via this macro, a graph drawing algorithm will be |
| 443 |
run later on the subgraph of all nodes that make up the layout. Which |
| 444 |
algorithm is run for the layout is dictated by which layout key (one of the |
| 445 |
|... layout| keys) is ``in force'' when the macro is called. Thus, using a |
| 446 |
layout key for selecting an algorithm must always be done \emph{before} the |
| 447 |
layout is started. (However, see the discussion of layout keys in the next |
| 448 |
subsection for more details on what really happens.) |
| 449 |
|
| 450 |
A vertex can be part of several layouts, either because they are nested or |
| 451 |
because they overlap (this happens when a node is later on added to another |
| 452 |
layout by calling |\pgfgdsetlatenodeoption|). This means that it is not |
| 453 |
immediately obvious how conflicts arising from the different ways different |
| 454 |
algorithms ``would like to place nodes'' should be resolved. The method for |
| 455 |
this resolving is detailed in Section~\ref{section-gd-layout-resolve}. |
| 456 |
\end{command} |
| 457 |
|
| 458 |
\begin{command}{\pgfgdendlayout} |
| 459 |
This command ends the \TeX\ scope of the current layout. Once closed, no |
| 460 |
nodes or edges can be added to a layout. |
| 461 |
\end{command} |
| 462 |
|
| 463 |
\begin{command}{\pgfgdsetlatenodeoption\marg{node name}} |
| 464 |
This command can only be called when the node named \meta{node name} has |
| 465 |
already been created inside the current graph drawing scope. The effect of |
| 466 |
calling this macro will be that all options currently on the graph drawing |
| 467 |
system's option stack will be added to the node's option, possibly |
| 468 |
overwriting the original option settings. Furthermore, the node will become |
| 469 |
part of all layouts currently on the option stack. This means that you can |
| 470 |
use this command to add a node to several layouts that are not included in |
| 471 |
one another. |
| 472 |
\end{command} |
| 473 |
|
| 474 |
|
| 475 |
\subsection{Layout Keys} |
| 476 |
|
| 477 |
\emph{Layout keys} are keys like |tree layout| or |layered layout| that are |
| 478 |
used to select a specific graph drawing algorithm. From the graph drawing |
| 479 |
system's point of view, these keys ``just'' select an algorithm and when |
| 480 |
several layout keys are used in a row, the last one would ``win''; just as when |
| 481 |
you say |orient=90| directly followed by |orient=0|, the result is that the |
| 482 |
|orient| key is set to |0| because the last key ``wins''. |
| 483 |
|
| 484 |
Unfortunately, if keys like |tree layout| were ``just'' to select an algorithm, |
| 485 |
we would still need a key or some special syntax to actually start a |
| 486 |
(sub)layout. In early versions of the system this was exactly what people had |
| 487 |
to do and this was somewhat awkward. Because of this problem, the behavior of |
| 488 |
the layout keys in \pgfname\ (and only there, other display layers need to |
| 489 |
implement their own behavior) is now a bit more involved. When you use a key |
| 490 |
like |tree layout| (more precisely, any key that was declared as an algorithm |
| 491 |
key on the algorithm layer of the graph drawing system) in any scope in |
| 492 |
\pgfname, the following happens: |
| 493 |
% |
| 494 |
\begin{enumerate} |
| 495 |
\item The graph drawing system is told that a specific algorithm has been |
| 496 |
selected (the Reingold--Tilford-algorithm in this case; this |
| 497 |
information was communicated to the graph drawing system during the |
| 498 |
declaration of the algorithm). Being ``told'' about this means that a |
| 499 |
special entry is pushed onto the current options stack of the graph |
| 500 |
drawing system. |
| 501 |
\item An internal ``request'' for a ``scope and a layout'' is made. This |
| 502 |
has several effects: |
| 503 |
\item We first test whether we are already inside a layout scope. If not, |
| 504 |
we use |\pgfgdbeginscope| to open a graph drawing scope. This scope |
| 505 |
will be closed appropriately (see |\pgfgdsetrequestcallback| for |
| 506 |
details). |
| 507 |
\item Next, a layout scope is opened using |\pgfgdbeginlayout|. It will |
| 508 |
also be closed appropriately. |
| 509 |
\end{enumerate} |
| 510 |
|
| 511 |
The net effect of the above is that the first use of a layout key in a picture |
| 512 |
starts both a graph drawing scope and also a main layout, while subsequent uses |
| 513 |
of layout keys inside a picture will only open sublayouts. |
| 514 |
|
| 515 |
\begin{command}{\pgfgdsetrequestcallback\marg{macro}} |
| 516 |
This command sets up \meta{macro} as the macro that is called whenever a |
| 517 |
layout key ``requests'' that a layout and, possibly, a graph drawing scope |
| 518 |
is opened. When \meta{macro} is called, it gets two parameters, the |
| 519 |
\meta{begin code} and the \meta{end code}. In addition to whatever setup |
| 520 |
the \meta{macro} would like to do, it should execute the \meta{begin code} |
| 521 |
at the beginning of a \TeX\ scope (the code will open graph drawing and |
| 522 |
layout scopes) and the \meta{end code} at the end of the same \TeX\ scope. |
| 523 |
|
| 524 |
The need for this slightly strange macro arises from the fact that in |
| 525 |
\tikzname\ we often write things like |[spring layout,node sep=2cm]|. The |
| 526 |
point is that when the |spring layout| key is executed, we do \emph{not} |
| 527 |
wish to open a layout scope immediately. Rather, this should happen only |
| 528 |
after the option |nodes sep=2cm| has been executed. For this reason, |
| 529 |
\tikzname\ sets up a special \meta{macro} that ``delays'' the execution of |
| 530 |
the \meta{begin code} until the end of the opening of the next scope. |
| 531 |
|
| 532 |
Because of this, in \tikzname\ layout keys can only be used as an option |
| 533 |
when a \tikzname\ scope is started. Thus, you can pass them to |\tikz|, to |
| 534 |
|{tikzpicture}|, to |\scoped|, to |{scope}|, to |graph|, and to |{graph}|. |
| 535 |
For instance, the |tree layout| option can be used in the following ways: |
| 536 |
% |
| 537 |
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing} |
| 538 |
\usegdlibrary{trees}}] |
| 539 |
\tikz [tree layout] \graph {1 -> {b,c}}; |
| 540 |
\tikz \graph [tree layout] {2 -> {b,c}}; |
| 541 |
\tikz \path graph [tree layout] {3 -> {b,c}}; |
| 542 |
|
| 543 |
\begin{tikzpicture}[tree layout] |
| 544 |
\graph {4 -> {b,c}}; |
| 545 |
\end{tikzpicture} |
| 546 |
|
| 547 |
\begin{tikzpicture} |
| 548 |
\scoped [tree layout] \graph {5 -> {b,c}}; |
| 549 |
|
| 550 |
\begin{scope}[tree layout, xshift=1.5cm] |
| 551 |
\graph {6 -> {b,c}}; |
| 552 |
\end{scope} |
| 553 |
\end{tikzpicture} |
| 554 |
\end{codeexample} |
| 555 |
|
| 556 |
You can \emph{not} use layout keys with a single node or on a path. In |
| 557 |
particular, to typeset a tree given in the |child| syntax somewhere inside |
| 558 |
a |{tikzpicture}|, you must prefix it with the |\scoped| command: |
| 559 |
% |
| 560 |
\begin{codeexample}[preamble={\usetikzlibrary{graphdrawing} |
| 561 |
\usegdlibrary{trees}}] |
| 562 |
\begin{tikzpicture} |
| 563 |
\scoped [tree layout] |
| 564 |
\node {root} |
| 565 |
child { node {left child} } |
| 566 |
child { node {right child} }; |
| 567 |
\end{tikzpicture} |
| 568 |
\end{codeexample} |
| 569 |
% |
| 570 |
Naturally, the above could have been written more succinctly as |
| 571 |
% |
| 572 |
\begin{codeexample}[preamble={\usetikzlibrary{graphdrawing} |
| 573 |
\usegdlibrary{trees}}] |
| 574 |
\tikz [tree layout] |
| 575 |
\node {root} |
| 576 |
child { node {left child} } |
| 577 |
child { node {right child} }; |
| 578 |
\end{codeexample} |
| 579 |
% |
| 580 |
Or even more succinctly: |
| 581 |
% |
| 582 |
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing} |
| 583 |
\usegdlibrary{trees}}] |
| 584 |
\tikz \graph [tree layout] { root -- {left child, right child} }; |
| 585 |
\end{codeexample} |
| 586 |
% |
| 587 |
\end{command} |
| 588 |
|
| 589 |
|
| 590 |
\subsection{Parameters} |
| 591 |
\label{section-gd-parameters} |
| 592 |
|
| 593 |
When a graph drawing algorithm starts working, a set of options, called ``graph |
| 594 |
drawing parameters'' or just ``parameters'' can influence the way the algorithm |
| 595 |
works. For instance, a graph drawing parameter might be the average distance |
| 596 |
between vertices which the algorithm should take into account. Another example |
| 597 |
might be the fact the certain nodes are special nodes and that a certain edge |
| 598 |
should have a large label. |
| 599 |
|
| 600 |
These graph drawing parameters are different from ``usual'' \pgfname\ options: |
| 601 |
An algorithmic parameter influences the way the algorithm works, while usual |
| 602 |
options influence the way the result looks like. For instance, the fact that a |
| 603 |
node is red is not a graph drawing parameter, while the shape of a node might |
| 604 |
be an graph drawing parameter. |
| 605 |
|
| 606 |
The possible graph parameters are declared by the algorithmic layer through the |
| 607 |
|declare| method; you cannot declare parameters on the \pgfname\ layer since |
| 608 |
this would not be compatible across different display systems. |
| 609 |
|
| 610 |
Users use a graph parameter in the same way as a normal key. The difference is |
| 611 |
that each time a key representing a graph drawing parameter is used, a special |
| 612 |
function of the graph drawing system's interface is called to ``push'' the |
| 613 |
parameter onto an internal option stack (and elements are popped from this |
| 614 |
stack whenever the \TeX\ scope closes in which the key was used). |
| 615 |
|
| 616 |
The net effect of all of this is that the graph drawing system keeps track of a |
| 617 |
stack of option in parallel to \TeX. You cannot, however, access the current |
| 618 |
values of graph drawing parameters from \TeX\ since they are tucked away deep |
| 619 |
inside the graph drawing system. |
| 620 |
|
| 621 |
|
| 622 |
\subsection{Events} |
| 623 |
|
| 624 |
\emph{Events} are used to pass information from the parser about the syntactic |
| 625 |
structure of a graph to graph drawing algorithms. Consider, for instance, a |
| 626 |
graph that is actually a tree in which some node ``misses'' its first child. In |
| 627 |
this case, the information that the child is missing is neither part of any |
| 628 |
node (because the node is missing, after all) nor is it an option of the whole |
| 629 |
graph. However, events are created by the parser to allow an algorithm to |
| 630 |
reconstruct the fact that the child is missing. Naturally, graph drawing |
| 631 |
algorithms may choose to ignore events and most will. |
| 632 |
|
| 633 |
Most of the creation and handling of events is done automatically. The only |
| 634 |
reason you might wish to use the following commands is when you write a |
| 635 |
``parser extension'' together with a new graph drawing algorithm. For instance, |
| 636 |
you might come up with new options that, when used, trigger events. |
| 637 |
|
| 638 |
\begin{command}{\pgfgdevent\marg{kind}\marg{parameter}} |
| 639 |
Calls |createEvent| of the graph drawing system's interface class. This |
| 640 |
creates a new |Event| object on the Lua layer whose |kind| field is set to |
| 641 |
\meta{kind} and the |parameters| field to \meta{parameter}. You must be |
| 642 |
inside a graph drawing scope to use this command. |
| 643 |
\end{command} |
| 644 |
|
| 645 |
\begin{command}{\pgfgdbegineventgroup\marg{parameter}} |
| 646 |
Starts an event group. This just means that an |Event| of kind |begin| is |
| 647 |
created with the given \meta{parameter}. |
| 648 |
\end{command} |
| 649 |
|
| 650 |
\begin{command}{\pgfgdendeventgroup} |
| 651 |
Ends an event group. This is done by adding an event of kind |end| without |
| 652 |
any parameters to the event string. |
| 653 |
\end{command} |
| 654 |
|
| 655 |
\begin{command}{\pgfgdeventgroup\marg{parameters}} |
| 656 |
Starts an event group just like |\pgfgdbegineventgroup|, but adds a |
| 657 |
corresponding closing |end| event at the end of the current \TeX\ group |
| 658 |
(using |\aftergroup|). |
| 659 |
\end{command} |
| 660 |
|
| 661 |
|
| 662 |
\subsection{Subgraph Nodes} |
| 663 |
|
| 664 |
\begin{command}{\pgfgdsubgraphnode\marg{name}\marg{node options}\marg{node text}} |
| 665 |
A subgraph node is a node that ``surrounds'' the nodes of a subgraph. The |
| 666 |
special property of a subgraph node opposed to a normal node is that it is |
| 667 |
created only after the subgraph has been laid out. However, the difference |
| 668 |
to a collection like |hyper| is that the node is available immediately as a |
| 669 |
normal node in the sense that you can connect edges to it. |
| 670 |
|
| 671 |
What happens internally is that subgraph nodes get ``registered'' |
| 672 |
immediately both on the \pgfname\ level and on the Lua level, but the |
| 673 |
actual node is only created inside the layout pipeline using a callback. |
| 674 |
The actual node creation happens when the innermost layout in which the |
| 675 |
subgraph node is declared has finished. |
| 676 |
|
| 677 |
When you create a subgraph node using this macro, you also start a |
| 678 |
collection (of an internal kind) that stores the subgraph. All following |
| 679 |
nodes in the current \TeX\ scope will become part of this collection. |
| 680 |
|
| 681 |
The \meta{name} is the node name by which you can refer to this node in the |
| 682 |
following. The \meta{node options} are normal \pgfname\ options (like |red| |
| 683 |
or |draw| or |circle|) that will influence the appearance when it is |
| 684 |
created later on. The \meta{node text} is the text that will be passed to |
| 685 |
|\pgfnode| upon creation of the node. |
| 686 |
|
| 687 |
See |InterfaceToDisplay.pushSubgraphVertex| for more details. |
| 688 |
\end{command} |