Debian Codegraph @

texmf-dist/doc/generic/pgf/pgfmanual-en-gd-usage-tikz.tex

raw
1 % Copyright 2019 by Till Tantau
2 %
3 % This file may be distributed and/or modified
4 %
5 % 1. under the LaTeX Project Public License and/or
6 % 2. under the GNU Free Documentation License.
7 %
8 % See the file doc/generic/pgf/licenses/LICENSE for more details.
9
10
11 \section{Using Graph Drawing in \tikzname}
12
13 {\noindent {\emph{by Till Tantau}}}
14
15 \begin{tikzlibrary}{graphdrawing}
16 This package provides capabilities for automatic graph drawing. It requires
17 that the document is typeset using Lua\TeX. This package should work with
18 Lua\TeX\ 0.54 or higher.
19 \end{tikzlibrary}
20
21 \ifluatex
22 \else
23 This section of the manual can only be typeset using Lua\TeX.
24 \expandafter\endinput
25 \fi
26
27
28 \subsection{Choosing a Layout and a Library}
29
30 The graph drawing engine is initialized when you load the library
31 |graphdrawing|. This library provides the basic framework for graph drawing,
32 including all options and keys described in the present section. However, this
33 library does \emph{not} load any actual algorithms for drawing graphs. For
34 this, you need to use the following command, which is defined by the
35 |graphdrawing| library:
36
37 \begin{command}{\usegdlibrary\marg{list of libraries}}
38 This command is used to load the special graph drawing libraries (the |gd|
39 in the name of the command stands for ``graph drawing''). The \meta{list of
40 libraries} is a comma-separated list of library written in the Lua
41 programming language (which is why a special command is needed).
42
43 In detail, this command does the following. For each \meta{name} in the
44 \meta{list of libraries} we do:
45 %
46 \begin{enumerate}
47 \item Check whether Lua\TeX\ can call |require| on the library file
48 |pgf.gd.|\meta{name}|.library|. Lua\TeX's usual file search
49 mechanism will search the texmf-trees in the usual manner and the
50 dots in the file name get converted into directory slashes.
51 \item If the above failed, try to |require| the string
52 |pgf.gd.|\meta{name}.
53 \item If this fails, try to |require| the string \meta{name}|.library|.
54 \item If this fails, try to |require| the string \meta{name}. If this
55 fails, print an error message.
56 \end{enumerate}
57 %
58 The net effect of the above is the following: Authors of graph drawing
59 algorithms can bundle together multiple algorithms in a library by creating
60 a |...xyz/library.lua| file that internally just calls |require| for all
61 files containing declarations. On the other hand, if a graph drawing
62 algorithm completely fits inside a single file, it can also be read
63 directly using |\usegdlibrary|.
64 %
65 \begin{codeexample}[code only]
66 \usetikzlibrary{graphdrawing}
67 \usegdlibrary{trees,force}
68 \end{codeexample}
69
70 The different graph drawing libraries are documented in the following
71 Sections~\ref{section-first-graphdrawing-library-in-manual} to
72 \ref{section-last-graphdrawing-library-in-manual}.
73 \end{command}
74
75 Note that in addition to the graph \emph{drawing} libraries, you may also wish
76 to load the normal \tikzname\ library |graphs|. It provides the powerful
77 |graph| path command with its easy-to-use syntax for specifying graphs, but you
78 can use the graph drawing engine independently of the |graphs| library, for
79 instance in conjunction with the |child| or the |edge| syntax. Here is a
80 typical setup:
81 %
82 \begin{codeexample}[code only]
83 \usetikzlibrary{graphs, graphdrawing}
84 \usegdlibrary{trees, layered}
85 \end{codeexample}
86
87 Having set things up, you must then specify for which scopes the graph drawing
88 engine should apply a layout algorithm to the nodes in the scope. Typically,
89 you just add an option ending with |... layout| to the |graph| path operation
90 and then let the graph drawing do its magic:
91 %
92 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
93 \usegdlibrary{layered}}]
94 \tikz [rounded corners]
95 \graph [layered layout, sibling distance=8mm, level distance=8mm]
96 {
97 a -> {
98 b,
99 c -> { d, e }
100 } ->
101 f ->
102 a
103 };
104 \end{codeexample}
105
106 Whenever you use such an option, you can:
107 %
108 \begin{itemize}
109 \item Create nodes in the usual way. The nodes will be created completely,
110 but then tucked away in an internal table. This means that all of
111 \tikzname's options for nodes can be applied. You can also name a node
112 and reference it later.
113 \item Create edges using either the syntax of the |graph| command (using
114 |--|, |<-|, |->|, or |<->|), or using the |edge| command, or using the
115 |child| command. These edges will, however, not be created immediately.
116 Instead, the basic layer's command |\pgfgdedge| will be called, which
117 stores ``all the information concerning the edge''. The actual drawing
118 of the edge will only happen after all nodes have been positioned.
119 \item Most of the keys that can be passed to an edge will work as expected.
120 In particular, you can add labels to edges using the usual |node|
121 syntax for edges.
122 \item The |label| and |pin| options can be used in the usual manner with
123 nodes inside a graph drawing scope. Only, the labels and nodes will
124 play no role in the positioning of the nodes and they are added when
125 the nodes are finally positioned.
126 \item Similarly, nodes that are placed ``on an edge'' using the implicit
127 positioning syntax can be used in the usual manner.
128 \end{itemize}
129 %
130 Here are some things that will \emph{not} work:
131 %
132 \begin{itemize}
133 \item Only edges created using the graph syntax, the |edge| command, or the
134 |child| command will correctly pass their connection information to the
135 basic layer. When you write |\draw (a)--(b);| inside a graph drawing
136 scope, where |a| and |b| are nodes that have been created inside the
137 scope, you will get an error message / things will look wrong. The
138 reason is that the usual |--| is not ``caught'' by the graph drawing
139 engine and, thus, tries to immediately connect two nodes that do not
140 yet exist (except inside some internal table).
141 \item The options of edges are executed twice: Once when the edge is
142 ``examined'' by the |\pgfgdedge| command (using some magic to shield
143 against the side effects) and then once more when the edge is actually
144 created. Fortunately, in almost all cases, this will not be a problem;
145 but if you do very evil magic inside your edge options, you must roll a
146 D100 to see what strange things will happen. (Do no evil, by the way.)
147 \end{itemize}
148
149 If you are really interested in the ``fine print'' of what happens, please see
150 Section~\ref{section-gd-pgf}.
151
152
153 \subsection{Graph Drawing Parameters}
154
155 Graph drawing algorithms can typically be configured in some way. For instance,
156 for a graph drawing algorithm that visualizes its nodes as a tree, it will
157 typically be useful when the user can change the so-called \emph{level
158 distance} and the \emph{sibling distance}. For other algorithms, like
159 force-based algorithms, a large number of parameters influence the way the
160 algorithms work. Options that influence graph drawing algorithms will be called
161 \emph{(graph drawing) parameters} in the following. From the user's point of
162 view, these parameters look like normal \tikzname\ keys and you set them in the
163 usual way. Internally, they are treated a bit differently from normal keys
164 since their ``effect'' becomes apparent only later on, namely during the run of
165 the graph drawing algorithm.
166
167 A graph drawing algorithm may or may not take different graph parameters into
168 account. After all, these options may even outright contradict each other, so
169 an algorithm can only try to ``do its best''. While many graph parameters are
170 very specific to a single algorithm, a number of graph parameters will be
171 important for many algorithms and they are documented in the course of the
172 present section. Here is an example of an option the ``always works'':
173 %
174 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
175 \usegdlibrary{force}}]
176 \tikz \graph [spring layout, vertical=1 to 2] { 1--2--3--1 };
177 \end{codeexample}
178
179 \includeluadocumentationof{pgf.gd.control.Distances}
180 \includeluadocumentationof{pgf.gd.control.Anchoring}
181 \includeluadocumentationof{pgf.gd.control.Orientation}
182
183 \includeluadocumentationof{pgf.gd.control.FineTune}
184
185 \includeluadocumentationof{pgf.gd.control.Components}
186 \includeluadocumentationof{pgf.gd.control.ComponentOrder}
187 \includeluadocumentationof{pgf.gd.control.ComponentDirection}
188 \includeluadocumentationof{pgf.gd.control.ComponentAlign}
189 \includeluadocumentationof{pgf.gd.control.ComponentDistance}
190
191 \includeluadocumentationof{pgf.gd.control.NodeAnchors}
192
193 \includeluadocumentationof{pgf.gd.model.Hyperedge}
194
195
196 \subsection{Using Several Different Layouts to Draw a Single Graph}
197 \label{section-gd-sublayouts}
198
199 Inside each graph drawing scope, a main algorithm is used to perform the graph
200 drawing. However, parts of the graph may be drawn using different algorithms:
201 For instance, a graph might consist of several, say, cliques that are arranged
202 in a tree-like fashion. In this case, it might be useful to layout each clique
203 using a circular layout, but then lay out all laid out cliques using a tree
204 drawing algorithm.
205
206 In order to lay out a graph using multiple algorithms, we need two things:
207 First, we must be able to \emph{specify} which algorithms should be used where
208 and, second, we must be able to \emph{resolve} conflicts that may result from
209 different algorithms ``having different ideas'' concerning where nodes should
210 be placed.
211
212
213 \subsubsection{Sublayouts}
214
215 Specifying different layouts for a graph is easy: Inside a graph drawing scope,
216 simply open scopes, in which you use an option like |tree layout| for the nodes
217 mentioned in this scope. Inside these scopes, you can open even subscopes for
218 sublayouts, and so on. Furthermore, the |graphs| library has special support
219 for sublayouts.
220
221 Let us start with the ``plain'' syntax for opening sublayouts: You pass a key
222 for creating layouts to a |scope|:
223 %
224 \begin{codeexample}[preamble={\usetikzlibrary{graphdrawing}
225 \usegdlibrary{force,trees}}]
226 \tikz [spring layout] {
227 \begin{scope}[tree layout]
228 \node (a) {a};
229 \node (b) {b};
230 \node (c) {c};
231 \draw (a) edge (b) edge (c);
232 \end{scope}
233
234 \begin{scope}[tree layout]
235 \node (1) {1};
236 \node (2) {2};
237 \draw (1) edge (2);
238 \end{scope}
239
240 \draw (a) edge (1);
241 }
242 \end{codeexample}
243
244 Let us see, what is going on here. The main layout (|spring layout|) contains
245 two sublayouts (the two |tree layouts|). Both of them are laid out
246 independently (more on the details in a moment). Then, from the main layout's
247 point of view, the sublayouts behave like ``large nodes'' and, thus, the edge
248 between |a| and |1| is actually the only edge that is used by the
249 |spring layout| -- resulting in a simple layout consisting of one big node at
250 the top and a big node at the bottom.
251
252 The |graphs| library has a special support for sublayouts: The syntax is as
253 follows: wherever a normal node would go, you can write
254 %
255 \begin{quote}
256 |//| \opt{\oarg{layout options}} |{|\meta{sublayout}|}|
257 \end{quote}
258
259 Following the double slash, you may provide \meta{layout options} in square
260 brackets. However, you \emph{must} provide a sublayout in braces. The contents
261 of \meta{sublayout} will be parsed using the usual |graph| syntax, but will
262 form a sublayout.
263 %
264 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
265 \usegdlibrary{force,trees}}]
266 \tikz \graph [spring layout] {
267 // [tree layout] { a -- {b, c} };
268 // [tree layout] { 1 -- 2 };
269 a -- 1;
270 };
271 \end{codeexample}
272
273 In the above example, there is no node before the double slash, which means
274 that the two sublayouts will be part of the main graph, but will not be
275 indicated otherwise.
276 %
277 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
278 \usegdlibrary{circular,trees}}]
279 \tikz \graph [simple necklace layout] {
280 // [simple necklace layout] { a -> b -> c -> d -> e -> f -> a };
281
282 // [tree layout] { % first tentacle
283 a -> {1, 2};
284 };
285
286 // [tree layout] {% second tentacle
287 d -> {3, 4 -> {5, 6}}
288 };
289 };
290 \end{codeexample}
291
292 In the above example, the first sublayout is the one for the nodes with letter
293 names. These nodes are arranged using a simple necklace layout as the sublayout
294 inherits this option from the main layout. The two small trees (|a -> {1, 2}|
295 and the tree starting at the |d| node) are also sublayouts, triggered by the
296 |tree layout| option. They are also arranged. Then, all of the layouts are
297 merged (as described later). The result is actually a single node, so the main
298 layout does nothing here.
299
300 Compare the above to the following code:
301 %
302 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
303 \usegdlibrary{circular,trees}}]
304 \tikz \graph [simple necklace layout] {
305 // [tree layout] { % first ``giant node''
306 a -> {1, 2};
307 };
308
309 a -> b -> c -> d;
310
311 // [tree layout] {% second ``giant node''
312 d -> {3, 4 -> {5, 6}}
313 },
314
315 d -> e -> f -> a;
316 };
317 \end{codeexample}
318
319 Here, only the two trees are laid out first. They are then contracted into
320 ``giant nodes'' and these are then part of the set of nodes that are arranged
321 by the |simple necklace layout|. For details of how this contracting works, see
322 below.
323
324
325 \subsubsection{Subgraph Nodes}
326
327 A \emph{subgraph node} is a special kind of node that ``surrounds'' the
328 vertices of a subgraph. The special property of a subgraph node opposed to a
329 normal node is that it is created only after the subgraph has been laid out.
330 However, the difference to a collection like |hyper| is that the node is
331 available immediately as a normal node in the sense that you can connect edges
332 to it.
333
334 The syntax used to declare a subgraph node in a |graph| specification is as
335 follows:
336 %
337 \begin{quote}
338 \opt{|"|}\meta{node name}\opt{|"|}\opt{|/|\opt{|"|}\meta{text}\opt{|"|}}
339 \opt{\oarg{node options}} |//| \opt{\oarg{layout options}} |{|\meta{subgraph}|}|
340 \end{quote}
341
342 The idea ist that a subgraph node is declared like a normal node specification,
343 but is followed by a double slash and a subgraph:
344 %
345 \begin{codeexample}[
346 width=5cm,
347 preamble={\usetikzlibrary{graphs,graphdrawing}
348 \usegdlibrary{circular,trees}},
349 ]
350 \tikz \graph [simple necklace layout] {
351 tree 1[draw, circle] // [tree layout] { a -> {1, 2}; }
352 -> b
353 -> c
354 -> tree 2[draw] // [tree layout] { d -> {3, 4 -> {5, 6} } }
355 -> e
356 -> f
357 -> tree 1;
358 };
359 \end{codeexample}
360
361 Note how the two subgraph nodes |tree 1| and |tree 2| surround the two smaller
362 trees. In the example, both had trees as contents and these trees were rendered
363 using a sublayout. However, a subgraph layout does not need to have its own
364 layout: If you do \emph{not} provide a layout name after the double slash, the
365 subgraph node will simply surround all nodes that were placed by the main
366 layout wherever they were placed:
367 %
368 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
369 \usegdlibrary{trees}}]
370 \tikz [subgraph text bottom=text centered,
371 subgraph nodes={font=\itshape}]
372 \graph [tree layout] {
373 a -> { b -> {c, d}, e -> {f, g -> h} };
374
375 left [draw] // { b, c, d };
376 right [draw] // { e, f, g, h};
377
378 left <-> right;
379 };
380 \end{codeexample}
381
382 Every time a subgraph node is created, the following style is execute:
383
384 \begin{key}{/tikz/every subgraph node}
385 Set a subgraph node style.
386 \end{key}
387
388 \begin{key}{/tikz/subgraph nodes=\meta{style}}
389 Sets the |every subgraph node| style to \meta{style}.
390 %
391 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
392 \usegdlibrary{trees}}]
393 \tikz [subgraph text bottom=text centered,
394 subgraph nodes=red]
395 \graph [tree layout] {
396 a -> { b -> {c, d}, e -> {f, g -> h} };
397
398 left [draw] // { b, c, d };
399 right [draw] // { e, f, g, h};
400
401 left <-> right;
402 };
403 \end{codeexample}
404 %
405 \end{key}
406
407 \begin{key}{/tikz/subgraph text none}
408 When this option is used, the text of a subgraph node is not shown. Adding
409 a slash after the node name achieves roughly the same effect, but this
410 option is useful in situations when subgraph nodes generally should not
411 have any text inside them.
412 %
413 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
414 \usegdlibrary{trees}}]
415 \tikz [subgraph text none]
416 \graph [tree layout] {
417 a -> { b -> {c, d}, e -> {f, g -> h} };
418
419 left [draw] // { b, c, d };
420 right [draw] // { e, f, g, h};
421
422 left <-> right;
423 };
424 \end{codeexample}
425 %
426 \end{key}
427
428 \begin{key}{/tikz/subgraph text top=\meta{text alignment options} (default text ragged right)}
429 Specifies that the text of a subgraph node should be placed at the top of
430 the subgraph node: Still inside the node, but above all nodes inside the
431 subgraph node.
432 %
433 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
434 \usegdlibrary{trees}}]
435 \tikz [subgraph text top=text ragged left]
436 \graph [tree layout] {
437 a -> { b -> {c, d}, e -> {f, g -> h} };
438
439 left [draw] // { b, c, d };
440 right [draw] // { e, f, g, h};
441
442 left <-> right;
443 };
444 \end{codeexample}
445 %
446 You can pass any of the \meta{text alignment options} understood by
447 \tikzname, such as |text centered|:
448 %
449 \begin{codeexample}[
450 width=5cm,
451 preamble={\usetikzlibrary{graphs,graphdrawing}
452 \usegdlibrary{trees}},
453 ]
454 \tikz [subgraph text top=text centered]
455 \graph [tree layout] {
456 a -> { b -> {c, d}, e -> {f, g -> h} };
457
458 left [draw, circle] // { b, c, d };
459 };
460 \end{codeexample}
461 %
462 To place a label \emph{outside} the subgraph node, use a label, typically
463 defined using the |quotes| library:
464 %
465 \begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing,quotes}
466 \usegdlibrary{trees}}]
467 \tikz \graph [tree layout] {
468 a -> { b -> {c, d}, e -> {f, g -> h} };
469
470 / ["left", draw] // { b, c, d } <->
471 / ["right", draw] // { e, f, g, h};
472 };
473 \end{codeexample}
474 %
475 \end{key}
476
477 \begin{key}{/tikz/subgraph text bottom=\meta{text alignment options} (default ragged right)}
478 Works like |subgraph text top|, only the text placed at the bottom.
479 \end{key}
480
481 Note that there are no keys |subgraph text left| or |... right|, for somewhat
482 technical reasons.
483
484 \begin{key}{/tikz/subgraph text sep=\meta{dimension} (initially .1em)}
485 Some space added between the inner nodes of a subgraph node and the text
486 labels.
487 \end{key}
488
489
490 \subsubsection{Overlapping Sublayouts}
491 \label{section-gd-layout-resolve}
492
493 Nodes and edges can be part of several layouts. This will inevitably lead to
494 conflicts because algorithm will disagree on where a node should be placed on
495 the canvas. For this reason, there are some rules governing how such conflicts
496 are resolved: Given a layout, starting with the main layout, the graph drawing
497 system does the following:
498 %
499 \begin{enumerate}
500 \item We start by first processing the (direct) sublayouts of the current
501 layout (recursively). Sublayouts may overlap (they may share one or
502 more nodes), but we run the specified layout algorithm for each
503 sublayout independently on a ``fresh copy'' of all the nodes making up
504 the sublayout. In particular, different, conflicting positions may be
505 computed for nodes when they are present in several sublayouts.
506 \item Once all nodes in the sublayouts have been laid out in this way, we
507 \emph{join} overlapping elements. The idea is that if two layouts share
508 exactly one vertex, we can shift them around so that his vertex is at
509 the same position in both layouts. In more detail, the following
510 happens:
511
512 We build a (conceptual) graph whose nodes are the sublayouts and in
513 which there is an edge between two nodes if the sublayouts represented
514 by these elements have a node in common. Inside the resulting graph, we
515 treat each connected component separately. Each component has the
516 property that the sublayouts represented by the nodes in the component
517 overlap by at least one node. We now \emph{join} them as follows: We
518 start with the first sublayout in the component (``first'' with respect
519 to the order in which they appear in the input graph) and ``mark'' this
520 sublayout. We loop the following instructions as long as possible:
521 Search for the first sublayout (again, with respect to the order in
522 which they appear in the input) that is connect by an edge to a marked
523 sublayout. The sublayout will now have at least one node in common with
524 the marked sublayouts (possibly, even more). We consider the first such
525 node (again, first respect to the input ordering) and shift the whole
526 sublayout is such a way that this particular node is at the position is
527 has in the marked sublayouts. Note that after the shift, other nodes
528 that are also present in the marked sublayouts may lie at a different
529 position in the current sublayout. In this case, the position in the
530 marked sublayouts ``wins''. We then mark the sublayout.
531 \item When the above algorithm has run, we will have computed positions for
532 all nodes in all sublayouts of each of the components. For each
533 component, we contract all nodes of the component to a single node.
534 This new node will be ``large'' in the sense that its convex hull is
535 the convex hull of all the nodes in the component. All nodes that used
536 to be part of the component are removed and the new large node is added
537 (with arcs adjusted appropriately).
538 \item We now run the layout's algorithm on the resulting nodes (the
539 remaining original nodes and the contracted nodes).
540 \item In a last step, once the graph has been laid out, we expand the nodes
541 that were previously contracted. For this, the nodes that were deleted
542 earlier get reinserted, but shifted by whatever amount the contraction
543 node got shifted.
544 \end{enumerate}
545
546
547 \subsection{Miscellaneous Options}
548
549 \includeluadocumentationof{pgf.gd.control.library}