1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
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
|