From 22536bb2b5257046d271b1eaa11b4a275d5ec041 Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Sat, 5 Jan 2019 22:40:38 +0000 Subject: pgf (5jan19) git-svn-id: svn://tug.org/texlive/trunk@49607 c570f23f-e606-0410-a88d-b1316a301751 --- .../evolving/SupergraphVertexSplitOptimization.lua | 196 +++++++++++++++++++++ 1 file changed, 196 insertions(+) create mode 100644 Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua') 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 new file mode 100644 index 00000000000..2295e60513b --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua @@ -0,0 +1,196 @@ +-- Copyright 2015 by Malte Skambath +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + + +local SupergraphVertexSplitOptimization = {} + +-- Imports +local lib = require "pgf.gd.lib" +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare + +local Vertex = require "pgf.gd.model.Vertex" +local Digraph = require "pgf.gd.model.Digraph" +local Coordinate = require "pgf.gd.model.Coordinate" + +declare { + key = "split me", + type = "boolean", + initial = false +} + +declare { + key = "split on disappearing", + type = "boolean", + initial = true +} + +declare { + key = "split on disjoint neighbors", + type = "boolean", + initial = false +} + +declare { + key = "split on disjoint children", + type = "boolean", + initial = false +} + +declare { + key = "split on disjoint parents", + type = "boolean", + initial = false +} + +declare { + key = "split all supervertices", + type = "boolean", + initial = false +} + +declare { + key = "unbound vertex splitting", + algorithm = SupergraphVertexSplitOptimization, + phase = "supergraph optimization", + phase_default = true, + summary = [[" + Use this key if you want to disable animations. + Instead of producing animations the evolving graph animation phasephase animates all vertices including movements and + fade in or fade out animations. + "]], + documentation = [[" + See ToDo + "]] +} + + + +-- Helpfunctions + + +-- Implementation + +function SupergraphVertexSplitOptimization:run() + local supergraph = assert(self.supergraph, "no supergraph passed") + + local split_on_dissapearing = self.digraph.options["split on disappearing"] + local split_on_no_common_neighbor = self.digraph.options["split on disjoint neighbors"] + local split_on_no_common_child = self.digraph.options["split on disjoint children"] + local split_on_no_common_parent = self.digraph.options["split on disjoint parents"] + local split_all = self.digraph.options["split all supervertices"] + + for _, supernode in ipairs(supergraph.vertices) do + -- follow trace of the supernode + local snapshots = supergraph:getSnapshots(supernode) + local splitsnapshots = {} + + for i=2, #snapshots do + local s = snapshots[i] + local s_prev = snapshots[i - 1] + local can_split = false + + if supergraph:consecutiveSnapshots(s_prev, s) then + local v1 = supergraph:getSnapshotVertex(supernode, s_prev) + local v2 = supergraph:getSnapshotVertex(supernode, s) + local is_child1 = {} + local is_parent1 = {} + local is_neighbor1 = {} + + local incoming1 = s_prev:incoming(v1) + local outgoing1 = s_prev:outgoing(v1) + + for _,e in ipairs(incoming1) do + local p = supergraph:getSupervertex(e.tail) + if p then + is_parent1[p] = true + is_neighbor1[p] = true + end + end + + for _,e in ipairs(outgoing1) do + local p = supergraph:getSupervertex(e.head) + if p then + is_child1[p] = true + is_neighbor1[p] = true + end + end + + local incoming2 = s:incoming(v2) + local outgoing2 = s:outgoing(v2) + + no_common_parent = true + no_common_child = true + no_common_neighbor = true + for _,e in ipairs(incoming2) do + local p = supergraph:getSupervertex(e.tail) + if p then + if is_neighbor1[p] then + no_common_neighbor = false + end + if is_parent1[p] then + no_common_parent = false + end + if (not no_common_neighbor) and (not no_common_parent) then + break + end + end + end + + for _,e in ipairs(outgoing2) do + local p = supergraph:getSupervertex(e.head) + if p then + if is_neighbor1[p] then + no_common_neighbor = false + end + if is_child1[p] then + no_common_child = false + end + if (not no_common_neighbor) and (not no_common_child) then + break + end + end + end + + + + if no_common_neighbor and split_on_no_common_neighbor then + can_split = true + --texio.write("[N@".. s.timestamp .."]") + end + if no_common_parent and split_on_no_common_parent then + can_split = true + --texio.write("[P@".. s.timestamp .."]") + end + if no_common_child and split_on_no_common_child then + can_split = true + --texio.write("[N@".. s.timestamp .."]") + end + if v2.options["split me"] then + can_split = true + end + else + can_split = true + --texio.write("[R@".. s.timestamp .."]") + end + if can_split or split_all then + table.insert(splitsnapshots, s) + end + end + if #splitsnapshots>0 then + supergraph:splitSupervertex(supernode, splitsnapshots) + end + end +end + + + + +-- Done + +return SupergraphVertexSplitOptimization -- cgit v1.2.3