summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ChildSpec.lua188
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua30
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua598
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/doc.lua110
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/library.lua2
5 files changed, 451 insertions, 477 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ChildSpec.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ChildSpec.lua
index 5af36428858..0b975fd3291 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ChildSpec.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ChildSpec.lua
@@ -33,11 +33,10 @@
-- 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:
--- %
+-- \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}
@@ -52,18 +51,15 @@
-- 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:
--- %
+-- \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|.
+-- \item You can simply specify the index of a child directly using
+-- the key |desired child index|.
-- \end{enumerate}
--
-- @end
@@ -82,27 +78,27 @@ declare {
initial = "0",
summary = [["
- Specifies how many children a tree node must have at least. If
- there are less, ``virtual'' children are added.
+ 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.
+ 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 } };
+ \tikz \graph [binary tree layout,level distance=5mm]
+ { a -> { b->c->d, e->f->g } };
"]]
}
@@ -112,60 +108,65 @@ 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.
+ 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.
+ 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} };
- "]]
+ 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} };
+ "]]
}
}
@@ -178,9 +179,9 @@ declare {
{ key = "desired child index", value = 1},
},
- summary = [["
- A shorthand for setting the desired child number to |1|.
- "]]
+ summary = [["
+ A shorthand for setting the desired child number to |1|.
+ "]]
}
---
@@ -191,11 +192,11 @@ declare {
{ key = "desired child index", value = 2},
},
- summary = [["
- A shorthand for setting the desired child number to |2|.
- "]]
+ summary = [["
+ A shorthand for setting the desired child number to |2|.
+ "]]
}
-
+
---
@@ -205,11 +206,11 @@ declare {
{ key = "desired child index", value = 3},
},
- summary = [["
- A shorthand for setting the desired child number to |3|.
+ summary = [["
+ A shorthand for setting the desired child number to |3|.
"]]
}
-
+
---
@@ -219,7 +220,8 @@ declare {
{ key = "desired child index", value = 4}
},
- summary = [["
- A shorthand for setting the desired child number to |4|.
+ summary = [["
+ A shorthand for setting the desired child number to |4|.
"]]
}
+
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua
index 69babd443c7..8eba23a2106 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua
@@ -27,7 +27,7 @@ local Storage = require "pgf.gd.lib.Storage"
declare {
key = "tree layout",
algorithm = ReingoldTilford1981,
-
+
preconditions = {
connected = true,
tree = true
@@ -69,7 +69,7 @@ declare {
},
documentation_in = "pgf.gd.trees.doc"
}
-
+
---
declare {
key = "extended binary tree layout",
@@ -86,16 +86,16 @@ declare {
-- Now comes the implementation:
-
+
function ReingoldTilford1981:run()
local root = self.spanning_tree.root
local layers = Storage.new()
local descendants = Storage.new()
-
+
self.extended_version = self.digraph.options['missing nodes get space']
-
+
self:precomputeDescendants(root, 1, layers, descendants)
self:computeHorizontalPosition(root, layers, descendants)
layered.arrange_layers_by_baselines(layers, self.adjusted_bb, self.ugraph)
@@ -113,7 +113,7 @@ function ReingoldTilford1981:precomputeDescendants(node, depth, layers, descenda
my_descendants[#my_descendants + 1] = d
end
end
-
+
layers[node] = depth
descendants[node] = my_descendants
end
@@ -121,7 +121,7 @@ end
function ReingoldTilford1981:computeHorizontalPosition(node, layers, descendants)
-
+
local children = self.spanning_tree:outgoing(node)
node.pos.x = 0
@@ -133,19 +133,19 @@ function ReingoldTilford1981:computeHorizontalPosition(node, layers, descendants
for i=1,#children do
self:computeHorizontalPosition(children[i].head, layers, descendants)
end
-
+
-- Now, compute minimum distances and shift them
local right_borders = {}
for i=1,#children-1 do
-
+
local local_right_borders = {}
-
+
-- Advance "right border" of the subtree rooted at
-- the i-th child
for _,d in ipairs(descendants[children[i].head]) do
local layer = layers[d]
- local x = d.pos.x
+ local x = d.pos.x
if self.extended_version or not (layer > child_depth and d.kind == "dummy") then
if not right_borders[layer] or right_borders[layer].pos.x < x then
right_borders[layer] = d
@@ -160,7 +160,7 @@ function ReingoldTilford1981:computeHorizontalPosition(node, layers, descendants
-- Now left for i+1 st child
for _,d in ipairs(descendants[children[i+1].head]) do
local layer = layers[d]
- local x = d.pos.x
+ local x = d.pos.x
if self.extended_version or not (layer > child_depth and d.kind == "dummy") then
if not left_borders[layer] or left_borders[layer].pos.x > x then
left_borders[layer] = d
@@ -179,13 +179,13 @@ function ReingoldTilford1981:computeHorizontalPosition(node, layers, descendants
local n1 = right_borders[layer]
if n1 then
shift = math.max(
- shift,
+ shift,
layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, n1, n2) + n1.pos.x - n2.pos.x
)
end
if local_right_borders[layer] then
if layer > child_depth and
- (left_borders[layer].pos.x - local_right_borders[layer].pos.x <= first_dist) then
+ (left_borders[layer].pos.x - local_right_borders[layer].pos.x <= first_dist) then
is_significant = true
end
end
@@ -200,7 +200,7 @@ function ReingoldTilford1981:computeHorizontalPosition(node, layers, descendants
d.pos.x = d.pos.x + shift
end
end
-
+
-- Finally, position root in the middle:
node.pos.x = (children[1].head.pos.x + children[#children].head.pos.x) / 2
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua
index 8951ce0538c..791fb81e658 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua
@@ -18,7 +18,7 @@
-- Although the algorithms of this library are tailored to layout trees,
-- they will work for any graph as input. First, if the graph is not
-- connected, it is decomposed into connected components and these are
--- laid out individually. Second, for each component, a spanning tree of
+-- laid out individiually. Second, for each component, a spanning tree of
-- the graph is computed first and the layout is computed for this
-- spanning tree; all other edges will still be drawn, but they have no
-- impact on the placement of the nodes. If the graph is already a tree,
@@ -28,9 +28,9 @@
-- a non-tree graph has many different possible spanning trees. You can
-- choose between different methods for deciding on a spanning tree, it
-- is even possible to implement new algorithms. (In the future, the
--- computation of spanning trees and the cycle removal in layered graph
+-- computation of spanning trees and the cylce removal in layered graph
-- drawing algorithms will be unified, but, currently, they are
--- implemented differently.)
+-- implemented differently.)
--
-- Selects the (sub)algorithm that is to be used for computing spanning
-- trees whenever this is requested by a tree layout algorithm. The
@@ -39,15 +39,15 @@
--\begin{codeexample}[]
--\tikz \graph [tree layout, breadth first spanning tree]
--{
--- 1 -- {2,3,4,5} -- 6;
---};
+-- 1 -- {2,3,4,5} -- 6;
+--};
--\end{codeexample}
--\begin{codeexample}[]
--\tikz \graph [tree layout, depth first spanning tree]
--{
--- 1 --[bend right] {2,3,4,5 [>bend left]} -- 6;
---};
---\end{codeexample}
+-- 1 --[bend right] {2,3,4,5 [>bend left]} -- 6;
+--};
+--\end{codeexample}
--
-- @end
@@ -82,91 +82,90 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
--
declare {
key = "breadth first spanning tree",
- algorithm = {
+ algorithm = {
run =
function (self)
- return SpanningTreeComputation.computeSpanningTree(self.ugraph, false, self.events)
+ return SpanningTreeComputation.computeSpanningTree(self.ugraph, false, self.events)
end
},
phase = "spanning tree computation",
phase_default = true,
- summary = [["
- This key selects ``breadth first'' as the (sub)algorithm for
- computing spanning trees. Note that this key does not cause a graph
- drawing scope to start; the key only has an effect in conjunction
- with keys like |tree layout|.
-"]],
- documentation = [["
- The algorithm will be called whenever a graph drawing algorithm
- needs a spanning tree on which to operate. It works as follows:
- %
- \begin{enumerate}
- \item It looks for a node for which the |root| parameter is
- set. If there are several such nodes, the first one is used.
- If there are no such nodes, the first node is used.
-
- Let call the node determined in this way the \emph{root node}.
- \item For every edge, a \emph{priority} is determined, which is a
- number between 1 and 10. How this happens, exactly, will be
- explained in a moment. Priority 1 means ``most important'' while
- priority 10 means ``least important''.
- \item Starting from the root node, we now perform a breadth first
- search through the tree, thereby implicitly building a spanning
- tree: Suppose for a moment that all edges have priority~1. Then,
- the algorithm works just the way that a normal breadth first
- search is performed: We keep a queue of to-be-visited nodes and
- while this queue is not empty, we remove its first node. If this
- node has not yet been visited, we add all its neighbors at the
- end of the queue. When a node is taken out of the queue, we make
- it the child of the node whose neighbor it was when it was
- added. Since the queue follows the ``first in, first out''
- principle (it is a fifo queue), the children of the root will be
- all nodes at distance $1$ form the root, their children will be
- all nodes at distance $2$, and so on.
- \item Now suppose that some edges have a priority different
- from~1, in which case things get more complicated. We now keep
- track of one fifo queue for each of the ten possible
- priorities. When we consider the neighbors of a node, we actually
- consider all its incident edges. Each of these edges has a certain
- priority and the neighbor is put into the queue of the edge's
- priority. Now, we still remove nodes normally from the queue for
- priority~1; only if this queue is empty and there is still a node
- in the queue for priority~2 we remove the first element from this
- queue (and proceed as before). If the second queue is also empty,
- we try the third, and so on up to the tenth queue. If all queues
- are empty, the algorithm stops.
- \end{enumerate}
-
- The effect of the ten queues is the following: If the edges of
- priority $1$ span the whole graph, a spanning tree consisting solely
- of these edges will be computed. However, if they do not, once we
- have visited reachable using only priority 1 edges, we will extend
- the spanning tree using a priority 2 edge; but then we once switch
- back to using only priority 1 edges. If neither priority~1 nor
- priority~2 edges suffice to cover the whole graph, priority~3 edges
- are used, and so on.
+ summary = [["
+ This key selects ``breadth first'' as the (sub)algorithm for
+ computing spanning trees. Note that this key does not cause a graph
+ drawing scope to start; the key only has an effect in conjunction
+ with keys like |tree layout|.
+ "]],
+ documentation = [["
+ The algorithm will be called whenever a graph drawing algorithm
+ needs a spanning tree on which to operate. It works as follows:
+ \begin{enumerate}
+ \item It looks for a node for which the |root| parameter is
+ set. If there are several such nodes, the first one is used. If there
+ are no such nodes, the first node is used.
+
+ Let call the node determined in this way the \emph{root node}.
+ \item For every edge, a \emph{priority} is determined, which is a
+ number between 1 and 10. How this happens, exactly, will be
+ explained in a moment. Priority 1 means ``most important'' while
+ priority 10 means ``least important''.
+ \item Starting from the root node, we now perform a breadth first
+ search through the tree, thereby implicitly building a spanning
+ tree: Suppose for a moment that all edges have priority~1. Then,
+ the algorithm works just the way that a normal breadth first
+ search is performed: We keep a queue of to-be-visited nodes and
+ while this queue is not empty, we remove its first node. If this
+ node has not yet been visited, we add all its neighbors at the
+ end of the queue. When a node is taken out of the queue, we make
+ it the child of the node whose neighbor it was when it was
+ added. Since the queue follows the ``first in, first out''
+ principle (it is a fifo queue), the children of the root will be
+ all nodes at distance $1$ form the root, their children will be
+ all nodes at distance $2$, and so on.
+ \item Now suppose that some edges have a priority different
+ from~1, in which case things get more complicated. We now keep
+ track of one fifo queue for each of the ten possible
+ priorities. When we consider the neighbors of a node, we actually
+ consider all its incident edges. Each of these edges has a certain
+ priority and the neighbor is put into the queue of the edge's
+ priority. Now, we still remove nodes normally from the queue for
+ priority~1; only if this queue is empty and there is still a node
+ in the queue for priority~2 we remove the first element from this
+ queue (and proceed as before). If the second queue is also empty,
+ we try the third, and so on up to the tenth queue. If all queues
+ are empty, the algorithm stops.
+ \end{enumerate}
+
+ The effect of the ten queues is the following: If the edges of
+ priority $1$ span the whole graph, a spanning tree consisting solely
+ of these edges will be computed. However, if they do not, once we
+ have visited reachable using only priority 1 edges, we will extend
+ the spanning tree using a priority 2 edge; but then we once switch
+ back to using only priority 1 edges. If neither priority~1 nor
+ priority~2 edges suffice to cover the whole graph, priority~3 edges
+ are used, and so on.
"]]
-}
+ }
---
declare {
key = "depth first spanning tree",
- algorithm = {
+ algorithm = {
run =
function (self)
- return SpanningTreeComputation.computeSpanningTree(self.ugraph, true, self.events)
+ return SpanningTreeComputation.computeSpanningTree(self.ugraph, true, self.events)
end
},
phase = "spanning tree computation",
- summary = [["
- Works exactly like |breadth first spanning tree| (same handling of
- priorities), only the queues are now lifo instead of
- fifo.
- "]]
-}
+ summary = [["
+ Works exactly like |breadth first spanning tree| (same handling of
+ priorities), only the queues are now lifo instead of
+ fifo.
+ "]]
+ }
---
--
@@ -175,13 +174,13 @@ declare {
type = "boolean",
default = true,
- summary = [["
- This Boolean parameter is used in the computation of spanning
- trees. When can be set for a node, this node will be used as the
- root for the spanning tree computation. If several nodes have this
- option set, the first node will be used.
- "]]
-}
+ summary = [["
+ This Boolean parameter is used in the computation of spanning
+ trees. When can be set for a node, this node will be used as the
+ root for the spanning tree computation. If several nodes have this
+ option set, the first node will be used.
+ "]]
+ }
---
@@ -190,29 +189,29 @@ declare {
key = "span priority",
type = "number",
- summary = [["
- Explicitly sets the ``span priority'' of an edge to \meta{number}, which must be
- a number between |1| and |10|. The priority of edges is used by
- spanning tree computations, see |breadth first spanning tree|.
- "]]
-}
-
+ summary = [["
+ Explicitly sets the ``span priority'' of an edge to \meta{number}, which must be
+ a number between |1| and |10|. The priority of edges is used by
+ spanning tree computations, see |breadth first spanning tree|.
+ "]]
+ }
+
---
--- when it comes to choosing which edges are part of the spanning tree.
+-- when it comes to choosing which edges are part of the spanning tree.
declare {
key = "span edge",
use = {
{ key = "span priority", value = 1 },
},
- summary = [["
- An easy-to-remember shorthand for |span priority=1|. When this key
- is used with an edge, it will always be preferred over other edges
- "]]
-}
-
+ summary = [["
+ An easy-to-remember shorthand for |span priority=1|. When this key
+ is used with an edge, it will always be preferred over other edges
+ "]]
+ }
+
@@ -224,29 +223,29 @@ declare {
{ key = "span priority", value = 10 },
},
- summary = [["
- An easy-to-remember shorthand for |span priority=10|. This causes
- the edge to be used only as a last resort as part of a spanning
- tree.
- "]],
- documentation = [["
- In the example, we add lots of edges that would normally be
- preferred in the computation of the spanning tree, but use
- |no span edge| to cause the algorithm to ignore these edges.
- "]],
- examples = [["
- \tikz \graph [tree layout, nodes={draw}, sibling distance=0pt,
- every group/.style={
- default edge kind=->, no span edge,
- path=source}]
- {
- 5 -> {
- "1,3" -> {0,2,4},
- 11 -> {
- "7,9" -> { 6, 8, 10 }
+ summary = [["
+ An easy-to-remember shorthand for |span priority=10|. This causes
+ the edge to be used only as a last resort as part of a spanning
+ tree.
+ "]],
+ documentation = [["
+ In the example, we add lots of edges that would normally be
+ preferred in the computation of the spanning tree, but use
+ |no span edge| to cause the algorithm to ignore these edges.
+ "]],
+ examples = [["
+ \tikz \graph [tree layout, nodes={draw}, sibling distance=0pt,
+ every group/.style={
+ default edge kind=->, no span edge,
+ path=source}]
+ {
+ 5 -> {
+ "1,3" -> {0,2,4},
+ 11 -> {
+ "7,9" -> { 6, 8, 10 }
+ }
}
- }
- };
+ };
"]]
}
@@ -258,85 +257,79 @@ declare {
type = "number",
initial = "3",
- summary = [["
- This key stores the span priority of all edges whose direction is
- |->|. There are similar keys for all other directions, such as
- |span priority <-| and so on.
+ summary = [["
+ This key stores the span priority of all edges whose direction is
+ |->|. There are similar keys for all other directions, such as
+ |span priority <-| and so on.
"]],
- documentation = [["
- When you write
- %
+ documentation = [["
+ When you write
\begin{codeexample}[code only]
-graph { a -> b -- c <- [span priority=2] d }
+graph { a -> b -- c <- [span priority=2] d }
\end{codeexample}
- %
- the priority of the edge from |a| to |b| would be the current
- value of the key |span priority ->|, the priority of the edge from
- |b| to |c| would be the current value of |span priority --|, and
- the priority of the edge from |c| to |d| would be |2|, regardless
- of the value of |span priority <-|.
-
- The defaults for the priorities are:
- %
- \begin{itemize}
- \item |span priority -> = 3|
- \item |span priority -- = 5|
- \item |span priority <-> = 5|
- \item |span priority <- = 8|
- \item |span priority -!- = 10|
- \end{itemize}
+ the priority of the edge from |a| to |b| would be the current
+ value of the key |span priority ->|, the priority of the edge from
+ |b| to |c| would be the current value of |span priority --|, and
+ the priority of the edge from |c| to |d| would be |2|, regardless
+ of the value of |span priority <-|.
+
+ The defaults for the priorities are:
+ \begin{itemize}
+ \item |span priority -> = 3|
+ \item |span priority -- = 5|
+ \item |span priority <-> = 5|
+ \item |span priority <- = 8|
+ \item |span priority -!- = 10|
+ \end{itemize}
"]]
}
-
+
---
-
+
declare {
key = "span priority reversed ->",
type = "number",
initial = "9",
- documentation = [["
- This key stores the span priority of traveling across reversed
- edges whose actual direction is |->| (again, there are similar keys
- for all other directions).
+ documentation = [["
+ This key stores the span priority of traveling across reversed
+ edges whose actual direction is |->| (again, there are similar keys
+ for all other directions).
"]],
- documentation = [["
- When you write
- %
+ documentation = [["
+ When you write
\begin{codeexample}[code only]
-graph { a -> b -- c <- [span priority=2] d }
+graph { a -> b -- c <- [span priority=2] d }
\end{codeexample}
- %
- there are, in addition to the priorities indicated above, also
- further edge priorities: The priority of the (reversed) edge |b|
- to |a| is |span priority reversed ->|, the priority of the
- (reversed) edge |c| to |b| is |span priority reversed --|, and the
- span priority of the reversed edge |d| to |c| is |2|, regardless
- of the value of |span priority reversed <-|.
-
- The defaults for the priorities are:
- %
- \begin{itemize}
- \item |span priority reversed -> = 9|
- \item |span priority reversed -- = 5|
- \item |span priority reversed <-> = 5|
- \item |span priority reversed <- = 7|
- \item |span priority reversed -!- = 10|
- \end{itemize}
-
- The default priorities are set in such a way, that non-reversed |->|
- edges have top priorities, |--| and |<->| edges have the same
- priorities in either direction, and |<-| edges have low priority in
- either direction (but going |a <- b| from |b| to |a| is given higher
- priority than going from |a| to |b| via this edge and also higher
- priority than going from |b| to |a| in |a -> b|).
-
- Keys like |span using directed| change the priorities ``en bloc''.
+ there are, in addition to the priorities indicated above, also
+ further edge priorities: The priority of the (reversed) edge |b|
+ to |a| is |span priority reversed ->|, the priority of the
+ (reversed) edge |c| to |b| is |span priority reversed --|, and the
+ span priority of the reversed edge |d| to |c| is |2|, regardless
+ of the value of |span priority reversed <-|.
+
+ The defaults for the priorities are:
+ \begin{itemize}
+ \item |span priority reversed -> = 9|
+ \item |span priority reversed -- = 5|
+ \item |span priority reversed <-> = 5|
+ \item |span priority reversed <- = 7|
+ \item |span priority reversed -!- = 10|
+ \end{itemize}
+
+ The default priorities are set in such a way, that non-reversed |->|
+ edges have top priorities, |--| and |<->| edges have the same
+ priorities in either direction, and |<-| edges have low priority in
+ either direction (but going |a <- b| from |b| to |a| is given higher
+ priority than going from |a| to |b| via this edge and also higher
+ priority than going from |b| to |a| in |a -> b|).
+
+ Keys like |span using directed| change the priorities ``en bloc''.
"]]
}
-
+
declare {
key = "span priority <-",
@@ -395,23 +388,23 @@ declare {
{ key = "span priority <->", value = 3},
{ key = "span priority reversed <->", value = 3},
},
- summary = [["
- This style sets a priority of |3| for all edges that are directed
- and ``go along the arrow direction'', that is, we go from |a| to
- |b| with a priority of |3| for the cases |a -> b|, |b <- a|,
- |a <-> b|, and |b <-> a|.
- This strategy is nice with trees specified with both forward and
- backward edges.
+ summary = [["
+ This style sets a priority of |3| for all edges that are directed
+ and ``go along the arrow direction'', that is, we go from |a| to
+ |b| with a priority of |3| for the cases |a -> b|, |b <- a|,
+ |a <-> b|, and |b <-> a|.
+ This strategy is nice with trees specified with both forward and
+ backward edges.
"]],
- examples = [["
- \tikz \graph [tree layout, nodes={draw}, sibling distance=0pt,
- span using directed]
- {
- 3 <- 5[root] -> 8,
- 1 <- 3 -> 4,
- 7 <- 8 -> 9,
- 1 -- 4 -- 7 -- 9
- };
+ examples = [["
+ \tikz \graph [tree layout, nodes={draw}, sibling distance=0pt,
+ span using directed]
+ {
+ 3 <- 5[root] -> 8,
+ 1 <- 3 -> 4,
+ 7 <- 8 -> 9,
+ 1 -- 4 -- 7 -- 9
+ };
"]]
}
@@ -431,9 +424,9 @@ declare {
{ key = "span priority reversed --", value = 5},
{ key = "span priority reversed -!-", value = 5},
},
-
- summary = [["
- Assings a uniform priority of 5 to all edges.
+
+ summary = [["
+ Assings a uniform priority of 5 to all edges.
"]]
}
@@ -447,7 +440,7 @@ declare {
-- determined through an edge priority function.
--
-- @param ugraph An undirected graph for which the spanning tree
--- should be computed
+-- should be computed
-- @param dfs True if depth first should be used, false if breadth
-- first should be used.
--
@@ -456,7 +449,7 @@ declare {
function SpanningTreeComputation.computeSpanningTree (ugraph, dfs, events)
local tree = Digraph.new (ugraph) -- copy vertices
-
+
local edge_priorities = ugraph.options['/graph drawing/edge priorities']
local root = lib.find(ugraph.vertices, function (v) return v.options['root'] end) or ugraph.vertices[1]
@@ -467,7 +460,7 @@ function SpanningTreeComputation.computeSpanningTree (ugraph, dfs, events)
local marked = {}
local stacks = { -- 10 stacks for 10 priorities, with 1 being the highest
- { { parent = nil, node = root}, top = 1, bottom = 1 },
+ { { parent = nil, node = root}, top = 1, bottom = 1 },
{ top = 0, bottom = 1},
{ top = 0, bottom = 1},
{ top = 0, bottom = 1},
@@ -478,51 +471,51 @@ function SpanningTreeComputation.computeSpanningTree (ugraph, dfs, events)
{ top = 0, bottom = 1},
{ top = 0, bottom = 1}
}
-
+
local function stack_is_non_empty (s) return s.top >= s.bottom end
-
+
while lib.find(stacks, stack_is_non_empty) do
local parent, node
-
+
for _,stack in ipairs(stacks) do
if stack_is_non_empty(stack) then
- -- Pop
- parent = stack[stack.top].parent
- node = stack[stack.top].node
-
- stack[stack.top] = nil
- stack.top = stack.top - 1
-
- break
+ -- Pop
+ parent = stack[stack.top].parent
+ node = stack[stack.top].node
+
+ stack[stack.top] = nil
+ stack.top = stack.top - 1
+
+ break
end
end
-
+
if not marked[node] then
-
+
-- The node is good!
marked[node] = true
-
+
if parent then
- tree:connect(parent,node)
+ tree:connect(parent,node)
end
-
+
local arcs = ugraph:outgoing(node)
-
+
for j=1,#arcs do
- local arc = arcs[dfs and j or #arcs - j + 1]
- local head = arc.head
-
- if not marked[head] then
- local priority = arc:spanPriority()
- local stack = assert(stacks[priority], "illegal edge priority")
- if dfs then
- stack.top = stack.top + 1
- stack[stack.top] = { parent = node, node = head}
- else
- stack.bottom = stack.bottom - 1
- stack[stack.bottom] = { parent = node, node = head}
- end
- end
+ local arc = arcs[dfs and j or #arcs - j + 1]
+ local head = arc.head
+
+ if not marked[head] then
+ local priority = arc:spanPriority()
+ local stack = assert(stacks[priority], "illegal edge priority")
+ if dfs then
+ stack.top = stack.top + 1
+ stack[stack.top] = { parent = node, node = head}
+ else
+ stack.bottom = stack.bottom - 1
+ stack[stack.bottom] = { parent = node, node = head}
+ end
+ end
end
end
end
@@ -532,105 +525,106 @@ function SpanningTreeComputation.computeSpanningTree (ugraph, dfs, events)
for i,v in ipairs(tree.vertices) do
copy[i] = v
end
-
+
-- Now, setup child lists
for _,v in ipairs(copy) do
-- Children as they come from the spanning tree computation
tree:sortOutgoing(v, function (a,b) return a:eventIndex() < b:eventIndex() end)
local outgoings = tree:outgoing(v)
-
+
-- Compute children as they come in the event list:
local children = {}
-
+
local i = (v.event.index or 0)+1
while i <= #events and events[i].kind == "edge" do
i = i + 1
end
-
+
if events[i] and events[i].kind == "begin" and events[i].parameters == "descendants" then
-- Ok, the node is followed by a descendants group
-- Now scan for nodes that are not inside a descendants group
local stop = events[i].end_index
local j = i+1
while j <= stop do
- if events[j].kind == "node" then
- children[#children+1] = events[j].parameters
- elseif events[j].kind == "begin" and events[j].parameters == "descendants" then
- j = events[j].end_index
- end
- j = j + 1
+ if events[j].kind == "node" then
+ children[#children+1] = events[j].parameters
+ elseif events[j].kind == "begin" and events[j].parameters == "descendants" then
+ j = events[j].end_index
+ end
+ j = j + 1
end
-- Test, whether outgoings and children contain the same nodes:
local function same_elements()
- local hash = {}
- for v,c in ipairs(outgoings) do
- hash[c.head] = true
- end
- local count = 0
- for _,c in pairs(children) do
- if c ~= "" then
- count = count + 1
- if not hash[c] or count > #outgoings then
- return false
- end
- end
- end
- return count == #outgoings
+ local hash = {}
+ for v,c in ipairs(outgoings) do
+ hash[c.head] = true
+ end
+ local count = 0
+ for _,c in pairs(children) do
+ if c ~= "" then
+ count = count + 1
+ if not hash[c] or count > #outgoings then
+ return false
+ end
+ end
+ end
+ return count == #outgoings
end
if same_elements() and #outgoings > 0 then
- -- increase number of children, if necessary
- local needed = math.max(#children, lib.lookup_option('minimum number of children', v, ugraph))
- for i=1,#children do
- if children[i] ~= "" then
- local d = children[i].options['desired child index']
- needed = d and math.max(needed, d) or needed
- end
- end
-
- local new_children = {}
- for i=1,#children do
- if children[i] ~= "" then
- local d = children[i].options['desired child index']
- if d then
- local target = d
-
- while new_children[target] do
- target = 1 + (target % #children)
- end
- new_children[target] = children[i]
- end
- end
- end
- for i=1,#children do
- if children[i] ~= "" then
- local d = children[i].options['desired child index']
- if not d then
- local target = i
-
- while new_children[target] do
- target = 1 + (target % #children)
- end
- new_children[target] = children[i]
- end
- end
- end
- for i=1,needed do
- if not new_children[i] then
- local new_child = Vertex.new{ kind = "dummy" }
- new_children[i] = new_child
- tree:add {new_child}
- tree:connect(v,new_child)
- end
- end
-
- tree:orderOutgoing(v,new_children)
+
+ -- increase number of children, if necessary
+ local needed = math.max(#children, lib.lookup_option('minimum number of children', v, ugraph))
+ for i=1,#children do
+ if children[i] ~= "" then
+ local d = children[i].options['desired child index']
+ needed = d and math.max(needed, d) or needed
+ end
+ end
+
+ local new_children = {}
+ for i=1,#children do
+ if children[i] ~= "" then
+ local d = children[i].options['desired child index']
+ if d then
+ local target = d
+
+ while new_children[target] do
+ target = 1 + (target % #children)
+ end
+ new_children[target] = children[i]
+ end
+ end
+ end
+ for i=1,#children do
+ if children[i] ~= "" then
+ local d = children[i].options['desired child index']
+ if not d then
+ local target = i
+
+ while new_children[target] do
+ target = 1 + (target % #children)
+ end
+ new_children[target] = children[i]
+ end
+ end
+ end
+ for i=1,needed do
+ if not new_children[i] then
+ local new_child = Vertex.new{ kind = "dummy" }
+ new_children[i] = new_child
+ tree:add {new_child}
+ tree:connect(v,new_child)
+ end
+ end
+
+ tree:orderOutgoing(v,new_children)
end
end
end
-
+
tree.root = root
return tree
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
};
]]
--------------------------------------------------------------------
+
+
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/library.lua
index a0019666ac8..b8e36982cfc 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/library.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/library.lua
@@ -16,7 +16,7 @@
-- Sections \ref{section-library-graphs}
-- and~\ref{section-trees}). The job of the graph drawing algorithms from
-- this library is to turn the specification of trees into beautiful
--- layouts.
+-- layouts.
--
-- We start this section with a description of algorithms, then we have a
-- look at how missing children can be specified and at what happens when