summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990b.lua
blob: 218ecbd2099023677b84040eabd3a6865c8d046b (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$


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