summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua
blob: b5a4ea22c94d64832e200c98c38be84bb5552920 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
-- Copyright 2015 by Malte Skambath
--
-- This file may be distributed an/or modified
--
-- 1. under the LaTeX Project Public License and/or
-- 2. under the GNU Public License
--
-- See the file doc/generic/pgf/licenses/LICENSE for more information


local SupergraphVertexSplitOptimization = {}

-- Imports
local lib        = require "pgf.gd.lib"
local declare    = require("pgf.gd.interface.InterfaceToAlgorithms").declare

local Vertex     = require "pgf.gd.model.Vertex"
local Digraph    = require "pgf.gd.model.Digraph"
local Coordinate = require "pgf.gd.model.Coordinate"

declare {
  key     = "split me",
  type    = "boolean",
  initial = false
}

declare {
  key     = "split on disappearing",
  type    = "boolean",
  initial = true
}

declare {
  key     = "split on disjoint neighbors",
  type    = "boolean",
  initial = false
}

declare {
  key     = "split on disjoint children",
  type    = "boolean",
  initial = false
}

declare {
  key     = "split on disjoint parents",
  type    = "boolean",
  initial = false
}

declare {
  key     = "split all supervertices",
  type    = "boolean",
  initial = false
}

declare {
  key       = "unbound vertex splitting",
  algorithm = SupergraphVertexSplitOptimization,
  phase     = "supergraph optimization",
  phase_default = true,
  summary = [["
    Use this key if you want to disable animations.
    Instead of producing animations the evolving graph animation phasephase animates all vertices including movements and
    fade in or fade out animations.
  "]],
  documentation = [["
    See ToDo
  "]]
}



-- Help functions


-- 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