diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GreedyTemporalCycleRemoval.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GreedyTemporalCycleRemoval.lua | 177 |
1 files changed, 177 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GreedyTemporalCycleRemoval.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GreedyTemporalCycleRemoval.lua new file mode 100644 index 00000000000..17c46aa352c --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GreedyTemporalCycleRemoval.lua @@ -0,0 +1,177 @@ +-- Copyright 2015 by Malte Skambath +-- +-- 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 + + +local GreedyTemporalCycleRemoval = {} + +-- Imports +local lib = require "pgf.gd.lib" +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + +local Vertex = require "pgf.gd.model.Vertex" +local Digraph = require "pgf.gd.model.Digraph" +local Coordinate = require "pgf.gd.model.Coordinate" + +local PriorityQueue = require "pgf.gd.lib.PriorityQueue" + +-- Keys + +--- + +declare { + key = "split critical arc head", + type = "boolean", + initial = true, + summary = "Specifies, that for a critical the tail node is separated" +} + +--- + +declare { + key = "split critical arc tail", + type = "boolean", + initial = true, + summary = "Specifies, that for a critical the tail node is separated" +} + +--- + +declare { + key = "greedy temporal cycle removal", + algorithm = GreedyTemporalCycleRemoval, + phase = "temporal cycle removal", + phase_default = true, + summary = [[" + A temporal dependency cycle is a cyclic path in the supergraph of + an evolving graph. Use this key if you want remove all temporal + dependency cycles by a greedy strategy which incrementally inserts + edge checks if this edge creates a cycle and splits at least one node + into two supernode at a given time. + "]], + documentation = [[" + See ToDo + "]] +} + +-- Helpfunctions +local function reachable(graph, v, w) + local visited = {} + local queue = PriorityQueue.new() + queue:enqueue(v,1) + while not queue:isEmpty() do + local vertex = queue:dequeue() + if vertex==w then + return true + end + local outgoings = graph:outgoing(vertex) + for _, e in ipairs(outgoings) do + local head = e.head + if not visited[head] then + visited[head] = true + if head == w then + return true + else + queue:enqueue(head,1) + end + end + end + end + return false +end + +-- Implementation + +function GreedyTemporalCycleRemoval:run() + local supergraph = assert(self.supergraph, "no supergraph passed") + local digraph = assert(self.digraph, "no digraph passed to the phase") + local split_tail = digraph.options["split critical arc tail"] + local split_head = digraph.options["split critical arc head"] + assert(split_tail or split_head, "without splitting nodes dependency cycles cannot be removed.") + + self:iterativeCycleRemoval(supergraph, split_tail, split_head) +end + +-- +-- Resolves all dependencies by splitting supernodes into multiple supernodes. +-- To resolve a cycle each edge will be inserted into a dependency graph +-- successively. Each time such edge closes a cycle the head and tail will +-- be splitet at the related snapshot. +-- +-- @param supergraph +-- +function GreedyTemporalCycleRemoval:iterativeCycleRemoval(supergraph, split_tail, split_head) + -- Build up the global dependency graph + -- A supernode v directly depends on another supernode w iff + -- there is a snapshot in which w is a child of w + local dependency_graph = Digraph.new(supergraph) + local stable_arcs = {} + for i, snapshot in ipairs(supergraph.snapshots) do + --local tree = snapshot.spanning_tree + for _,tree in ipairs(snapshot.spanning_trees) do + local new_arcs = {} + + for _, e in ipairs(tree.arcs) do + if e.head.kind ~= "dummy" and e.tail.kind~="dummy" then + table.insert(new_arcs, e) + + local sv = supergraph:getSupervertex(e.tail) + local sw = supergraph:getSupervertex(e.head) + local dep_arc = dependency_graph:arc(sv, sw) + + + if (not dep_arc) then + -- check if the edge v->w closes a cycle in the dependencygraph + --pgf.debug{dependency_graph} + local cycle_arc = reachable(dependency_graph, sw, sv) + dep_arc = dependency_graph:connect(sv,sw) +-- texio.write("\ncheck ".. sv.name.."->" .. sw.name) + if cycle_arc then + if split_tail then + supergraph:splitSupervertex(sv, { [1]=snapshot }) + end + if split_head then + supergraph:splitSupervertex(sw, { [1]=snapshot }) + end + + -- rebuild dependency graph + dependency_graph = Digraph.new(supergraph) + + for _, arc in ipairs(stable_arcs) do + dependency_graph:connect(arc.tail, arc.head) + end + + for _, arc in ipairs(new_arcs) do + local sv = supergraph:getSupervertex(arc.tail) + local sw = supergraph:getSupervertex(arc.head) + dependency_graph:connect(sv, sw) + end + end -- end of resovle cycle_arc + end + end + end + -- Stable Arcs: + for _, arc in ipairs(new_arcs) do + + local sv = supergraph:getSupervertex(arc.tail) + local sw = supergraph:getSupervertex(arc.head) + local deparc = dependency_graph:arc(sv, sw) +-- if not deparc or not stable_arcs[deparc] then +-- stable_arcs[deparc] = true + table.insert(stable_arcs, deparc) +-- end + + end + end -- end for spanning_tree + end -- end for snapshot +end + + +-- Done + +return GreedyTemporalCycleRemoval |