summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CycleRemovalBergerS1990a.lua
blob: 76deb8adaf623d5b17e255d5efe9b3d6ca727ce7 (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
-- 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 CycleRemovalBergerS1990a = {}

local lib = require("pgf.gd.lib")


function CycleRemovalBergerS1990a: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 _,node in ipairs(self.graph.nodes) do
    -- 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 CycleRemovalBergerS1990a