| 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} |