diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/doc/trees/ReingoldTilford1981.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/doc/trees/ReingoldTilford1981.lua | 309 |
1 files changed, 309 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/doc/trees/ReingoldTilford1981.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/doc/trees/ReingoldTilford1981.lua new file mode 100644 index 00000000000..794214c5f74 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/doc/trees/ReingoldTilford1981.lua @@ -0,0 +1,309 @@ +-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/doc/trees/ReingoldTilford1981.lua,v 1.1 2013/03/05 23:44:30 tantau Exp $ + + +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 signifcant 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] } + }; +]] +-------------------------------------------------------------------- + + |