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

-- Imports

local Ranking = require "pgf.gd.layered.Ranking"
local Iterators = require "pgf.gd.deprecated.Iterators"


function NodeRankingMinimumHeight:run()
  local ranking = Ranking.new()

  for node in Iterators.topologicallySorted(self.graph) do
    local edges = node:getIncomingEdges()

    if #edges == 0 then
      ranking:setRank(node, 1)
    else
      local max_rank = -math.huge
      for _,edge in ipairs(edges) do
        max_rank = math.max(max_rank, ranking:getRank(edge:getNeighbour(node)))
      end

      assert(max_rank >= 1)

      ranking:setRank(node, max_rank + 1)
    end
  end

  return ranking
end


-- done

return NodeRankingMinimumHeight