summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/experimental/evolving/SupergraphVertexSplitOptimization.lua
blob: 2295e60513b465d573ab47f499b170734ccb87f3 (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
  "]]
}



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