summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GraphAnimationCoordination.lua526
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GreedyTemporalCycleRemoval.lua114
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Skambath2016.lua362
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua197
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua186
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/TimeSpec.lua58
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/doc.lua50
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/layered.lua56
8 files changed, 771 insertions, 778 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GraphAnimationCoordination.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GraphAnimationCoordination.lua
index 31f8f27431b..2dd23937fe1 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GraphAnimationCoordination.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/GraphAnimationCoordination.lua
@@ -49,11 +49,11 @@ declare {
type = "boolean",
Initial = false,
documentation = [["
- This key specifies, if a supernode changed its
- visual properties since the last snapshot.
- The default value is |false| and prevent the algorithm
- to produce a lot of unnecessary animations.
- "]]
+ This key specifies, if a supernode changed its
+ visual properties since the last snapshot.
+ The default value is |false| and prevent the algorithm
+ to produce a lot of unnecessary animations.
+ "]]
}
declare {
@@ -70,12 +70,12 @@ declare {
type = "number",
initial = 0.5,
documentation = [["
- This key specifies a minimum time in which a single node
- has to be prohibited to be animated.
- For a node with minimum rest time of 1s that exists in a snapshot
- at time $t$ this means that all animations including movements and fadings
- are only allowed before $t$-0.5s and after $t$+0.5s.
- "]],
+ This key specifies a minimum time in which a single node
+ has to be prohibited to be animated.
+ For a node with minimum rest time of 1s that exists in a snapshot
+ at time $t$ this means that all animations including movements and fadings
+ are only allowed before $t$-0.5s and after $t$+0.5s.
+ "]],
}
declare {
@@ -83,9 +83,9 @@ declare {
type = "number",
initial = math.huge,
documentation = [["
- Use this key if you want to limit the time during nodes are allowed to move
- when they changing their positions.
- "]],
+ Use this key if you want to limit the time during nodes are allowed to move
+ when they changing their positions.
+ "]],
}
declare {
@@ -93,10 +93,7 @@ declare {
type = "boolean",
initial = true,
documentation = [["
- Use this key if you want to allow that the fade animations for or
- disappearing nodes may occurs while the mid time between two snapshots.
- If false then the appearing ends on the midtime and the disappearing
- starts in this moment.
+ Use this key if you want to allow that the fade animations for or dissappearing nodes may occurs while the mid time between two snapshots. If false then the appearing ends on the midtime and the disappering starts in this moment.
"]]
}
@@ -106,39 +103,40 @@ declare {
algorithm = GraphAnimationCoordination,
phase = "evolving graph animation",
phase_default = true,
- summary = [["
- This phase animates all vertices including movements and
- fade in or fade out animations given an evolving graph as sequence
- of single snapshot graphs.
+ summary = [["
+ This phase animates all vertices including movements and
+ fade in or fade out animations given an evolving graph as sequence
+ of single snapshot graphs.
"]],
- documentation = [["
- This phase animates all vertices including movements and
- fade in or fade out animations given an evolving graph as sequence
- of single snapshot graphs.
-
- Your algorithm needs to work on evolving graphs and has to use
- the |evolving graph animation| phase. You do not need to use
- this key by yourself then because this key starts the default
- algorithm algorithm of the phase.
- %
- \begin{codeexample}[]
- local ga_class = self.digraph.options.algorithm_phases['evolving graph animation']
- -- animate graph
- ga_class.new {
- main_algorithm = self,
- supergraph = supergraph,
- digraph = self.digraph,
- ugraph = self.ugraph
- }:run()
- \end{codeexample}
-
- This algorithm and phase require a supergraph instance and the original
- digraph and ugraph. Note that you have to set the layout of the snapshot
- nodes before running algorithms of this is useful.
+ documentation = [["
+ This phase animates all vertices including movements and
+ fade in or fade out animations given an evolving graph as sequence
+ of single snapshot graphs.
+
+ Your algorithm needs to work on evolving graphs and has to use
+ the |evolving graph animation| phase. You do not need to use
+ this key by yourself then because this key starts the default
+ algorithm algorithm of the phase.
+
+ \begin{codeexample}[]
+ local ga_class = self.digraph.options.algorithm_phases['evolving graph animation']
+ -- animate graph
+ ga_class.new {
+ main_algorithm = self,
+ supergraph = supergraph,
+ digraph = self.digraph,
+ ugraph = self.ugraph
+ }:run()
+ \end{codeexample}
+
+ This algorithm and phase require a supergraph instance and the original digraph and ugraph.
+ Note that you have to set the layout of the snapshot nodes before running algorithms of this
+ is useful.
+
"]],
}
--- Help functions
+-- Helpfunctions
--
-- Appends a move animation to a given snapshot object such that the
@@ -148,7 +146,7 @@ declare {
--
-- This means if we want to move a node 1cm to the right the value of
-- |c_from| has to be (0,0) while |c_to| must be (1,0). The argument
--- |c_from| is useful for a node which has a position but its
+-- |c_from| is usefull for a node which has a position but its
-- previous node related to the same supervertex is at a different
-- position. Then we can use this argument to move the new node to
-- its origin position for smooth transitions.
@@ -172,16 +170,16 @@ local function append_move_animation(object, c_from, c_to, t_start, t_end)
local t1 = (7*t_start + 5*t_end)/12
local t2 = (5*t_start + 7*t_end)/12
table.insert(animations, {
- attribute = "translate",
- entries = {
- { t = t_start, value = c_from},
--- { t = t1, value = c1 },
--- { t = t2, value = c2 },
- { t = t_end, value = c_to }
- },
- options = { { key = "freeze at end", },
--- {key = "entry control", value="0}{1",}
- }
+ attribute = "translate",
+ entries = {
+ { t = t_start, value = c_from},
+-- { t = t1, value = c1 },
+-- { t = t2, value = c2 },
+ { t = t_end, value = c_to }
+ },
+ options = { { key = "freeze at end", },
+-- {key = "entry control", value="0}{1",}
+ }
})
object.animations = animations
end
@@ -189,26 +187,26 @@ end
local function append_fade_animation(object, v_start, v_end, t_start, t_end)
local animations = object.animations or {}
-
+
if v_start == 0 then
table.insert(animations, {
- attribute = "stage",
- entries = { { t = t_start, value = "true"}, },
- options = { { key = "freeze at end" } }
+ attribute = "stage",
+ entries = { { t = t_start, value = "true"}, },
+ options = { { key = "freeze at end" } }
})
elseif v_end == 0 and nil then
table.insert(animations, {
- attribute = "stage",
- entries = { { t = t_end, value = "false"}, },
- options = { --{ key = "freeze at end" }
- }
- })
+ attribute = "stage",
+ entries = { { t = t_end, value = "false"}, },
+ options = { --{ key = "freeze at end" }
+ }
+ })
end
table.insert(animations, {
attribute = "opacity",
entries = {
- { t = t_start, value = v_start },
+ { t = t_start, value = v_start },
{ t = t_end, value = v_end } },
options = { { key = "freeze at end" } }
})
@@ -223,13 +221,13 @@ local function eq_offset(a1, a2, b1, b2)
local dy = ((a1.y-a2.y) - (b1.y-b2.y))
if dx<0 then dx = -dx end
if dy<0 then dy = -dy end
- return dx<0.001 and dy<0.001
+ return dx<0.001 and dy<0.001
end
--
-- Check if two arcs connect a pair of nodes at the same position.
-- This can be used as an indicator that two consecutive arcs
--- can be represented by the same arc object.
+-- can be representet by the same arc object.
--
local function eq_arc(arc1, arc2)
if not arc1 or not arc2 then
@@ -253,7 +251,7 @@ function GraphAnimationCoordination:run()
self.next_node = Storage.new()
self.visible_objects = Storage.new()
-
+
self:precomputeNodes()
self:precomputeEdges()
self:animateNodeAppearing()
@@ -265,7 +263,7 @@ end
function GraphAnimationCoordination:generateNodeMotions(node_types)
local supergraph = self.supergraph
local graph = self.digraph
-
+
for _, supervertex in ipairs(self.supergraph.vertices) do
local lj = -1
local last_v = nil
@@ -274,25 +272,25 @@ function GraphAnimationCoordination:generateNodeMotions(node_types)
local vertex = supergraph:getSnapshotVertex(supervertex, s)
if lj == j-1 and vertex and last_v then
- local mrt1 = last_v.options["minimum rest time"]/2
- local mrt2 = vertex.options["minimum rest time"]/2
-
+ local mrt1 = last_v.options["minimum rest time"]/2
+ local mrt2 = vertex.options["minimum rest time"]/2
+
local s1 = Coordinate.new(0,0)
- local e1 = Coordinate.new(vertex.pos.x-last_v.pos.x,-vertex.pos.y+last_v.pos.y)
-
- local s2 = Coordinate.new(-vertex.pos.x+last_v.pos.x,vertex.pos.y-last_v.pos.y)
- local e2 = Coordinate.new(0,0)
-
- local t_end = s.timestamp - math.max(0, mrt2)
- local t_start = last_time + math.max(0,mrt1)
-
- local representative = self.visible_objects[supervertex][s]
- if representative == vertex then
- append_move_animation(vertex, s2, e2, t_start, t_end)
- append_move_animation(last_v, s1, e1, t_start, t_end)
- else
- append_move_animation(representative,s1,e1,t_start,t_end)
- end
+ local e1 = Coordinate.new(vertex.pos.x-last_v.pos.x,-vertex.pos.y+last_v.pos.y)
+
+ local s2 = Coordinate.new(-vertex.pos.x+last_v.pos.x,vertex.pos.y-last_v.pos.y)
+ local e2 = Coordinate.new(0,0)
+
+ local t_end = s.timestamp - math.max(0, mrt2)
+ local t_start = last_time + math.max(0,mrt1)
+
+ local representative = self.visible_objects[supervertex][s]
+ if representative == vertex then
+ append_move_animation(vertex, s2, e2, t_start, t_end)
+ append_move_animation(last_v, s1, e1, t_start, t_end)
+ else
+ append_move_animation(representative,s1,e1,t_start,t_end)
+ end
end
last_time = s.timestamp
lj = j
@@ -302,59 +300,59 @@ function GraphAnimationCoordination:generateNodeMotions(node_types)
end
-
+
function GraphAnimationCoordination:generateEdgeMotions()
local supergraph = self.supergraph
local graph = self.digraph
-
+
for i, arc in ipairs(supergraph.arcs) do
local head = arc.head
local tail = arc.tail
-
+
local last_arc = nil
local last_time = nil
local last_v = nil
local last_w = nil
-
+
for j, s in ipairs(supergraph.snapshots) do
local v = supergraph:getSnapshotVertex(tail,s)
local w = supergraph:getSnapshotVertex(head,s)
if v and w then
- local this_arc = graph:arc(v,w) --or graph:arc(w,v)
+ local this_arc = graph:arc(v,w) --or graph:arc(w,v)
if this_arc then
- if this_arc and last_arc then
- local mrt1 = last_v.options["minimum rest time"]/2
- local mrt2 = v.options["minimum rest time"]/2
-
- local s1 = Coordinate.new(0,0)--lv.pos
- local e1 = Coordinate.new(v.pos.x-last_v.pos.x,-v.pos.y+last_v.pos.y)
-
- local s2 = Coordinate.new(-v.pos.x+last_v.pos.x,v.pos.y-last_v.pos.y)
- local e2 = Coordinate.new(0,0)
-
- local t_end = s.timestamp - math.max(0,mrt2)
- local t_start = last_time + math.max(0,mrt1)
-
- local representative = self.visible_objects[arc][s]
- if representative == this_arc then
- append_move_animation(last_arc, s1, e1, t_start,t_end)
- append_move_animation(this_arc, s2, e2, t_start,t_end)
- else
- append_move_animation(representative,s1,e1,t_start,t_end)
- end
- this_arc = representative
- end
- last_arc = this_arc
- last_v = v
- last_time = s.timestamp
- else
- last_arc = nil
- end
+ if this_arc and last_arc then
+ local mrt1 = last_v.options["minimum rest time"]/2
+ local mrt2 = v.options["minimum rest time"]/2
+
+ local s1 = Coordinate.new(0,0)--lv.pos
+ local e1 = Coordinate.new(v.pos.x-last_v.pos.x,-v.pos.y+last_v.pos.y)
+
+ local s2 = Coordinate.new(-v.pos.x+last_v.pos.x,v.pos.y-last_v.pos.y)
+ local e2 = Coordinate.new(0,0)
+
+ local t_end = s.timestamp - math.max(0,mrt2)
+ local t_start = last_time + math.max(0,mrt1)
+
+ local representative = self.visible_objects[arc][s]
+ if representative == this_arc then
+ append_move_animation(last_arc, s1, e1, t_start,t_end)
+ append_move_animation(this_arc, s2, e2, t_start,t_end)
+ else
+ append_move_animation(representative,s1,e1,t_start,t_end)
+ end
+ this_arc = representative
+ end
+ last_arc = this_arc
+ last_v = v
+ last_time = s.timestamp
+ else
+ last_arc = nil
+ end
else
- last_arc = nil
+ last_arc = nil
end
end
end
@@ -365,9 +363,9 @@ end
-- @field t_transition The mid time between two snapshot times.
-- @field fade_duration The duration of the fade animation
-- @field overlapping A boolean defining if the animation occurs
--- before and after the mid time (true) or if it
+-- beofre and after the mid time (true) or if it
-- starts/end only in one interval (false)
--- @field closing A boolean specifying if this is an outfading time
+-- @field closing A boolean specifieng if this is a outfading time
local function compute_fade_times(t_transition, fade_duration, overlapping, closing)
if overlapping then
@@ -396,9 +394,9 @@ function GraphAnimationCoordination:animateNodeAppearing()
local overlapping_out= true
local minimum_rest_time = math.max(0,vertex.options["minimum rest time"])
local allow_overlapping = vertex.options["overlapping transition"]
- local fadein_duration = 0.01
- local fadeout_duration = 0.01
-
+ local fadein_duration = 0.01
+ local fadeout_duration = 0.01
+
if self.is_first[vertex] then
fadein_duration = self.ugraph.options["fadein time"]
overlapping_in = false or allow_overlapping
@@ -416,7 +414,7 @@ function GraphAnimationCoordination:animateNodeAppearing()
fadeout_duration = (interval.to-interval.from-minimum_rest_time)/2
if overlapping then fadeout_duration = fadeout_duration*2 end
end
-
+
local fin = compute_fade_times(interval.from, fadein_duration, overlapping_in, false)
local fout = compute_fade_times(interval.to, fadeout_duration, overlapping_out, true)
@@ -424,23 +422,23 @@ function GraphAnimationCoordination:animateNodeAppearing()
if representative~= vertex then
table.insert(vertex.animations,{
- attribute = "stage",
- entries = { { t = 0, value = "false"}, },
- options = {}
+ attribute = "stage",
+ entries = { { t = 0, value = "false"}, },
+ options = {}
})
end
-
+
if interval.from > -math.huge and (vertex == representative or self.is_first[vertex]) then
-- only appears if the snapshot node is its own repr. or if in the prev snapshot is
-- no representative.
- append_fade_animation(representative, 0, 1, fin.t_start, fin.t_end)
+ append_fade_animation(representative, 0, 1, fin.t_start, fin.t_end)
end
if interval.to < math.huge and (self.is_last[vertex] or self.last_rep[vertex]) then
-- The snapshot node only disappears when the node is not visible
- -- in the next or (this=)last snapshot:
+ -- in the next or (this=)last snapshot:
append_fade_animation(representative, 1, 0, fout.t_start, fout.t_end)
end
- end
+ end
end
@@ -449,119 +447,121 @@ function GraphAnimationCoordination:animateEdgeAppearing()
local supergraph = self.supergraph
local graph = self.digraph
for _,edge in ipairs(graph.arcs) do
- local snapshot = supergraph:getSnapshot(edge.head)
- local int = snapshot.interval
- local superarc = supergraph:getSuperarc(edge)
- local representative = self.visible_objects[superarc][snapshot] or edge
-
- local minimum_rest_time = math.max(0,edge.head.options["minimum rest time"]/2,
- edge.tail.options["minimum rest time"]/2)
-
- local appears = math.max(int.from, int.from)
- local disappears = math.min(int.to, int.to)
-
- local overlapping_in = true -- init true for crossfading
- local overlapping_out= true
- local fadein_duration = 0.01
- local fadeout_duration = 0.01
- local allow_overlapping = (edge.tail.options["overlapping transition"] and edge.head.options["overlapping transition"])
-
- if self.is_first[edge] and not self.move_on_enter[edge] and not self.move_on_enter[edge.head] then
- fadein_duration = self.ugraph.options["fadein time"]
- overlapping_in = false or allow_overlapping
- end
-
- if self.is_last[edge] and not self.move_on_leave[edge] then
- fadeout_duration = self.ugraph.options["fadeout time"]
- overlapping_out = false or allow_overlapping
- end
-
-
- if self.is_first[edge]
- and (self.move_on_enter[edge.head]
- or self.move_on_enter[edge.tail] )
- then
- appears = snapshot.timestamp - minimum_rest_time
- end
- if self.is_last[edge] and
- (self.move_on_leave[edge.head]
- or self.move_on_leave[edge.tail]
- ) then
- disappears = snapshot.timestamp + minimum_rest_time
- end
-
- local fin = compute_fade_times(appears, fadein_duration, overlapping_in,false)
- local fout = compute_fade_times(disappears,fadeout_duration,overlapping_out,true)
-
- edge.animations = edge.animations or {}
-
- if representative~=edge then
- table.insert(edge.animations,{
- attribute = "stage",
- entries = { { t = 0, value = "false"}, },
- options = {}})
- end
-
- -- Fade in:
- if appears > -math.huge and (edge == representative or self.is_first[edge]) then
- append_fade_animation(representative, 0, 1, fin.t_start, fin.t_end )
- end
+ local snapshot = supergraph:getSnapshot(edge.head)
+ local int = snapshot.interval
+ local superarc = supergraph:getSuperarc(edge)
+ local representative = self.visible_objects[superarc][snapshot] or edge
+
+ local minimum_rest_time = math.max(0,edge.head.options["minimum rest time"]/2,
+ edge.tail.options["minimum rest time"]/2)
+
+ local appears = math.max(int.from, int.from)
+ local disappears = math.min(int.to, int.to)
+
+ local overlapping_in = true -- init true for crossfading
+ local overlapping_out= true
+ local fadein_duration = 0.01
+ local fadeout_duration = 0.01
+ local allow_overlapping = (edge.tail.options["overlapping transition"] and edge.head.options["overlapping transition"])
+
+ if self.is_first[edge] and not self.move_on_enter[edge] and not self.move_on_enter[edge.head] then
+ fadein_duration = self.ugraph.options["fadein time"]
+ overlapping_in = false or allow_overlapping
+ end
+
+ if self.is_last[edge] and not self.move_on_leave[edge] then
+ fadeout_duration = self.ugraph.options["fadeout time"]
+ overlapping_out = false or allow_overlapping
+ end
+
- -- Fade out:
- if disappears < math.huge and (self.is_last[edge] or self.last_rep[edge])then
- append_fade_animation(representative, 1, 0, fout.t_start,fout.t_end )
+ if self.is_first[edge]
+ and (self.move_on_enter[edge.head]
+ or self.move_on_enter[edge.tail] )
+ then
+ appears = snapshot.timestamp - minimum_rest_time
+ end
+ if self.is_last[edge] and
+ (self.move_on_leave[edge.head]
+ or self.move_on_leave[edge.tail]
+ ) then
+ disappears = snapshot.timestamp + minimum_rest_time
+ end
+
+ local fin = compute_fade_times(appears, fadein_duration, overlapping_in,false)
+ local fout = compute_fade_times(disappears,fadeout_duration,overlapping_out,true)
+
+ edge.animations = edge.animations or {}
+
+ if representative~=edge then
+ table.insert(edge.animations,{
+ attribute = "stage",
+ entries = { { t = 0, value = "false"}, },
+ options = {}})
+ end
+
+ -- Fade in:
+ if appears > -math.huge and (edge == representative or self.is_first[edge]) then
+ append_fade_animation(representative, 0, 1, fin.t_start, fin.t_end )
+ end
+
+ -- Fade out:
+ if disappears < math.huge and (self.is_last[edge] or self.last_rep[edge])then
+ append_fade_animation(representative, 1, 0, fout.t_start,fout.t_end )
+ end
+
end
- end
+
end
function GraphAnimationCoordination:precomputeNodes()
local supergraph = self.supergraph
-
+
for _, supernode in ipairs(supergraph.vertices) do
-
+
local vis_nodes = {}
self.visible_objects[supernode] = vis_nodes
-
+
local any_previous_node = nil
local previous_representant = nil
local node_before = nil
for i, s in ipairs(supergraph.snapshots) do
- local node = supergraph:getSnapshotVertex(supernode, s)
+ local node = supergraph:getSnapshotVertex(supernode, s)
if node then
- -- assume the node is the last node
- self.is_last[node] = true
-
- if node.options["modified"] then
- -- modified
- vis_nodes[s] = node
- previous_representant = node
- if any_previous_node then
- self.last_rep[any_previous_node] = true
- end
- else
- -- unmodified
- previous_representant = previous_representant or node
- vis_nodes[s] = previous_representant
- end
- any_previous_node = node
-
- if node_before then
- self.is_last[node_before] = false
- self.previous_node[node] = node_before
- self.next_node[node_before] = node
-
- local do_move = (( node.pos.x ~= node_before.pos.x )
- or (node.pos.y ~= node_before.pos.y))
- self.move_on_enter[node] = do_move
- self.move_on_leave[node_before] = do_move
- else
- self.is_first[node] = true
- end
- node_before = node
+ -- assume the node is the last node
+ self.is_last[node] = true
+
+ if node.options["modified"] then
+ -- modified
+ vis_nodes[s] = node
+ previous_representant = node
+ if any_previous_node then
+ self.last_rep[any_previous_node] = true
+ end
+ else
+ -- unmodified
+ previous_representant = previous_representant or node
+ vis_nodes[s] = previous_representant
+ end
+ any_previous_node = node
+
+ if node_before then
+ self.is_last[node_before] = false
+ self.previous_node[node] = node_before
+ self.next_node[node_before] = node
+
+ local do_move = (( node.pos.x ~= node_before.pos.x )
+ or (node.pos.y ~= node_before.pos.y))
+ self.move_on_enter[node] = do_move
+ self.move_on_leave[node_before] = do_move
+ else
+ self.is_first[node] = true
+ end
+ node_before = node
else
- node_before = nil
+ node_before = nil
end
end
end
@@ -574,8 +574,8 @@ function GraphAnimationCoordination:precomputeEdges()
local tail = arc.tail
if not ( self.is_first[head] or self.is_first[tail]) then
if not self.digraph:arc(self.previous_node[tail], self.previous_node[head]) then
- -- new arc connects existing nodes
- self.is_first[arc] = true
+ -- new arc connects existing nodes
+ self.is_first[arc] = true
end
else
-- arc and at least one node is new.
@@ -583,8 +583,8 @@ function GraphAnimationCoordination:precomputeEdges()
end
if not ( self.is_last[head] or self.is_last[tail]) then
if not self.digraph:arc(self.next_node[tail],self.next_node[head]) then
- -- arc disappears while nodes are still in the next snapshot
- self.is_last[arc] = true
+ -- arc disappears while nodes are still in the next snapshot
+ self.is_last[arc] = true
end
else
-- arc and at least one node disappears in the next snapshot
@@ -603,34 +603,34 @@ function GraphAnimationCoordination:precomputeEdges()
local previous_arc
local previous_representant
-
+
for _, s in ipairs(supergraph.arc_snapshots[superarc]) do
- local head = supergraph:getSnapshotVertex(superarc.head, s)
- local tail = supergraph:getSnapshotVertex(superarc.tail, s)
- -- use the digraph because the snapshot arc is not synced
- local arc = self.digraph:arc(tail, head)
-
- local modified = false
- local opt_array = arc:optionsArray('modified')
- for i = 1,#opt_array.aligned do
- modified = modified or opt_array[i]
- end
-
- if modified or
- not eq_arc(arc, previous_arc) or self.is_first[arc] then
- --modified
- previous_representant = arc
- vis_objects[s] = arc
- if previous_arc then
- self.last_rep[previous_arc] = true
- end
+ local head = supergraph:getSnapshotVertex(superarc.head, s)
+ local tail = supergraph:getSnapshotVertex(superarc.tail, s)
+ -- use the digraph because the snapshot arc is not syncted
+ local arc = self.digraph:arc(tail, head)
+
+ local modified = false
+ local opt_array = arc:optionsArray('modified')
+ for i = 1,#opt_array.aligned do
+ modified = modified or opt_array[i]
+ end
+
+ if modified or
+ not eq_arc(arc, previous_arc) or self.is_first[arc] then
+ --modified
+ previous_representant = arc
+ vis_objects[s] = arc
+ if previous_arc then
+ self.last_rep[previous_arc] = true
+ end
else
- -- unmodified
- previous_representant = previous_representant or arc
- vis_objects[s] = previous_representant
- end
- previous_arc = arc
- end
+ -- unmodified
+ previous_representant = previous_representant or arc
+ vis_objects[s] = previous_representant
+ end
+ previous_arc = arc
+ end
end
end
-- Done
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
index 0c348bcc8fd..17c46aa352c 100644
--- 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
@@ -47,19 +47,19 @@ declare {
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.
+ 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
+ documentation = [["
+ See ToDo
"]]
}
--- Help functions
+-- Helpfunctions
local function reachable(graph, v, w)
local visited = {}
local queue = PriorityQueue.new()
@@ -73,12 +73,12 @@ local function reachable(graph, v, w)
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
+ visited[head] = true
+ if head == w then
+ return true
+ else
+ queue:enqueue(head,1)
+ end
end
end
end
@@ -101,13 +101,13 @@ 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 split at the related snapshot.
+-- 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 if
+ -- 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 = {}
@@ -115,57 +115,57 @@ function GreedyTemporalCycleRemoval:iterativeCycleRemoval(supergraph, split_tail
--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 dependency graph
- --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 resolve cycle_arc
- end
+ 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)
+-- stable_arcs[deparc] = true
+ table.insert(stable_arcs, deparc)
-- end
-
+
end
end -- end for spanning_tree
end -- end for snapshot
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Skambath2016.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Skambath2016.lua
index 2beec1e216e..23bbdf36a8c 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Skambath2016.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Skambath2016.lua
@@ -6,7 +6,7 @@
-- 2. under the GNU Public License
--
-- See the file doc/generic/pgf/licenses/LICENSE for more information
---
+--
-- Imports
require "pgf.gd.trees.ChildSpec"
@@ -17,7 +17,7 @@ local Vertex = require "pgf.gd.model.Vertex"
local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
local layered = require "pgf.gd.layered"
local tlayered = require "pgf.gd.experimental.evolving.layered"
-local SpanningTreeComputation = require "pgf.gd.trees.SpanningTreeComputation"
+local SpanningTreeComputation = require "pgf.gd.trees.SpanningTreeComputation"
local lib = require "pgf.gd.lib"
local Storage = require "pgf.gd.lib.Storage"
@@ -71,19 +71,19 @@ declare {
--- Help functions
+-- Helpfunctions
---
-- Borders models the borderlines / the line of border vertices
-- of a tree or subtree structure which can change over time.
-- Each ordered and rooted tree or subtree has vertices per layer for which they
--- are on the outer places. On the left or respectively on the right.
+-- are on the outer places. On the left or respectivly on the right.
-- The field |left| and |right| stores the both borderlines.
-- A \emph{borderline} is an array. This array contains for each layer of the tree
-- a table mapping a given snapshot to the related border-vertex of the layer
-- in the snapshot.
---
--- @field left
+--
+-- @field left
-- @field right
--
local Borders = {}
@@ -136,7 +136,7 @@ function Borders.copyBordersAtSnapshot(source, target, snapshot)
level_border_left = target.left[i] or {}
level_border_right = target.right[i] or {}
assert(not level_border_left[snapshot] and not level_border_right[snapshot],
- "border for a given snapshot already defined")
+ "border for a given snapshat already defined")
level_border_left[snapshot] = source.left[i][snapshot]
level_border_right[snapshot] = source.right[i][snapshot]
target.left[i] = level_border_left
@@ -149,7 +149,7 @@ end
-- placed on the right next to the existing borders. For each level
-- and time in which the group has a border the borders on the right
-- will be replaced with this border. If it is not existing in the old
--- borders then also the left border will be adapted
+-- borders then also the left border will be adapted
--
-- @param borders The existing borders. These will be modified with
-- the borders of
@@ -164,27 +164,27 @@ local function adapt_borders(borders, group_borders, snapshots, ignore_dummies)
local r = borders.right[level] or {}
for _, s in pairs(snapshots) do
if ignore_dummies then
- local gls,grs = group_borders.left[level][s], group_borders.right[level][s]
- if gls~=nil then
- if gls.kind~="dummy" then
- l[s] = l[s] or gls
- end
- end
- if grs~=nil then
- if grs.kind~="dummy" then
- r[s] = grs or r[s]
- end
- end
+ local gls,grs = group_borders.left[level][s], group_borders.right[level][s]
+ if gls~=nil then
+ if gls.kind~="dummy" then
+ l[s] = l[s] or gls
+ end
+ end
+ if grs~=nil then
+ if grs.kind~="dummy" then
+ r[s] = grs or r[s]
+ end
+ end
else
- l[s] = l[s] or group_borders.left[level][s]
- r[s] = group_borders.right[level][s] or r[s]
+ l[s] = l[s] or group_borders.left[level][s]
+ r[s] = group_borders.right[level][s] or r[s]
end
-
+
end
borders.left[level] = l
borders.right[level] = r
end
-
+
end
--
@@ -211,16 +211,16 @@ end
local function shift_group(shift, group, snapshots, descendants)
assert(group,"no group passed")
assert(shift~=math.huge and shift ~=-math.huge,
- "shift must be a valid finite length")
+ "shift must be a valid finit length")
local shifted = {} -- remember which vertex was shifted during this run
local anchor = -math.huge
for _, s in ipairs(snapshots) do
- local v = group[s]
- if not shifted[v] and v then
+ local v = group[s]
+ if not shifted[v] and v then
v.pos.x = v.pos.x + shift
shifted[v] = true
- -- also shift all descendants of the group vertex
+ -- also shift all descendants of the group vertex
for _, d in ipairs(descendants[v]) do
if not shifted[d] then
d.pos.x = d.pos.x + shift
@@ -228,28 +228,28 @@ local function shift_group(shift, group, snapshots, descendants)
end
end
anchor = math.max(anchor, v.pos.x )
- end
+ end
end
return anchor
end
--
--- Traverse through the spanning tree |tree| of a snapshot and sort
--- the child nodes into groups. A group summarizes for a given parent
+-- Traverse through the spanneng tree |tree| of a snapshot and sort
+-- the child nodes into groups. A group summarises for a given parent
-- node all children node over time that are at the same child
-- position. The k-th child group groups[i] maps each snapshot to the
-- k-th node in the related snapshot.
--
--
-- @field supergraph the supergraph
---
+--
-- @field tree the tree or spanning tree to decide the indices of the
-- child nodes
--
-- @field childgroups a Storage which contains the list of childgroups
-- for each supernode
--
--- @field snapshot
+-- @field snapshot
--
local function precompute_childgroups(supergraph, tree, node, childgroups, snapshot)
local outgoings = tree:outgoing(node)
@@ -257,7 +257,7 @@ local function precompute_childgroups(supergraph, tree, node, childgroups, snaps
local supervertex = supergraph:getSupervertex(node)
local groups = childgroups[supervertex] or {}
for i, e in ipairs(outgoings) do
-
+
group = groups[i] or {}
assert(e.head, "no edge")
group[snapshot] = e.head
@@ -274,7 +274,7 @@ end
-- vertices in a tree by accumulation of the relative shifts on the
-- path from the root to the vertex recursively.
--
--- @param tree the tree in which the vertex's position should be
+-- @param tree the tree in which the vertice's position should be
-- computed.
--
-- @param vertex the next vertex that gets its absolute coordinate.
@@ -302,7 +302,7 @@ local function get_next(border_pair, next)
local nr = next.right[border_pair.right]
assert ((nl and nr) or (not nl and not nr))
return {left = nl, right = nr,
- }
+ }
end
local function add_shift(abs_shift, border_pair, next)
@@ -325,25 +325,25 @@ function Skambath2016:computeRequiredDistance(tree, vertex, i, shifts, next)
if clumb.right.kind=="dummy" then shifts[clumb.right] = 0 end
local v0 = outgoings[i].head
local v1 = outgoings[i+1].head
- local shift = layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, v0, v1) + shifts[clumb.right]
+ local shift = layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, v0, v1) + shifts[clumb.right]
local last0 = {left = clumb.left, right = clumb.right}
- local last1 = {left = v1, right = v1}
+ local last1 = {left = v1, right = v1}
local next0 = get_next(last0, next)
local next1 = get_next(last1, next)
local abs_shift0 = {left = shifts[clumb.left], right = shifts[clumb.right]}
- local abs_shift1 = {left = 0, right = 0}
+ local abs_shift1 = {left = 0, right = 0}
while (next0.left and next1.left) do
add_shift(abs_shift0, last0, next)
add_shift(abs_shift1, last1, next)
shift = math.max(shift,
- layered.ideal_sibling_distance(self.adjusted_bb,
- self.ugraph,
- next0.right,
- next1.left)
- + abs_shift0.right - abs_shift1.left)
--- texio.write("\n | "..(next0.right.name or "dummy").."<->"..(next1.left.name or "dummy").." :\t"..shift)
+ layered.ideal_sibling_distance(self.adjusted_bb,
+ self.ugraph,
+ next0.right,
+ next1.left)
+ + abs_shift0.right - abs_shift1.left)
+-- texio.write("\n | "..(next0.right.name or "dummy").."<->"..(next1.left.name or "dummy").." :\t"..shift)
last0, last1 = next0, next1
next0 = get_next(next0, next)
next1 = get_next(next1, next)
@@ -383,7 +383,7 @@ local function apply_shift(tree, vertex, i, shifts, next, border_ptr, shift)
next.left[last0.left] = next1.left
-- pgf.debug{last0,abs0,abs1,last1}
next.left_shift[last0.left] = shift - abs0.left + (abs1.left + next.left_shift[last1.left] )
-
+
else
-- both trees have the same height
end
@@ -398,11 +398,11 @@ function Skambath2016:run()
local childgroups = Storage.new()
local phases = self.digraph.options.algorithm_phases
-
+
local so_class = phases['supergraph optimization']
local ga_class = phases['evolving graph animation']
local cr_class = phases['temporal cycle removal']
-
+
self.extended_version = self.digraph.options['missing nodes get space']
self.supergraph = Supergraph.generateSupergraph(self.digraph)
local supergraph_original = Supergraph.generateSupergraph(self.digraph)
@@ -414,8 +414,8 @@ function Skambath2016:run()
digraph = self.digraph,
ugraph = self.ugraph
}:run()
-
-
+
+
self:precomputeSpanningTrees()
-- Resolve cyclic dependencies if exists.
@@ -432,13 +432,13 @@ function Skambath2016:run()
self:computeHorizontalLayout(childgroups, descendants)
-- self:computeHorizontalLayoutFast()
-
- -- vertical positions
+
+ -- vertical positions
tlayered.arrange_layers_by_baselines(layers,
- self.adjusted_bb,
- self.ugraph,
- self.supergraph.snapshots,
- self.supergraph.vertex_snapshots)
+ self.adjusted_bb,
+ self.ugraph,
+ self.supergraph.snapshots,
+ self.supergraph.vertex_snapshots)
-- animate graph
ga_class.new {
@@ -446,11 +446,11 @@ function Skambath2016:run()
supergraph = supergraph_original,
digraph = self.digraph,
ugraph = self.ugraph
- }:run()
+ }:run()
end
--
--- Compute the required shift value for a second tree to guarantee
+-- Compute the required shift value for a second tree to garuantee
-- a required node distance.
-- @field right_borders The Border data structure for the right border of
-- the left tree
@@ -465,11 +465,11 @@ function Skambath2016:computeMinShift(right_borders, left_borders, selected_snap
local max_level = math.min(#right_borders, #left_borders)
local first_shift = 0
local snapshots = selected_snapshots or self.supergraph.snapshots
-
+
for layer = 1, max_level do
local rb, lb = right_borders[layer], left_borders[layer]
for _,s in ipairs(snapshots) do
-
+
local v1,v2 = rb[s],lb[s]
if v1 and v2 then
local local_shift = layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, v1, v2) + v1.pos.x - v2.pos.x
@@ -497,7 +497,7 @@ function Skambath2016:computeMinShift(right_borders, left_borders, selected_snap
if is_significant then
shift = shift + self.ugraph.options['significant sep']
end
-
+
return shift
end
@@ -521,20 +521,20 @@ function Skambath2016:computeHorizontalLayout(groups, descendants)
end
-- 1. Initialize Dependencies
-
+
for _, snapshot in ipairs(self.supergraph.snapshots) do
for _, spanning_tree in ipairs(snapshot.spanning_trees) do
for _, arc in ipairs(spanning_tree.arcs) do
-
- local head = self.supergraph:getSupervertex(arc.head)
- local tail = self.supergraph:getSupervertex(arc.tail)
-
- if(head and tail) then
- if not dependency_graph:arc(tail, head) then
- dependency_graph:connect(tail, head)
- dep_counter[tail] = dep_counter[tail] + 1
- end
- end
+
+ local head = self.supergraph:getSupervertex(arc.head)
+ local tail = self.supergraph:getSupervertex(arc.tail)
+
+ if(head and tail) then
+ if not dependency_graph:arc(tail, head) then
+ dependency_graph:connect(tail, head)
+ dep_counter[tail] = dep_counter[tail] + 1
+ end
+ end
end
end
end
@@ -546,19 +546,19 @@ function Skambath2016:computeHorizontalLayout(groups, descendants)
queue:enqueue(vertex, 1)
end
end
-
- -- 2.
+
+ -- 2.
while not queue:isEmpty() do
- local vertex = queue:dequeue()
+ local vertex = queue:dequeue()
local vertex_snapshots = self.supergraph:getSnapshots(vertex)
-
+
-- a. Resolve dependencies on this vertex:
local incomings = dependency_graph:incoming(vertex)
- for _, e in ipairs(incomings) do
+ for _, e in ipairs(incomings) do
dep_counter[e.tail] = dep_counter[e.tail] - 1
if dep_counter[e.tail] == 0 then
- queue:enqueue(e.tail, 1)
- end
+ queue:enqueue(e.tail, 1)
+ end
end
-- b. Compute borders of this supervertex:
@@ -569,63 +569,63 @@ function Skambath2016:computeHorizontalLayout(groups, descendants)
snapshot_vertex.pos.x = 0
snapshot_vertex.pos.y = 0
end
-
+
local vertex_groups = groups[vertex]
local last_pos_x = 0
if vertex_groups then
-- c. Compute borders of groups:
local all_group_borders = {}
for i, group in ipairs(vertex_groups) do
- local group_boders = Borders.new()
- for _,s in ipairs(vertex_snapshots) do
- local child = group[s]
- if child then
- local child_borders
- if not (child.kind == "dummy") then
- local superchild = self.supergraph:getSupervertex(child)
- child_borders = subtree_borders[superchild] or Borders.new()
- else
- child_borders = Borders.new()
- child_borders:addBoth(1, s, child)
- end
- assert(child.pos~=math.huge, "invalid child pos")
- shift_group(-child.pos.x,{[s]=child},{[1]=s}, descendants)
- Borders.copyBordersAtSnapshot(child_borders, group_boders, s)
- end
- end
- all_group_borders[i] = group_boders
+ local group_boders = Borders.new()
+ for _,s in ipairs(vertex_snapshots) do
+ local child = group[s]
+ if child then
+ local child_borders
+ if not (child.kind == "dummy") then
+ local superchild = self.supergraph:getSupervertex(child)
+ child_borders = subtree_borders[superchild] or Borders.new()
+ else
+ child_borders = Borders.new()
+ child_borders:addBoth(1, s, child)
+ end
+ assert(child.pos~=math.huge, "invalid child pos")
+ shift_group(-child.pos.x,{[s]=child},{[1]=s}, descendants)
+ Borders.copyBordersAtSnapshot(child_borders, group_boders, s)
+ end
+ end
+ all_group_borders[i] = group_boders
end
-
+
-- d. Place groups and merge borders of groups:
local last_group = nil
last_pos_x = 0
local merged_borders = Borders.new()
local final_borders = Borders.new()
for i, group in ipairs(vertex_groups) do
- local group_borders = all_group_borders[i]
- if last_group_borders then
- -- i. compute minimal shift
-
- local shift
- shift = self:computeMinShift(merged_borders.right, group_borders.left)
-
-
- assert(shift ~= math.huge and shift~=-math.huge, "invalid shift")
-
- -- ii. shift group
- local anchor = shift_group(shift, group,vertex_snapshots, descendants)
- last_pos_x = anchor
- end
- last_group_borders = group_borders
-
- -- iii. adapt borders
- adapt_borders(merged_borders,
- group_borders,
- self.supergraph.snapshots)
- adapt_borders(final_borders,
- group_borders,
- self.supergraph.snapshots,
- not self.extended_version)
+ local group_borders = all_group_borders[i]
+ if last_group_borders then
+ -- i. compute minimal shift
+
+ local shift
+ shift = self:computeMinShift(merged_borders.right, group_borders.left)
+
+
+ assert(shift ~= math.huge and shift~=-math.huge, "invalid shift")
+
+ -- ii. shift group
+ local anchor = shift_group(shift, group,vertex_snapshots, descendants)
+ last_pos_x = anchor
+ end
+ last_group_borders = group_borders
+
+ -- iii. adapt borders
+ adapt_borders(merged_borders,
+ group_borders,
+ self.supergraph.snapshots)
+ adapt_borders(final_borders,
+ group_borders,
+ self.supergraph.snapshots,
+ not self.extended_version)
end -- for (group)
vertex_borders:appendBelow(1, final_borders)
end
@@ -637,24 +637,24 @@ function Skambath2016:computeHorizontalLayout(groups, descendants)
local snapshot_vertex = self.supergraph:getSnapshotVertex(vertex, s)
snapshot_vertex.pos.x = x
end
-
- subtree_borders[vertex] = vertex_borders
+
+ subtree_borders[vertex] = vertex_borders
end
- -- align roots
+ -- align roots
for _, s in ipairs(self.supergraph.snapshots) do
local lastroot
- local rborder
+ local rborder
for i, spanning_tree in ipairs(s.spanning_trees) do
local root = spanning_tree.root
local rootborders = subtree_borders[self.supergraph:getSupervertex(root)]
shift_group(-root.pos.x,{[s]=root},{[1]=s}, descendants)
if i>1 then
- local l = subtree_borders[self.supergraph:getSupervertex(lastroot)]
- local r = rootborders
- shift = math.max(self:computeMinShift(l.right, r.left, {[1]=s}),
- self:computeMinShift(rborder.right,r.left, {[1]=s}))
- shift_group(shift,{[s]=root},{[1]=s}, descendants)
+ local l = subtree_borders[self.supergraph:getSupervertex(lastroot)]
+ local r = rootborders
+ shift = math.max(self:computeMinShift(l.right, r.left, {[1]=s}),
+ self:computeMinShift(rborder.right,r.left, {[1]=s}))
+ shift_group(shift,{[s]=root},{[1]=s}, descendants)
else
rborder = Borders.new()
end
@@ -684,28 +684,28 @@ function Skambath2016:computeHorizontalLayoutFast()
dependency_graph:add {vertex}
end
-
+
-- I. Initialize Dependencies (Build Dependency Graph)
for _, snapshot in ipairs(self.supergraph.snapshots) do
for _, spanning_tree in ipairs(snapshot.spanning_trees) do
table.insert(all_trees, spanning_tree)
shifts[spanning_tree] = Storage.new()
next[spanning_tree] = {left= Storage.new(),
- right= Storage.new(),
- left_shift = Storage.new(),
- right_shift = Storage.new()
+ right= Storage.new(),
+ left_shift = Storage.new(),
+ right_shift = Storage.new()
}
-
+
for _, arc in ipairs(spanning_tree.arcs) do
- local head = self.supergraph:getSupervertex(arc.head)
- local tail = self.supergraph:getSupervertex(arc.tail)
-
- if(head and tail) then
- if not dependency_graph:arc(tail, head) then
- dependency_graph:connect(tail, head)
- dep_counter[tail] = dep_counter[tail] + 1
- end
- end
+ local head = self.supergraph:getSupervertex(arc.head)
+ local tail = self.supergraph:getSupervertex(arc.tail)
+
+ if(head and tail) then
+ if not dependency_graph:arc(tail, head) then
+ dependency_graph:connect(tail, head)
+ dep_counter[tail] = dep_counter[tail] + 1
+ end
+ end
end
end
end
@@ -718,21 +718,21 @@ function Skambath2016:computeHorizontalLayoutFast()
queue:enqueue(vertex, 1)
end
end
-
+
while not queue:isEmpty() do
-- Next node in topological order
local vertex = queue:dequeue()
-- texio.write("\n\n --- "..vertex.name .. " ---")
--pgf.debug{next}
local vertex_snapshots = self.supergraph:getSnapshots(vertex)
-
+
-- a. Resolve dependencies on this vertex:
local incomings = dependency_graph:incoming(vertex)
- for _, e in ipairs(incomings) do
+ for _, e in ipairs(incomings) do
dep_counter[e.tail] = dep_counter[e.tail] - 1
if dep_counter[e.tail] == 0 then
- queue:enqueue(e.tail, 1)
- end
+ queue:enqueue(e.tail, 1)
+ end
end
-- b. Compute maximum number of children over time:
@@ -743,7 +743,7 @@ function Skambath2016:computeHorizontalLayoutFast()
num_children = math.max(num_children, #(tree:outgoing(v)))
shifts[tree][v] = 0
end
-
+
-- c. Shift all subtrees in all snapshots:
local hlp_ptr = Storage.new()
local max_shift = 0
@@ -751,27 +751,27 @@ function Skambath2016:computeHorizontalLayoutFast()
-- i) Compute the necessary shift between the i-th and (i+1)-th subtrees (per snapshot):
local min_shift = 0
for t, s in ipairs(vertex_snapshots) do
- local snapshot_vertex = self.supergraph:getSnapshotVertex(vertex, s)
- local tree = s.spanning_trees[1]
- local req_shift, hptr
- req_shift, hptr = self:computeRequiredDistance(tree,
- snapshot_vertex,
- i,
- shifts[tree],
- next[tree]
- )
- hlp_ptr[t] = hptr
--- texio.write(" -> \t"..req_shift)
- min_shift = math.max(min_shift, req_shift)
+ local snapshot_vertex = self.supergraph:getSnapshotVertex(vertex, s)
+ local tree = s.spanning_trees[1]
+ local req_shift, hptr
+ req_shift, hptr = self:computeRequiredDistance(tree,
+ snapshot_vertex,
+ i,
+ shifts[tree],
+ next[tree]
+ )
+ hlp_ptr[t] = hptr
+-- texio.write(" -> \t"..req_shift)
+ min_shift = math.max(min_shift, req_shift)
end
-- texio.write("\n \t\t".. min_shift )
-
- -- ii) Synchronize distance between neighbored subtrees and apply shifts
+
+ -- ii) Synchronize distance between neigbored subtrees and apply shifts
for t, s in ipairs(vertex_snapshots) do
- local snapshot_vertex = self.supergraph:getSnapshotVertex(vertex, s)
- local tree = s.spanning_trees[1]
- apply_shift(tree, snapshot_vertex, i, shifts[tree], next[tree], hlp_ptr[t], min_shift)
+ local snapshot_vertex = self.supergraph:getSnapshotVertex(vertex, s)
+ local tree = s.spanning_trees[1]
+ apply_shift(tree, snapshot_vertex, i, shifts[tree], next[tree], hlp_ptr[t], min_shift)
end
max_shift = min_shift
@@ -781,22 +781,22 @@ function Skambath2016:computeHorizontalLayoutFast()
local snapshot_vertex = self.supergraph:getSnapshotVertex(vertex, s)
local tree = s.spanning_trees[1]
local outgoings = tree:outgoing(snapshot_vertex)
-
+
-- next[tree].left[snapshot_vertex] = outgoings[1].head
for i = 1,#outgoings do
- if i==1 then
- next[tree].left_shift[snapshot_vertex] = - max_shift / 2
- next[tree].left[snapshot_vertex]= outgoings[i].head
- end
- shifts[tree][outgoings[i].head] = shifts[tree][outgoings[i].head] - max_shift / 2
- next[tree].right[snapshot_vertex] = outgoings[i].head
- next[tree].right_shift[snapshot_vertex] = shifts[tree][outgoings[i].head]
+ if i==1 then
+ next[tree].left_shift[snapshot_vertex] = - max_shift / 2
+ next[tree].left[snapshot_vertex]= outgoings[i].head
+ end
+ shifts[tree][outgoings[i].head] = shifts[tree][outgoings[i].head] - max_shift / 2
+ next[tree].right[snapshot_vertex] = outgoings[i].head
+ next[tree].right_shift[snapshot_vertex] = shifts[tree][outgoings[i].head]
end
-
+
end
-
+
end -- end while (all vertices have been processed)
-- III. Accumulate absolute horizontal coordinates
@@ -832,7 +832,7 @@ end
--
---
+--
--
function Skambath2016:precomputeChildgroups(childgroups)
for _,s in ipairs(self.supergraph.snapshots) do
@@ -849,8 +849,8 @@ end
--
function Skambath2016:precomputeSpanningTrees()
local events = assert(self.scope.events,
- "no events found for the spanning tree computation")
-
+ "no events found for the spanning tree computation")
+
for i, s in ipairs(self.supergraph.snapshots) do
-- The involved snapshot graph:
local s_copy = Digraph.new(s)
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua
index 99e79919b54..490b8b3191d 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Supergraph.lua
@@ -27,12 +27,12 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
-- and if there is a single snapshot in which two vertices are
-- connected by an edge they are connected in the supergraph.
--
--- Note that in \tikzname\ a \emph{node} is more than a single dot. A node
+-- Note that in TikZ a \emph{node} is more than a single dot. A node
-- has a content and different properties like background-color or a
--- shape. Formally this can be modeled by function mapping vertices
+-- shape. Formally this can be modelled by function mapping vertices
-- to their properties. For evolving graphs this could be done in the
--- same way. As this is difficult to be realized in PGF because there
--- is no basic support for time dependent properties on nodes, each
+-- same way. As this is difficult to be realised in PGF because there
+-- is no basic support for time dependend properties on nodes, each
-- vertex will be displayed over time by different single
-- (snapshot-)nodes which can have different visual properties. This
-- means for a vertex which we call |supervertex| in the following we
@@ -53,7 +53,7 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
-- @field supervertices_by_id This storage maps a node identifier to the
-- related supervertex such that PGF-nodes which belonging to
-- the same superverticex can be identified
---
+--
-- @field snapshots An array of all snapshots. Sorted in ascending order
-- over the timestamps of the snapshots.
--
@@ -64,7 +64,6 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
-- Assume we want to iterate over all snapshots
-- for a certain pair of supernodes in which they are connected
-- by an arc. The arc_snapshots storage helps in this case:
--- %
-- \begin{codeexample}[code only, tikz syntax=false]
-- local supergraph = Supergraph.generateSupergraph(self.digraph)
-- local u = supergraph.vertices[1]
@@ -111,24 +110,24 @@ local get_snapshot
--
-- @param snapshots An array of all existing snapshots
-- @param timestamps A table which maps known timestamps to their
--- related snapshots
+-- related snapshots
-- @param ugraph The ugraph of the underlying graph structure
-- @param snapshot_time
--
-- @return The snapshot instance found in the snapshots array for the
--- wanted timestamp snapshot_time if it doesn't exists a new snapshot
--- will be generated and added to the arrays
+-- wanted timestamp snapshot_time if it does'nt exists a new snapshot
+-- will be generated and added to the arrays
--
function get_snapshot(snapshots, timestamps, ugraph, snapshot_time)
local snapshot
local snapshot_idx = timestamps[snapshot_time]
-
+
if not snapshot_idx then
-- store snapshot if it doesn't exists
- snapshot_idx = timestamps.n + 1
+ snapshot_idx = timestamps.n + 1
timestamps[snapshot_time] = snapshot_idx
timestamps.n = timestamps.n + 1
- snapshot = Digraph.new {
+ snapshot = Digraph.new {
syntactic_digraph = ugraph.syntactic_digraph,
options = ugraph.options
}
@@ -137,7 +136,7 @@ function get_snapshot(snapshots, timestamps, ugraph, snapshot_time)
else
snapshot = snapshots[snapshot_idx]
end
- assert(snapshot~=nil, "an unexpected error occurred")
+ assert(snapshot~=nil, "an unexpected error occured")
return snapshot
end
@@ -153,7 +152,7 @@ end
--
-- @return The supergraph which is a |Digraph| that has a supervertex
-- for each set of snapshot-vertices with the same |supernode|
--- attribute.
+-- attribute.
--
function Supergraph.generateSupergraph(digraph)
local new_supergraph
@@ -162,35 +161,35 @@ function Supergraph.generateSupergraph(digraph)
options = digraph.options,
digraph = digraph,
}
-
- -- array to store the supervertices for a given vertex name
+
+ -- array to store the supervertices for a given vertex name
local local_snapshots = {} -- array to store each snapshot graphs
-
+
local timestamps = { n = 0 } -- set of snapshot times
- -- separate and assign vertices to their snapshots and supervertices
+ -- separate and assign vertices to their snapshots and supervertives
for i,vertex in ipairs(digraph.vertices) do
local snapshot_time = assert(vertex.options["snapshot"], "Missing option 'snapshot' for vertex ".. vertex.name ..". ")
local supernode_name = assert(vertex.options["supernode"], "Missing option 'supernode' for vertex"..vertex.name..". ")
-
+
local snapshot = get_snapshot(local_snapshots, timestamps, digraph, snapshot_time)
local supervertex = new_supergraph.supervertices_by_id[supernode_name]
-
+
if not supervertex then
- -- first appearance of the supernode id
- supervertex = Vertex.new {
- kind = "super",
- name = supernode_name
+ -- first appeareance of the supernode id
+ supervertex = Vertex.new {
+ kind = "super",
+ name = supernode_name
}
supervertex.snapshots = {}
supervertex.subvertex = {}
- new_supergraph.supervertices_by_id[supernode_name] = supervertex
+ new_supergraph.supervertices_by_id[supernode_name] = supervertex
new_supergraph:add{supervertex}
supervertex.options = {}
supervertex.options = vertex.options
- end
-
+ end
+
snapshot:add{vertex}
new_supergraph.supervertices[vertex] = supervertex
@@ -199,11 +198,11 @@ function Supergraph.generateSupergraph(digraph)
end
-- Create edges
- for i, e in ipairs(digraph.arcs) do
+ for i, e in ipairs(digraph.arcs) do
local u,v = e.tail, e.head
local snapshot_tail = new_supergraph.vertex_snapshots[e.tail]
local snapshot_head = new_supergraph.vertex_snapshots[e.head]
-
+
assert(snapshot_head == snapshot_tail, "Arcs must connect nodes that exist at the same time.")
-- connect in the snapshot graph
@@ -212,18 +211,18 @@ function Supergraph.generateSupergraph(digraph)
-- connect in the supergraph:
local super_tail = new_supergraph.supervertices[u]
local super_head = new_supergraph.supervertices[v]
-
+
new_supergraph:assignToSuperarc(super_tail, super_head, snapshot_tail)
end
-
+
-- snapshots in temporal order
- table.sort(local_snapshots,
+ table.sort(local_snapshots,
function(s1,s2)
return s1.timestamp < s2.timestamp
end )
-
- local previous_snapshot
-
+
+ local previous_snapshot
+
for i,s in ipairs(local_snapshots) do
local start = -math.huge
if previous_snapshot then
@@ -236,18 +235,18 @@ function Supergraph.generateSupergraph(digraph)
new_supergraph.snapshots = local_snapshots
new_supergraph.snapshots_indices = Storage.new()
-
+
for i, s in ipairs(new_supergraph.snapshots) do
new_supergraph.snapshots_indices[s] = i
end
-
+
return new_supergraph
end
function Supergraph:getSnapshotStaticDuration(snapshot)
assert(snapshot, "a snapshot as parameter expected, but got nil")
- local idur = snapshot.interval.to - snapshot.interval.from
+ local idur = snapshot.interval.to - snapshot.interval.from
assert(idur, "unexpected nil-value")
local d1 = snapshot.interval.to - snapshot.timestamp
local d2 = snapshot.timestamp - snapshot.interval.from
@@ -273,9 +272,9 @@ function Supergraph:getDuration()
end
---
---
+--
-- @return The ratio of the time of a snapshot related to the global duration of the whole
--- evolving trees. (The time between the last and first snapshot)
+-- evlolving trees. (The time between the last and first snapshot)
function Supergraph:getSnapshotRelativeDuration(snapshot)
if self:getDuration() == 0 then
return 1
@@ -295,7 +294,7 @@ end
function Supergraph:getSupervertex(vertex)
assert(vertex, "vertex required")
assert(self.supervertices, "supervertex table is not defined")
- return self.supervertices[vertex]
+ return self.supervertices[vertex]
end
function Supergraph:getSuperarc(arc)
@@ -323,7 +322,7 @@ end
---
-- For a given supervertex get the related vertex for a snapshot
--
--- @param supervertex
+-- @param supervertex
--
-- @param snapshot
--
@@ -341,7 +340,7 @@ function Supergraph:consecutiveSnapshots(snapshot1, snapshot2, n)
local idx1 = self.snapshots_indices[snapshot1] --or -1
local idx2 = self.snapshots_indices[snapshot2] --or -1
local d = n or 1
-
+
return (idx2-idx1 <= d) or (idx1-idx2 <= d)
end
@@ -359,21 +358,21 @@ end
-- their positions from the supergraph.
--
function Supergraph:sharePositions(ugraph, ignore)
-
+
for _,vertex in ipairs(ugraph.vertices) do
if not ignore then
vertex.pos.x = self.supervertices[vertex].pos.x
vertex.pos.y = self.supervertices[vertex].pos.y
else
if not ignore.x then
- vertex.pos.x = self.supervertices[vertex].pos.x
+ vertex.pos.x = self.supervertices[vertex].pos.x
end
if not ignore.y then
- vertex.pos.y = self.supervertices[vertex].pos.y
+ vertex.pos.y = self.supervertices[vertex].pos.y
end
end
-
-
+
+
end
end
@@ -381,7 +380,7 @@ function Supergraph:onAllSnapshotvertices(f, ugraph)
for _,vertex in ipairs(ugraph.vertices) do
local snapshot_vertex = self.supertvertices[vertex]
if snapshot_vertex then
- f(vertex, snapshot_vertex)
+ f(vertex, snapshot_vertex)
end
end
end
@@ -395,23 +394,23 @@ end
-- the original vertex.
-- If a supervertex has no subvertices then it will not be added to the graph.
--
--- @param supervertex The supervertex which should be split.
+-- @param supervertex The supervertex which should be splitted.
--
-- @param snapshots An array of snapshots at which the supervertex
--- should be split into a new one with the corresponding pgf-vertices.
+-- should be splitted into a new one with the corresponding pgf-vertices.
-- If there are more than one snapshots passed to the function
-- for each snapshot there will be a new pseudo-vertex
--
function Supergraph:splitSupervertex(supervertex, snapshots)
assert(supervertex, "no supervertex defined")
-- snapshots in temporal order
- table.sort(snapshots,
+ table.sort(snapshots,
function(s1,s2)
return s1.timestamp < s2.timestamp
end )
assert(#snapshots~=0)
-
+
local edit_snapshots = supervertex.snapshots
local first_removed = math.huge
local rem_arcs = {}
@@ -438,42 +437,42 @@ function Supergraph:splitSupervertex(supervertex, snapshots)
local s = self.snapshots[j]
local vertex = self:getSnapshotVertex(supervertex, s)
if vertex then
- self.supervertices[vertex] = pseudovertex
- self:addSnapshotVertex(pseudovertex, s, vertex)
- self:removeSnapshotVertex(supervertex, s)
-
- if not has_subvertices then
- has_subvertices = true
- self:add{pseudovertex}
- end
-
- -- update edges:
- local incoming = self.digraph:incoming(vertex)
- local outgoing = self.digraph:outgoing(vertex)
-
- for _, arc in ipairs(incoming) do
- local tail = self.supervertices[arc.tail]
- local head = self.supervertices[arc.head]
- self:assignToSuperarc(tail, pseudovertex, s)
-
- local super_arc = self:arc(tail, supervertex)
- if not rem_arcs[super_arc] then
- table.insert(rem_arcs, {arc = super_arc, snapshot = s})
- rem_arcs[super_arc] = true
- end
- end
-
- for _, arc in ipairs(outgoing) do
- local tail = self.supervertices[arc.tail]
- local head = self.supervertices[arc.head]
- self:assignToSuperarc(pseudovertex, head, s)
-
- local super_arc = self:arc(supervertex, head)
- if not rem_arcs[super_arc] then
- table.insert(rem_arcs, {arc = super_arc, snapshot = s})
- rem_arcs[super_arc] = true
- end
- end
+ self.supervertices[vertex] = pseudovertex
+ self:addSnapshotVertex(pseudovertex, s, vertex)
+ self:removeSnapshotVertex(supervertex, s)
+
+ if not has_subvertices then
+ has_subvertices = true
+ self:add{pseudovertex}
+ end
+
+ -- update edges:
+ local incoming = self.digraph:incoming(vertex)
+ local outgoing = self.digraph:outgoing(vertex)
+
+ for _, arc in ipairs(incoming) do
+ local tail = self.supervertices[arc.tail]
+ local head = self.supervertices[arc.head]
+ self:assignToSuperarc(tail, pseudovertex, s)
+
+ local super_arc = self:arc(tail, supervertex)
+ if not rem_arcs[super_arc] then
+ table.insert(rem_arcs, {arc = super_arc, snapshot = s})
+ rem_arcs[super_arc] = true
+ end
+ end
+
+ for _, arc in ipairs(outgoing) do
+ local tail = self.supervertices[arc.tail]
+ local head = self.supervertices[arc.head]
+ self:assignToSuperarc(pseudovertex, head, s)
+
+ local super_arc = self:arc(supervertex, head)
+ if not rem_arcs[super_arc] then
+ table.insert(rem_arcs, {arc = super_arc, snapshot = s})
+ rem_arcs[super_arc] = true
+ end
+ end
end
end
end
@@ -482,14 +481,14 @@ function Supergraph:splitSupervertex(supervertex, snapshots)
for _, removed_arc in ipairs(rem_arcs) do
local snapshots = self.arc_snapshots[removed_arc.arc]
for i=#snapshots,1,-1 do
- local s = snapshots[i]
- if s.timestamp >= removed_arc.snapshot.timestamp then
- table.remove(snapshots, i)
- end
+ local s = snapshots[i]
+ if s.timestamp >= removed_arc.snapshot.timestamp then
+ table.remove(snapshots, i)
+ end
end
if #snapshots==0 then
- self:disconnect(removed_arc.arc.tail, removed_arc.arc.head)
+ self:disconnect(removed_arc.arc.tail, removed_arc.arc.head)
end
end
end
@@ -554,16 +553,16 @@ end
--
function Supergraph:assignToSuperarc(super_tail, super_head, snapshot)
assert(self:contains(super_tail) and self:contains(super_head),
- "tried to connect supernodes not in the supergraph")
-
+ "tried to connect supernodes not in the supergraph")
+
local super_arc = self:arc(super_tail, super_head)
if not super_arc then
- super_arc = self:connect(super_tail, super_head)
+ super_arc = self:connect(super_tail, super_head)
end
-
+
table.insert(self.arc_snapshots[super_arc], snapshot)
self.arc_snapshots[super_arc][snapshot] = true
-
+
return super_arc
end
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua
index b5a4ea22c94..2295e60513b 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua
@@ -59,19 +59,19 @@ declare {
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.
+ 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
+ documentation = [["
+ See ToDo
"]]
}
--- Help functions
+-- Helpfunctions
-- Implementation
@@ -84,102 +84,102 @@ function SupergraphVertexSplitOptimization:run()
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)
+ 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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/TimeSpec.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/TimeSpec.lua
index 2b2168da1aa..13d453f1fd6 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/TimeSpec.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/TimeSpec.lua
@@ -14,49 +14,47 @@ local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
---
declare {
- key = "snapshot",
- type = "time",
- initial = "0s",
- summary = "The time of the snapshot in which a PGF node should be visible.",
- documentation = [["
- This option defines the time in seconds when respectively in which
- state or snapshot of the graph the PGF represents a graph node.
- "]],
+ key = "snapshot",
+ type = "time",
+ initial = "0s",
+ summary = "The time of the snapshot in which a PGF node should be visible.",
+ documentation = [["
+ This option defines the time in seconds when respectively in which
+ state or snapshot of the graph the PGF represents a graph node.
+"]]
}
---
declare {
- key = "supernode",
- type = "string",
- initial = "null",
- summary = "A unique name for a node a given PGF node should be assigned to.",
- documentation = [["
- Because it should be possible that nodes can change their
- appearance, they are represented by separate PGF nodes in each
- snapshot. To identify PGF nodes of the same supernode we have to
- specify this key.
- "]],
+ key = "supernode",
+ type = "string",
+ initial = "null",
+ summary = "A unique name for a node a given PGF node should be assigned to.",
+ documentation = [["
+ Because it should be possible that nodes can change their
+ appearance, they are represented by separate PGF nodes in each
+ snapshot. To identify PGF nodes of the same supernode we have to
+ specify this key.
+"]]
}
---
declare {
- key = "fadein time",
- type = "time",
- initial = "0.5s",
- summary = [["
- The time in seconds it should take that a nodes will be fade in
- when it disappears in the graph.
- "]],
+ key = "fadein time",
+ type = "time",
+ initial = "0.5s",
+ summary = [["The time in seconds it should take that a nodes will be fade in
+ when it disappears in the graph"]],
}
---
declare {
- key = "fadeout time",
- type = "time",
- initial = "0.5s",
- summary = "",
- documentation = "The same as |fadein time| but for disappearing nodes.",
+ key = "fadeout time",
+ type = "time",
+ initial = "0.5s",
+ summary = "",
+ documentation = "The same as |fadein time| but for disappearing nodes."
}
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/doc.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/doc.lua
index dbd81462758..801e3808bb4 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/doc.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/doc.lua
@@ -26,27 +26,26 @@ documentation
A method to create layouts for evolving graphs as an SVG animation.The Reingold--Tilford method is a standard method for drawing
trees. It is described in:
-The algorithm, which is based on the Reingold--Tilford algorithm and
+The algorithm, which is based on the Reingold--Tilford algorithm and
its implementation in |graphdrawing.trees|, is introduced in my Masthesis:
-%
\begin{itemize}
- \item
- M.\ Skambath,
- \newblock Algorithmic Drawing of Evolving Trees, Masterthesis, 2016
+\item
+ M.\ Skambath,
+ \newblock Algorithmic Drawing of Evolving Trees, Masterthesis, 2016
\end{itemize}
-You can use the same known graph macros as for other graph drawing
-algorithms in Ti\emph{k}Z. In addition all keys and features that
+You can use the same known graph macros as for other graph drawing
+algorithms in Ti\emph{k}Z. In addition all keys and features that
are available for the static tree algorithm can be used:
-%
+
\begin{codeexample}[animation list={1,1.5,2,2.5,3,3.5,4}]
\tikz \graph[animated binary tree layout,
nodes={draw,circle}, auto supernode,
- ] {
- {[when=1] 15 -> {10 -> { ,11}, 20 }},
- {[when=2] 15 -> {10 -> {3,11}, 20 }},
- {[when=3] 15 -> {10 -> {3, }, 20 }},
- {[when=4] 15 -> {10 -> {3, }, 20 -> 18 }},
+ ] {
+ {[when=1] 15 -> {10 -> { ,11}, 20 }},
+ {[when=2] 15 -> {10 -> {3,11}, 20 }},
+ {[when=3] 15 -> {10 -> {3, }, 20 }},
+ {[when=4] 15 -> {10 -> {3, }, 20 -> 18 }},
};
\end{codeexample}
]]
@@ -55,11 +54,11 @@ are available for the static tree algorithm can be used:
example
[[
\tikz[animated binary tree layout]
- \graph[nodes={draw,circle}, auto supernode] {
- {[when=1] 15 -> {10 -> { ,11}, 20 }},
- {[when=2] 15 -> {10 -> {3,11}, 20 }},
- {[when=3] 15 -> {10 -> {3, }, 20 }},
- {[when=4] 15 -> {10 -> {3, }, 20 -> 18 }},
+ \graph[nodes={draw,circle}, auto supernode] {
+ {[when=1] 15 -> {10 -> { ,11}, 20 }},
+ {[when=2] 15 -> {10 -> {3,11}, 20 }},
+ {[when=3] 15 -> {10 -> {3, }, 20 }},
+ {[when=4] 15 -> {10 -> {3, }, 20 -> 18 }},
};
]]
--------------------------------------------------------------------
@@ -77,17 +76,15 @@ key "animated binary tree layout"
summary
[[ A layout based on the Reingold--Tilford method for drawing
-binary trees.
-]]
+binary trees. ]]
documentation
[[
This key executes:
-%
\begin{enumerate}
- \item |animated tree layout|, thereby selecting the Reingold--Tilford method,
- \item |minimum number of children=2|, thereby ensuring the all nodes
- have (at least) two children or none at all, and
+\item |animated tree layout|, thereby selecting the Reingold--Tilford method,
+\item |minimum number of children=2|, thereby ensuring the all nodes
+ have (at least) two children or none at all, and
\end{enumerate}
]]
@@ -102,15 +99,14 @@ example
--------------------------------------------------------------------
-
+
--------------------------------------------------------------------
key "extended animated binary tree layout"
summary
[[ This algorithm is similar to |animated binary tree layout|, only the
option \texttt{missing nodes get space} is executed and the
-\texttt{significant sep} is zero.
-]]
+\texttt{significant sep} is zero. ]]
example
[[
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/layered.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/layered.lua
index 15df9990f8e..dc1e8ab571c 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/layered.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/layered.lua
@@ -23,7 +23,7 @@ local lib = require "pgf.gd.lib"
local Storage = require "pgf.gd.lib.Storage"
local layered = require "pgf.gd.layered"
---
+--
-- This file defines some basic functions to compute and/or set the
-- ideal distances between nodes of any kind of layered drawing of a
-- graph.
@@ -35,7 +35,7 @@ local layered = require "pgf.gd.layered"
--
-- @param layers A |Storage| object assigning layers to vertices.
-- @param paddings A |Storage| object storing the computed distances
--- (paddings).
+-- (paddings).
-- @param graph The graph in which the nodes reside
-- @param snapshots The list of snapshots over which the overlaying evolving
-- graph exists
@@ -56,47 +56,47 @@ function temporallayered.arrange_layers_by_baselines (layers, paddings, graph, s
end
if count_layers > 0 then
-
-
+
+
-- Now compute ideal distances and store
local height = 0
-
+
for _, s in ipairs(snapshots) do
local layer_vertices = snapshots_layers[s]
if #layer_vertices > 0 then -- sanity check
- for _,v in ipairs(layer_vertices[1]) do
- v.pos.y = 0
- end
+ for _,v in ipairs(layer_vertices[1]) do
+ v.pos.y = 0
+ end
end
end
-
+
for i=2, count_layers do
local distance = 0
for _, s in ipairs(snapshots) do
- local layer_vertices = snapshots_layers[s]
- if #layer_vertices >= i then
- distance = math.max(
- distance,
- layered.baseline_distance(
- paddings,
- s,
- layer_vertices[i-1],
- layer_vertices[i]))
- end
+ local layer_vertices = snapshots_layers[s]
+ if #layer_vertices >= i then
+ distance = math.max(
+ distance,
+ layered.baseline_distance(
+ paddings,
+ s,
+ layer_vertices[i-1],
+ layer_vertices[i]))
+ end
end
-
+
height = height + distance
-
+
for _, s in ipairs(snapshots) do
- local layer_vertices = snapshots_layers[s]
- if #layer_vertices >= i then
- for _,v in ipairs(layer_vertices[i]) do
- v.pos.y = height
- end
- end
+ local layer_vertices = snapshots_layers[s]
+ if #layer_vertices >= i then
+ for _,v in ipairs(layer_vertices[i]) do
+ v.pos.y = height
+ end
+ end
end
end
- end
+ end
end