summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua598
1 files changed, 296 insertions, 302 deletions
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