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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
-- 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 SupergraphVertexSplitOptimization = {}
-- 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"
declare {
key = "split me",
type = "boolean",
initial = false
}
declare {
key = "split on disappearing",
type = "boolean",
initial = true
}
declare {
key = "split on disjoint neighbors",
type = "boolean",
initial = false
}
declare {
key = "split on disjoint children",
type = "boolean",
initial = false
}
declare {
key = "split on disjoint parents",
type = "boolean",
initial = false
}
declare {
key = "split all supervertices",
type = "boolean",
initial = false
}
declare {
key = "unbound vertex splitting",
algorithm = SupergraphVertexSplitOptimization,
phase = "supergraph optimization",
phase_default = true,
summary = [["
Use this key if you want to disable animations.
Instead of producing animations the evolving graph animation phasephase animates all vertices including movements and
fade in or fade out animations.
"]],
documentation = [["
See ToDo
"]]
}
-- Helpfunctions
-- Implementation
function SupergraphVertexSplitOptimization:run()
local supergraph = assert(self.supergraph, "no supergraph passed")
local split_on_dissapearing = self.digraph.options["split on disappearing"]
local split_on_no_common_neighbor = self.digraph.options["split on disjoint neighbors"]
local split_on_no_common_child = self.digraph.options["split on disjoint children"]
local split_on_no_common_parent = self.digraph.options["split on disjoint parents"]
local split_all = self.digraph.options["split all supervertices"]
for _, supernode in ipairs(supergraph.vertices) do
-- follow trace of the supernode
local snapshots = supergraph:getSnapshots(supernode)
local splitsnapshots = {}
for i=2, #snapshots do
local s = snapshots[i]
local s_prev = snapshots[i - 1]
local can_split = false
if supergraph:consecutiveSnapshots(s_prev, s) then
local v1 = supergraph:getSnapshotVertex(supernode, s_prev)
local v2 = supergraph:getSnapshotVertex(supernode, s)
local is_child1 = {}
local is_parent1 = {}
local is_neighbor1 = {}
local incoming1 = s_prev:incoming(v1)
local outgoing1 = s_prev:outgoing(v1)
for _,e in ipairs(incoming1) do
local p = supergraph:getSupervertex(e.tail)
if p then
is_parent1[p] = true
is_neighbor1[p] = true
end
end
for _,e in ipairs(outgoing1) do
local p = supergraph:getSupervertex(e.head)
if p then
is_child1[p] = true
is_neighbor1[p] = true
end
end
local incoming2 = s:incoming(v2)
local outgoing2 = s:outgoing(v2)
no_common_parent = true
no_common_child = true
no_common_neighbor = true
for _,e in ipairs(incoming2) do
local p = supergraph:getSupervertex(e.tail)
if p then
if is_neighbor1[p] then
no_common_neighbor = false
end
if is_parent1[p] then
no_common_parent = false
end
if (not no_common_neighbor) and (not no_common_parent) then
break
end
end
end
for _,e in ipairs(outgoing2) do
local p = supergraph:getSupervertex(e.head)
if p then
if is_neighbor1[p] then
no_common_neighbor = false
end
if is_child1[p] then
no_common_child = false
end
if (not no_common_neighbor) and (not no_common_child) then
break
end
end
end
if no_common_neighbor and split_on_no_common_neighbor then
can_split = true
--texio.write("[N@".. s.timestamp .."]")
end
if no_common_parent and split_on_no_common_parent then
can_split = true
--texio.write("[P@".. s.timestamp .."]")
end
if no_common_child and split_on_no_common_child then
can_split = true
--texio.write("[N@".. s.timestamp .."]")
end
if v2.options["split me"] then
can_split = true
end
else
can_split = true
--texio.write("[R@".. s.timestamp .."]")
end
if can_split or split_all then
table.insert(splitsnapshots, s)
end
end
if #splitsnapshots>0 then
supergraph:splitSupervertex(supernode, splitsnapshots)
end
end
end
-- Done
return SupergraphVertexSplitOptimization
|