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.lua637
1 files changed, 637 insertions, 0 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
new file mode 100644
index 00000000000..24e9a69c385
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua
@@ -0,0 +1,637 @@
+-- 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/trees/SpanningTreeComputation.lua,v 1.7 2013/05/23 20:01:29 tantau Exp $
+
+
+
+---
+-- @section subsection {Spanning Tree Computation}
+--
+-- \label{subsection-gd-spanning-tree}
+-- 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 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,
+-- the spanning tree will be the original graph.
+--
+-- The computation of the spanning tree is a non-trivial process since
+-- 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 cylce removal in layered graph
+-- drawing algorithms will be unified, but, currently, they are
+-- 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
+-- default algorithm is |breadth first spanning tree|.
+--
+--\begin{codeexample}[]
+--\tikz \graph [tree layout, breadth first spanning tree]
+--{
+-- 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}
+--
+-- @end
+
+local SpanningTreeComputation = {}
+
+
+
+-- Namespace
+require("pgf.gd.trees").SpanningTreeComputation = SpanningTreeComputation
+
+
+-- Imports
+local lib = require "pgf.gd.lib"
+
+local Vertex = require "pgf.gd.model.Vertex"
+local Digraph = require "pgf.gd.model.Digraph"
+
+
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+
+
+-- ------------------------- --
+-- General tree parameters --
+-- ------------------------- --
+
+
+
+
+---
+--
+declare {
+ key = "breadth first spanning tree",
+ algorithm = {
+ run =
+ function (self)
+ 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.
+ "]]
+ }
+
+---
+
+declare {
+ key = "depth first spanning tree",
+ algorithm = {
+ run =
+ function (self)
+ 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.
+ "]]
+ }
+
+---
+--
+declare {
+ key = "root",
+ 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.
+ "]]
+ }
+
+
+---
+--
+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|.
+ "]]
+ }
+
+
+
+---
+-- 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
+ "]]
+ }
+
+
+
+
+---
+--
+declare {
+ key = "no span edge",
+ use = {
+ { 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 }
+ }
+ }
+ };
+ "]]
+}
+
+
+
+---
+declare {
+ key = "span priority ->",
+ 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.
+ "]],
+ documentation = [["
+ When you write
+\begin{codeexample}[code only]
+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}
+ "]]
+}
+
+
+
+---
+
+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 = [["
+ When you write
+\begin{codeexample}[code only]
+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''.
+ "]]
+}
+
+
+declare {
+ key = "span priority <-",
+ type = "number",
+ initial = "8",
+}
+
+declare {
+ key = "span priority reversed <-",
+ type = "number",
+ initial = "7",
+}
+
+declare {
+ key = "span priority --",
+ type = "number",
+ initial = "5",
+}
+
+declare {
+ key = "span priority reversed --",
+ type = "number",
+ initial = "5",
+}
+
+declare {
+ key = "span priority <->",
+ type = "number",
+ initial = "5",
+}
+
+declare {
+ key = "span priority reversed <->",
+ type = "number",
+ initial = "5",
+}
+
+declare {
+ key = "span priority -!-",
+ type = "number",
+ initial= "10",
+}
+
+declare {
+ key = "span priority reversed -!-",
+ type = "number",
+ initial= "10",
+}
+
+---
+
+declare {
+ key = "span using directed",
+ use = {
+ { key = "span priority reversed <-", value = 3},
+ { 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.
+ "]],
+ 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
+ };
+ "]]
+}
+
+---
+
+declare {
+ key = "span using all",
+ use = {
+ { key = "span priority <-", value = 5},
+ { key = "span priority ->", value = 5},
+ { key = "span priority <->", value = 5},
+ { key = "span priority --", value = 5},
+ { key = "span priority -!-", value = 5},
+ { key = "span priority reversed <-", value = 5},
+ { key = "span priority reversed ->", value = 5},
+ { key = "span priority reversed <->", value = 5},
+ { key = "span priority reversed --", value = 5},
+ { key = "span priority reversed -!-", value = 5},
+ },
+
+ summary = [["
+ Assings a uniform priority of 5 to all edges.
+ "]]
+}
+
+
+-- The implementation
+
+--
+-- Compute a spanning tree of a graph
+--
+-- The algorithm will favor nodes according to their priority. This is
+-- determined through an edge priority function.
+--
+-- @param ugraph An undirected graph for which the spanning tree
+-- should be computed
+-- @param dfs True if depth first should be used, false if breadth
+-- first should be used.
+--
+-- @return A new graph that is a spanning tree.
+
+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]
+
+ -- Traverse tree, giving preference to directed edges and, that
+ -- failing, to undirected and bidirected edges, and, that failing,
+ -- all other edges.
+ local marked = {}
+
+ local stacks = { -- 10 stacks for 10 priorities, with 1 being the highest
+ { { parent = nil, node = root}, top = 1, bottom = 1 },
+ { top = 0, bottom = 1},
+ { top = 0, bottom = 1},
+ { top = 0, bottom = 1},
+ { top = 0, bottom = 1},
+ { top = 0, bottom = 1},
+ { top = 0, bottom = 1},
+ { top = 0, bottom = 1},
+ { 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
+ end
+ end
+
+ if not marked[node] then
+
+ -- The node is good!
+ marked[node] = true
+
+ if parent then
+ 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
+ end
+ end
+ end
+
+ -- Now, copy vertex list
+ local copy = {}
+ 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
+ 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
+ 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)
+ end
+ end
+ end
+
+ tree.root = root
+
+ return tree
+end
+
+
+
+-- Done
+
+return SpanningTreeComputation \ No newline at end of file