blob: deaae69524699bb887e333e70fa1b625bcc02042 (
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
|
-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $
local CycleRemovalBergerS1990b = {}
local lib = require("pgf.gd.lib")
function CycleRemovalBergerS1990b:run()
-- remember edges that were removed
local removed = {}
-- remember edges that need to be reversed
local reverse = {}
-- iterate over all nodes of the graph
for _,j in ipairs(lib.random_permutation(#self.graph.nodes)) do
local node = self.graph.nodes[j]
-- get all outgoing edges that have not been removed yet
-- get all outgoing edges that have not been removed yet
local out_edges = lib.imap(node:getOutgoingEdges(),
function (edge)
if not removed[edge] then return edge end
end)
-- get all incoming edges that have not been removed yet
local in_edges = lib.imap(node:getIncomingEdges(),
function (edge)
if not removed[edge] then return edge end
end)
if #out_edges >= #in_edges then
-- we have more outgoing than incoming edges, reverse all incoming
-- edges and mark all incident edges as removed
for _,edge in ipairs(out_edges) do
removed[edge] = true
end
for _,edge in ipairs(in_edges) do
reverse[edge] = true
removed[edge] = true
end
else
-- we have more incoming than outgoing edges, reverse all outgoing
-- edges and mark all incident edges as removed
for _,edge in ipairs(out_edges) do
reverse[edge] = true
removed[edge] = true
end
for _,edge in ipairs(in_edges) do
removed[edge] = true
end
end
end
-- mark edges as reversed
for edge in pairs(reverse) do
edge.reversed = true
end
end
-- done
return CycleRemovalBergerS1990b
|