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
|
-- 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$
-- Declare
local CycleRemovalEadesLS1993 = {}
-- Import
local lib = require "pgf.gd.lib"
function CycleRemovalEadesLS1993:run()
local copied_graph = self.graph:copy()
local copied_node = {}
local origin_node = {}
local copied_edge = {}
local origin_edge = {}
local preserve = {}
for _,edge in ipairs(self.graph.edges) do
copied_edge[edge] = edge:copy()
origin_edge[copied_edge[edge]] = edge
for _,node in ipairs(edge.nodes) do
if copied_node[node] then
copied_edge[edge]:addNode(copied_node[node])
else
copied_node[node] = node:copy()
origin_node[copied_node[node]] = node
copied_graph:addNode(copied_node[node])
copied_edge[edge]:addNode(copied_node[node])
end
end
end
local function node_is_sink(node)
return node:getOutDegree() == 0
end
local function node_is_source(node)
return node:getInDegree() == 0
end
local function node_is_isolated(node)
return node:getDegree() == 0
end
while #copied_graph.nodes > 0 do
local sink = lib.find(copied_graph.nodes, node_is_sink)
while sink do
for _,edge in ipairs(sink:getIncomingEdges()) do
preserve[edge] = true
end
copied_graph:deleteNode(sink)
sink = lib.find(copied_graph.nodes, node_is_sink)
end
local isolated_node = lib.find(copied_graph.nodes, node_is_isolated)
while isolated_node do
copied_graph:deleteNode(isolated_node)
isolated_node = lib.find(copied_graph.nodes, node_is_isolated)
end
local source = lib.find(copied_graph.nodes, node_is_source)
while source do
for _,edge in ipairs(source:getOutgoingEdges()) do
preserve[edge] = true
end
copied_graph:deleteNode(source)
source = lib.find(copied_graph.nodes, node_is_source)
end
if #copied_graph.nodes > 0 then
local max_node = nil
local max_out_edges = nil
local max_in_edges = nil
for _,node in ipairs(copied_graph.nodes) do
local out_edges = node:getOutgoingEdges()
local in_edges = node:getIncomingEdges()
if max_node == nil or (#out_edges - #in_edges > #max_out_edges - #max_in_edges) then
max_node = node
max_out_edges = out_edges
max_in_edges = in_edges
end
end
assert(max_node and max_out_edges and max_in_edges)
for _,edge in ipairs(max_out_edges) do
preserve[edge] = true
copied_graph:deleteEdge(edge)
end
for _,edge in ipairs(max_in_edges) do
copied_graph:deleteEdge(edge)
end
copied_graph:deleteNode(max_node)
end
end
for _,edge in ipairs(self.graph.edges) do
if not preserve[copied_edge[edge]] then
edge.reversed = true
end
end
end
-- done
return CycleRemovalEadesLS1993
|