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
|
-- Copyright 2011 by Jannis Pohlmann
--
-- This file may be distributed and/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
-- @release $Header$
local NodeRankingGansnerKNV1993 = {}
-- Imports
local Edge = require "pgf.gd.deprecated.Edge"
local Node = require "pgf.gd.deprecated.Node"
local NetworkSimplex = require "pgf.gd.layered.NetworkSimplex"
function NodeRankingGansnerKNV1993:run()
local simplex = NetworkSimplex.new(self.graph, NetworkSimplex.BALANCE_TOP_BOTTOM)
simplex:run()
self.ranking = simplex.ranking
return simplex.ranking
end
function NodeRankingGansnerKNV1993:mergeClusters()
self.cluster_nodes = {}
self.cluster_node = {}
self.cluster_edges = {}
self.original_nodes = {}
self.original_edges = {}
for _,cluster in ipairs(self.graph.clusters) do
local cluster_node = Node.new{
name = 'cluster@' .. cluster.name,
}
table.insert(self.cluster_nodes, cluster_node)
for _,node in ipairs(cluster.nodes) do
self.cluster_node[node] = cluster_node
table.insert(self.original_nodes, node)
end
self.graph:addNode(cluster_node)
end
for _,edge in ipairs(self.graph.edges) do
local tail = edge:getTail()
local head = edge:getHead()
if self.cluster_node[tail] or self.cluster_node[head] then
table.insert(self.original_edges, edge)
local cluster_edge = Edge.new{
direction = Edge.RIGHT,
weight = edge.weight,
minimum_levels = edge.minimum_levels,
}
table.insert(self.cluster_edges, cluster_edge)
if self.cluster_node[tail] then
cluster_edge:addNode(self.cluster_node[tail])
else
cluster_edge:addNode(tail)
end
if self.cluster_node[head] then
cluster_edge:addNode(self.cluster_node[head])
else
cluster_edge:addNode(head)
end
end
end
for _,edge in ipairs(self.cluster_edges) do
self.graph:addEdge(edge)
end
for _,edge in ipairs(self.original_edges) do
self.graph:deleteEdge(edge)
end
for _,node in ipairs(self.original_nodes) do
self.graph:deleteNode(node)
end
end
function NodeRankingGansnerKNV1993:createClusterEdges()
for n = 1, #self.cluster_nodes-1 do
local first_cluster = self.cluster_nodes[n]
local second_cluster = self.cluster_nodes[n+1]
local edge = Edge.new{
direction = Edge.RIGHT,
weight = 1,
minimum_levels = 1,
}
edge:addNode(first_cluster)
edge:addNode(second_cluster)
self.graph:addEdge(edge)
table.insert(self.cluster_edges, edge)
end
end
function NodeRankingGansnerKNV1993:removeClusterEdges()
end
function NodeRankingGansnerKNV1993:expandClusters()
for _,node in ipairs(self.original_nodes) do
assert(self.ranking:getRank(self.cluster_node[node]))
self.ranking:setRank(node, self.ranking:getRank(self.cluster_node[node]))
self.graph:addNode(node)
end
for _,edge in ipairs(self.original_edges) do
for _,node in ipairs(edge.nodes) do
node:addEdge(edge)
end
self.graph:addEdge(edge)
end
for _,node in ipairs(self.cluster_nodes) do
self.ranking:setRank(node, nil)
self.graph:deleteNode(node)
end
for _,edge in ipairs(self.cluster_edges) do
self.graph:deleteEdge(edge)
end
end
-- done
return NodeRankingGansnerKNV1993
|