summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/NodePositioningGansnerKNV1993.lua
blob: 3af15ad159398ee6f1ebfe50e5f562bedebae263 (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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
-- 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 NodePositioningGansnerKNV1993 = {}


-- Imports

local layered = require "pgf.gd.layered"

local Graph = require "pgf.gd.deprecated.Graph"
local Edge  = require "pgf.gd.deprecated.Edge"
local Node  = require "pgf.gd.deprecated.Node"

local NetworkSimplex = require "pgf.gd.layered.NetworkSimplex"
local Storage = require "pgf.gd.lib.Storage"


function NodePositioningGansnerKNV1993:run()
  local auxiliary_graph = self:constructAuxiliaryGraph()

  local simplex = NetworkSimplex.new(auxiliary_graph, NetworkSimplex.BALANCE_LEFT_RIGHT)
  simplex:run()
  local x_ranking = simplex.ranking
  
  local layers = Storage.new()
  
  local ranks = self.ranking:getRanks()
  for _,rank in ipairs(ranks) do
    local nodes = self.ranking:getNodes(rank)
    for _,node in ipairs(nodes) do
      node.pos.x = x_ranking:getRank(node.aux_node)
      layers[node.orig_vertex] = rank
    end
  end

  layered.arrange_layers_by_baselines(layers, self.main_algorithm.adjusted_bb, self.main_algorithm.ugraph)
  
  -- Copy back
  for _,rank in ipairs(ranks) do
    local nodes = self.ranking:getNodes(rank)
    for _,node in ipairs(nodes) do
      node.pos.y = node.orig_vertex.pos.y
    end
  end
end




function NodePositioningGansnerKNV1993:constructAuxiliaryGraph()

  local aux_graph = Graph.new()

  local edge_node = {}

  for _,node in ipairs(self.graph.nodes) do
    local copy = Node.new{
      name = node.name,
      orig_node = node,
    }
    node.aux_node = copy
    aux_graph:addNode(copy)
  end

  for i=#self.graph.edges,1,-1 do
    local edge = self.graph.edges[i]
    local node = Node.new{
      name = '{' .. tostring(edge) .. '}',
    }

    aux_graph:addNode(node)

    node.orig_edge = edge
    edge_node[edge] = node

    local head = edge:getHead()
    local tail = edge:getTail()

    local tail_edge = Edge.new{
      direction = Edge.RIGHT,
      minimum_levels = 0,
      weight = edge.weight * self:getOmega(edge),
    }
    tail_edge:addNode(node)
    tail_edge:addNode(tail.aux_node)
    aux_graph:addEdge(tail_edge)

    local head_edge = Edge.new{
      direction = Edge.RIGHT,
      minimum_levels = 0,
      weight = edge.weight * self:getOmega(edge),
    }
    head_edge:addNode(node)
    head_edge:addNode(head.aux_node)
    aux_graph:addEdge(head_edge)
  end

  local ranks = self.ranking:getRanks()
  for _,rank in ipairs(ranks) do
    local nodes = self.ranking:getNodes(rank)
    for n = 1, #nodes-1 do
      local v = nodes[n]
      local w = nodes[n+1]

      local separator_edge = Edge.new{
        direction = Edge.RIGHT,
        minimum_levels = self:getDesiredHorizontalDistance(v, w),
        weight = 0,
      }
      separator_edge:addNode(v.aux_node)
      separator_edge:addNode(w.aux_node)
      aux_graph:addEdge(separator_edge)
    end
  end

  return aux_graph
end



function NodePositioningGansnerKNV1993:getOmega(edge)
  local node1 = edge.nodes[1]
  local node2 = edge.nodes[2]

  if (node1.kind == "dummy") and (node2.kind == "dummy") then
    return 8
  elseif (node1.kind == "dummy") or (node2.kind == "dummy") then
    return 2
  else
    return 1
  end
end



function NodePositioningGansnerKNV1993:getDesiredHorizontalDistance(v, w)
  return layered.ideal_sibling_distance(self.main_algorithm.adjusted_bb, self.graph.orig_digraph, v.orig_vertex, w.orig_vertex)
end


-- done

return NodePositioningGansnerKNV1993