summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua
blob: 169c7ff5e19351d7478fcfc15cf53c3f9dfe4512 (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
-- Copyright 2012 by Till Tantau
--
-- This file may be distributed an/or modified
--
-- 1. under the LaTeX Project Public License and/or
-- 2. under the GNU Public License
--
-- See the file doc/generic/pgf/licenses/LICENSE for more information

-- @release $Header$


local key           = require 'pgf.gd.doc'.key
local documentation = require 'pgf.gd.doc'.documentation
local summary       = require 'pgf.gd.doc'.summary
local example       = require 'pgf.gd.doc'.example


--------------------------------------------------------------------
key          "tree layout"

summary      "This layout uses the Reingold--Tilform method for drawing trees."

documentation
[[
The Reingold--Tilford method is a standard method for drawing
trees. It is described in:
%
\begin{itemize}
  \item
    E.~M.\ Reingold and J.~S.\ Tilford,
    \newblock Tidier drawings of trees,
    \newblock \emph{IEEE Transactions on Software Engineering,}
    7(2), 223--228, 1981.
\end{itemize}
%
My implementation in |graphdrawing.trees| follows the following paper, which
introduces some nice extensions of the basic algorithm:
%
\begin{itemize}
  \item
    A.\ Br\"uggemann-Klein, D.\ Wood,
    \newblock Drawing trees nicely with \TeX,
    \emph{Electronic Publishing,} 2(2), 101--115, 1989.
\end{itemize}
%
As a historical remark, Br\"uggemann-Klein and Wood have implemented
their version of the Reingold--Tilford algorithm directly in \TeX\
(resulting in the Tree\TeX\ style). With the power of Lua\TeX\ at
our disposal, the 2012 implementation in the |graphdrawing.tree|
library is somewhat more powerful and cleaner, but it really was an
impressive achievement to implement this algorithm back in 1989
directly in \TeX.

The basic idea of the Reingold--Tilford algorithm is to use the
following rules to position the nodes of a tree (the following
description assumes that the tree grows downwards, other growth
directions are handled by the automatic orientation mechanisms of
the graph drawing library):
%
\begin{enumerate}
  \item For a node, recursively compute a layout for each of its children.
  \item Place the tree rooted at the first child somewhere on the page.
  \item Place the tree rooted at the second child to the right of the
    first one as near as possible so that no two nodes touch (and such
    that the |sibling sep| padding is not violated).
  \item Repeat for all subsequent children.
  \item Then place the root above the child trees at the middle
    position, that is, at the half-way point between the left-most and
    the right-most child of the node.
\end{enumerate}
%
The standard keys |level distance|, |level sep|, |sibling distance|,
and |sibling sep|, as well as the |pre| and |post| versions of these
keys, as taken into consideration when nodes are positioned. See also
Section~\ref{subsection-gd-dist-pad} for details on these keys.

\noindent\textbf{Handling of Missing Children.}
As described in Section~\ref{section-gd-missing-children}, you can
specify that some child nodes are ``missing'' in the tree, but some
space should be reserved for them. This is exactly what happens:
When the subtrees of the children of a node are arranged, each
position with a missing child is treated as if a zero-width,
zero-height subtree were present at that positions:
%
\begin{codeexample}[]
\tikz [tree layout, nodes={draw,circle}]
  \node {r}
    child { node {a}
      child [missing]
      child { node {b} }
    }
    child[missing];
\end{codeexample}
%
or in |graph| syntax:
%
\begin{codeexample}[]
  \tikz \graph [tree layout, nodes={draw,circle}]
  {
    r -> {
      a -> {
        , %missing
        b},
      % missing
    }
  };
\end{codeexample}
%
More than one child can go missing:
%
\begin{codeexample}[]
\tikz \graph [tree layout, nodes={draw,circle}, sibling sep=0pt]
  { r -> { a, , ,b -> {c,d}, ,e} };
\end{codeexample}
%
Although missing children are taken into consideration for the
computation of the placement of the children of a root node relative
to one another and also for the computation of the position of the
root node, they are usually \emph{not} considered as part of the
``outline'' of a subtree (the \texttt{minimum number of children}
key ensures that |b|, |c|, |e|, and |f| all have a missing right
child):
%
\begin{codeexample}[]
\tikz \graph [tree layout, minimum number of children=2,
              nodes={draw,circle}]
  { a -> { b -> c -> d, e -> f -> g } };
\end{codeexample}
%
This behaviour of ``ignoring'' missing children in later stages of
the recursion can be changed using the key |missing nodes get space|.

\noindent\textbf{Significant Pairs of Siblings.}
Br\"uggemann-Klein and Wood have proposed an extension of the
Reingold--Tilford method that is intended to better highlight the
overall structure of a tree. Consider the following two trees:
%
\begin{codeexample}[]
\tikz [baseline=(a.base), tree layout, minimum number of children=2,
       sibling distance=5mm, level distance=5mm]
  \graph [nodes={circle, inner sep=0pt, minimum size=2mm, fill, as=}]{
    a -- { b -- c -- { d -- e, f -- { g, h }}, i -- j -- k[second] }
  };\quad
\tikz [baseline=(a.base), tree layout, minimum number of children=2,
       sibling distance=5mm, level distance=5mm]
  \graph [nodes={circle, inner sep=0pt, minimum size=2mm, fill, as=}]{
    a -- { b -- c -- d -- e, i -- j -- { f -- {g,h}, k } }
  };
\end{codeexample}
%
As observed by Br\"uggemann-Klein and Wood, the two trees are
structurally quite different, but the Reingold--Tilford method
places the nodes at exactly the same positions and only one edge
``switches'' positions. In order to better highlight the differences
between the trees, they propose to add a little extra separation
between siblings that form a \emph{significant pair}. They define
such a pair as follows: Consider the subtrees of two adjacent
siblings. There will be one or more levels where these subtrees have
a minimum distance. For instance, the following two trees the
subtrees of the nodes |a| and |b| have a minimum distance only at
the top level in the left example, and in all levels in the second
example. A \emph{significant pair} is a pair of siblings where the
minimum distance is encountered on any level other than the first
level. Thus, in the first example there is no significant pair,
while in the second example |a| and |b| form such a pair.
%
\begin{codeexample}[]
\tikz \graph [tree layout, minimum number of children=2,
               level distance=5mm, nodes={circle,draw}]
  { / -> { a -> / -> /, b -> /[second] -> /[second] }};
  \quad
\tikz \graph [tree layout, minimum number of children=2,
              level distance=5mm, nodes={circle,draw}]
  { / -> { a -> / -> /, b -> / -> / }};
\end{codeexample}
%
Whenever the algorithm encounters a significant pair, it adds extra
space between the siblings as specified by the |significant sep|
key.
]]


example
[[
\tikz [tree layout, sibling distance=8mm]
  \graph [nodes={circle, draw, inner sep=1.5pt}]{
    1 -- { 2 -- 3 -- { 4 -- 5, 6 -- { 7, 8, 9 }}, 10 -- 11 -- { 12, 13 } }
  };
]]


example
[[
\tikz [tree layout, grow=-30,
       sibling distance=0mm, level distance=0mm,]
  \graph [nodes={circle, draw, inner sep=1.5pt}]{
    1 -- { 2 -- 3 -- { 4 -- 5, 6 -- { 7, 8, 9 }}, 10 -- 11 -- { 12, 13 } }
  };
]]
--------------------------------------------------------------------



--------------------------------------------------------------------
key          "missing nodes get space"

summary
[[
When set to true, missing children are treated as if they where
zero-width, zero-height nodes during the whole tree layout process.
]]


example
[[
\tikz \graph [tree layout, missing nodes get space,
              minimum number of children=2, nodes={draw,circle}]
{ a -> { b -> c -> d, e -> f -> g } };
]]
--------------------------------------------------------------------





--------------------------------------------------------------------
key          "significant sep"

summary
[[
This space is added to significant pairs by the modified
Reingold--Tilford algorithm.
]]

example
[[
\tikz [baseline=(a.base), tree layout, significant sep=1em,
       minimum number of children=2,
       sibling distance=5mm, level distance=5mm]
  \graph [nodes={circle, inner sep=0pt, minimum size=2mm, fill, as=}]{
    a -- { b -- c -- { d -- e, f -- { g, h }}, i -- j -- k[second] }
  };\quad
\tikz [baseline=(a.base), tree layout, significant sep=1em,
       minimum number of children=2,
       sibling distance=5mm, level distance=5mm]
  \graph [nodes={circle, inner sep=0pt, minimum size=2mm, fill, as=}]{
    a -- { b -- c -- d -- e, i -- j -- { f -- {g,h}, k } }
  };
]]
--------------------------------------------------------------------



--------------------------------------------------------------------
key          "binary tree layout"

summary
[[
A layout based on the Reingold--Tilford method for drawing
binary trees.
]]

documentation
[[
This key executes:
%
\begin{enumerate}
  \item |tree layout|, thereby selecting the Reingold--Tilford method,
  \item |minimum number of children=2|, thereby ensuring the all nodes
    have (at least) two children or none at all, and
  \item |significant sep=10pt| to highlight significant pairs.
\end{enumerate}
%
In the examples, the last one is taken from the paper of
Br\"uggemann-Klein and Wood. It demonstrates nicely the
advantages of having the full power of \tikzname's anchoring and the
graph drawing engine's orientation mechanisms at one's disposal.
]]


example
[[
\tikz [grow'=up, binary tree layout, sibling distance=7mm, level distance=7mm]
  \graph {
    a -- { b -- c -- { d -- e, f -- { g, h }}, i -- j -- k[second] }
  };
]]

example
[[
\tikz \graph [binary tree layout] {
  Knuth -> {
    Beeton -> Kellermann [second] -> Carnes,
    Tobin -> Plass -> { Lamport, Spivak }
  }
};\qquad
\tikz [>=spaced stealth']
  \graph [binary tree layout, grow'=right, level sep=1.5em,
          nodes={right, fill=blue!50, text=white, chamfered rectangle},
                 edges={decorate,decoration={snake, post length=5pt}}]
  {
    Knuth -> {
      Beeton -> Kellermann [second] -> Carnes,
      Tobin -> Plass -> { Lamport, Spivak }
    }
  };
]]
--------------------------------------------------------------------



--------------------------------------------------------------------
key          "extended binary tree layout"

summary
[[
This algorithm is similar to |binary tree layout|, only the
option \texttt{missing nodes get space} is executed and the
\texttt{significant sep} is zero.
]]

example
[[
\tikz [grow'=up, extended binary tree layout,
       sibling distance=7mm, level distance=7mm]
  \graph {
    a -- { b -- c -- { d -- e, f -- { g, h }}, i -- j -- k[second] }
  };
]]
--------------------------------------------------------------------