summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua110
1 files changed, 44 insertions, 66 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua
index 169c7ff5e19..753f386bb9e 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua
@@ -25,55 +25,49 @@ 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.
+\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.
+\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.
+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):
-%
+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.
+\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.
+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
@@ -82,7 +76,6 @@ 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}
@@ -92,9 +85,7 @@ zero-height subtree were present at that positions:
}
child[missing];
\end{codeexample}
-%
or in |graph| syntax:
-%
\begin{codeexample}[]
\tikz \graph [tree layout, nodes={draw,circle}]
{
@@ -106,36 +97,31 @@ or in |graph| syntax:
}
};
\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):
-%
+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|.
+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]
@@ -147,8 +133,7 @@ overall structure of a tree. Consider the following two trees:
\graph [nodes={circle, inner sep=0pt, minimum size=2mm, fill, as=}]{
a -- { b -- c -- d -- e, i -- j -- { f -- {g,h}, k } }
};
-\end{codeexample}
-%
+\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
@@ -164,7 +149,6 @@ 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}]
@@ -174,7 +158,6 @@ while in the second example |a| and |b| form such a pair.
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.
@@ -207,8 +190,9 @@ 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.
+When set to true, missing children are treated as if they
+where zero-width, zero-height nodes during the whole tree layout
+process.
]]
@@ -228,10 +212,8 @@ example
key "significant sep"
summary
-[[
-This space is added to significant pairs by the modified
-Reingold--Tilford algorithm.
-]]
+[[ This space is added to signifcant pairs by the modified
+Reingold--Tilford algorithm. ]]
example
[[
@@ -256,22 +238,18 @@ example
key "binary tree layout"
summary
-[[
-A layout based on the Reingold--Tilford method for drawing
-binary trees.
-]]
+[[ 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.
+\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
@@ -292,33 +270,31 @@ example
\tikz \graph [binary tree layout] {
Knuth -> {
Beeton -> Kellermann [second] -> Carnes,
- Tobin -> Plass -> { Lamport, Spivak }
+ 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}}]
+ edges={decorate,decoration={snake, post length=5pt}}]
{
Knuth -> {
Beeton -> Kellermann [second] -> Carnes,
- Tobin -> Plass -> { Lamport, Spivak }
+ Tobin -> Plass -> { Lamport, Spivak }
}
};
]]
--------------------------------------------------------------------
-
+
--------------------------------------------------------------------
key "extended binary tree layout"
summary
-[[
-This algorithm is similar to |binary tree layout|, only the
+[[ 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.
-]]
+\texttt{significant sep} is zero. ]]
example
[[
@@ -329,3 +305,5 @@ example
};
]]
--------------------------------------------------------------------
+
+