-- 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$
---
-- @section subsection {Specifying Missing Children}
--
-- \label{section-gd-missing-children}
--
-- In the present section we discuss keys for specifying missing children
-- in a tree. For many certain kind of trees, in particular for binary
-- trees, there are not just ``a certain number of children'' at each
-- node, but, rather, there is a designated ``first'' (or ``left'') child
-- and a ``second'' (or ``right'') child. Even if one of these children
-- is missing and a node actually has only one child, the single child will
-- still be a ``first'' or ``second'' child and this information should
-- be taken into consideration when drawing a tree.
--
-- The first useful key for specifying missing children is
-- |missing number of children| which allows you to state how many
-- children there are, at minimum.
--
-- Once the minimum number of children has been set, we still need a way
-- of specifying ``missing first children'' or, more generally, missing
-- children that are not ``at the end'' of the list of children. For
-- this, there are three methods:
-- %
-- \begin{enumerate}
-- \item When you use the |child| syntax, you can use the |missing| key
-- with the |child| command to indicate a missing child:
-- %
-- \begin{codeexample}[]
-- \tikz [binary tree layout, level distance=5mm]
-- \node {a}
-- child { node {b}
-- child { node {c}
-- child { node {d} }
-- } }
-- child { node {e}
-- child [missing]
-- child { node {f}
-- child [missing]
-- child { node {g}
-- } } };
-- \end{codeexample}
-- %
-- \item When using the |graph| syntax, you can use an ``empty node'',
-- which really must be completely empty and may not even contain a
-- slash, to indicate a missing node:
-- %
-- \begin{codeexample}[]
-- \tikz [binary tree layout, level distance=5mm]
-- \graph { a -> { b -> c -> d, e -> { , f -> { , g} } } };
-- \end{codeexample}
-- %
-- \item You can simply specify the index of a child directly using
-- the key |desired child index|.
-- \end{enumerate}
--
-- @end
-- Imports
local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
---
--
declare {
key = "minimum number of children",
type = "number",
initial = "0",
summary = [["
Specifies how many children a tree node must have at least. If
there are less, ``virtual'' children are added.
"]],
documentation = [["
When this key is set to |2| or more, the following happens: We first
compute a spanning tree for the graph, see
Section~\ref{subsection-gd-spanning-tree}. Then, whenever a node is
not a leaf in this spanning tree (when it has at least one child),
we add ``virtual'' or ``dummy'' nodes as children of the node until
the total number of real and dummy children is at least
\meta{number}. If there where at least \meta{number} children at the
beginning, nothing happens.
The new children are added after the existing children. This means
that, for instance, in a tree with \meta{number} set to |2|, for
every node with a single child, this child will be the first child
and the second child will be missing.
"]],
examples = [["
\tikz \graph [binary tree layout,level distance=5mm]
{ a -> { b->c->d, e->f->g } };
"]]
}
---
declare {
key = "desired child index",
type = "number",
summary = [["
Pass this key to a node to tell the graph drawing engine which child
number you ``desired'' for the node. Whenever all desires for the
children of a node are conflict-free, they will all be met; children
for which no desired indices were given will remain at their
position, whenever possible, but will ``make way'' for children with
a desired position.
"]],
documentation = [["
In detail, the following happens: We first
determine the total number of children (real or dummy) needed, which
is the maximum of the actual number of children, of the
\texttt{minimum number of children}, and of the highest desired
child index. Then we go over all children that have a desired child
index and put they at this position. If the position is already
taken (because some other child had the same desired index), the
next free position is used with a wrap-around occurring at the
end. Next, all children without a desired index are place using the
same mechanism, but they want to be placed at the position they had
in the original spanning tree.
While all of this might sound a bit complicated, the application of
the key in a binary tree is pretty straightforward: To indicate that
a node is a ``right'' child in a tree, just add \texttt{desired child index=2}
to it. This will make it a second child, possibly causing the fist
child to be missing. If there are two nodes specified as children of
a node, by saying \texttt{desired child index=}\meta{number} for one
of them, you will cause it be first or second child, depending on
\meta{number}, and cause the \emph{other} child to become the other
child.
Since |desired child index=2| is a bit long, the following shortcuts
are available: |first|, |second|, |third|, and |fourth|.
You might wonder why |second| is used rather than |right|. The
reason is that trees may also grow left and right and, additionally,
the |right| and |left| keys are already in use for
anchoring. Naturally, you can locally redefine them, if you want.
"]],
examples = {[["
\tikz \graph [binary tree layout, level distance=5mm]
{ a -> b[second] };
"]],[["
\tikz \graph [binary tree layout, level distance=5mm]
{ a -> { b[second], c} };
"]],[["
\tikz \graph [binary tree layout, level distance=5mm]
{ a -> { b, c[first]} };
"]],[["
\tikz \graph [binary tree layout, level distance=5mm]
{ a -> { b[second], c[second]} };
"]],[["
\tikz \graph [binary tree layout, level distance=5mm]
{ a -> { b[third], c[first], d} };
"]]
}
}
---
declare {
key = "first",
use = {
{ key = "desired child index", value = 1},
},
summary = [["
A shorthand for setting the desired child number to |1|.
"]]
}
---
declare {
key = "second",
use = {
{ key = "desired child index", value = 2},
},
summary = [["
A shorthand for setting the desired child number to |2|.
"]]
}
---
declare {
key = "third",
use = {
{ key = "desired child index", value = 3},
},
summary = [["
A shorthand for setting the desired child number to |3|.
"]]
}
---
declare {
key = "fourth",
use = {
{ key = "desired child index", value = 4}
},
summary = [["
A shorthand for setting the desired child number to |4|.
"]]
}