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