diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Skambath2016.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/Skambath2016.lua | 362 |
1 files changed, 181 insertions, 181 deletions
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 23bbdf36a8c..2beec1e216e 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 { --- Helpfunctions +-- Help functions --- -- 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 respectivly on the right. +-- are on the outer places. On the left or respectively 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 snapshat already defined") + "border for a given snapshot 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 finit length") + "shift must be a valid finite 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 spanneng tree |tree| of a snapshot and sort --- the child nodes into groups. A group summarises for a given parent +-- Traverse through the spanning tree |tree| of a snapshot and sort +-- the child nodes into groups. A group summarizes 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 vertice's position should be +-- @param tree the tree in which the vertex'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 garuantee +-- Compute the required shift value for a second tree to guarantee -- 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 neigbored subtrees and apply shifts + + -- ii) Synchronize distance between neighbored 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) |