summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua291
1 files changed, 291 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua
new file mode 100644
index 00000000000..8b2527edd5f
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua
@@ -0,0 +1,291 @@
+-- Copyright 2011 by Jannis Pohlmann
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $
+
+
+
+--- The Ranking class is used by the Sugiyama algorithm to compute an ordering on the
+-- nodes of a layer
+
+local Ranking = {}
+Ranking.__index = Ranking
+
+-- Namespace
+local layered = require "pgf.gd.layered"
+layered.Ranking = Ranking
+
+
+local lib = require "pgf.gd.lib"
+
+
+-- TODO Jannis: document!
+
+
+function Ranking.new()
+ local ranking = {
+ rank_to_nodes = {},
+ node_to_rank = {},
+ position_in_rank = {},
+ }
+ setmetatable(ranking, Ranking)
+ return ranking
+end
+
+
+
+function Ranking:copy()
+ local copied_ranking = Ranking.new()
+
+ -- copy rank to nodes mapping
+ for rank, nodes in pairs(self.rank_to_nodes) do
+ copied_ranking.rank_to_nodes[rank] = lib.copy(self.rank_to_nodes[rank])
+ end
+
+ -- copy node to rank mapping
+ copied_ranking.node_to_rank = lib.copy(self.node_to_rank)
+
+ -- copy node to position in rank mapping
+ copied_ranking.position_in_rank = lib.copy(self.position_in_rank)
+
+ return copied_ranking
+end
+
+
+
+function Ranking:reset()
+ self.rank_to_nodes = {}
+ self.node_to_rank = {}
+ self.position_in_rank = {}
+end
+
+
+
+function Ranking:getRanks()
+ local ranks = {}
+ for rank, nodes in pairs(self.rank_to_nodes) do
+ table.insert(ranks, rank)
+ end
+ table.sort(ranks)
+ return ranks
+end
+
+
+
+function Ranking:getRankSize(rank)
+ if self.rank_to_nodes[rank] then
+ return #self.rank_to_nodes[rank]
+ else
+ return 0
+ end
+end
+
+
+
+function Ranking:getNodeInfo(node)
+ return self:getRank(node), self:getRankPosition(node)
+end
+
+
+
+function Ranking:getNodes(rank)
+ return self.rank_to_nodes[rank] or {}
+end
+
+
+
+function Ranking:getRank(node)
+ return self.node_to_rank[node]
+end
+
+
+
+function Ranking:setRank(node, new_rank)
+ local rank, pos = self:getNodeInfo(node)
+
+ if rank == new_rank then
+ return
+ end
+
+ if rank then
+ for n = pos+1, #self.rank_to_nodes[rank] do
+ local other_node = self.rank_to_nodes[rank][n]
+ self.position_in_rank[other_node] = self.position_in_rank[other_node]-1
+ end
+
+ table.remove(self.rank_to_nodes[rank], pos)
+ self.node_to_rank[node] = nil
+ self.position_in_rank[node] = nil
+
+ if #self.rank_to_nodes[rank] == 0 then
+ self.rank_to_nodes[rank] = nil
+ end
+ end
+
+ if new_rank then
+ self.rank_to_nodes[new_rank] = self.rank_to_nodes[new_rank] or {}
+ table.insert(self.rank_to_nodes[new_rank], node)
+ self.node_to_rank[node] = new_rank
+ self.position_in_rank[node] = #self.rank_to_nodes[new_rank]
+ end
+end
+
+
+
+function Ranking:getRankPosition(node)
+ return self.position_in_rank[node]
+end
+
+
+
+function Ranking:setRankPosition(node, new_pos)
+ local rank, pos = self:getNodeInfo(node)
+
+ assert((rank and pos) or ((not rank) and (not pos)))
+
+ if pos == new_pos then
+ return
+ end
+
+ if rank and pos then
+ for n = pos+1, #self.rank_to_nodes[rank] do
+ local other_node = self.rank_to_nodes[rank][n]
+ self.position_in_rank[other_node] = self.position_in_rank[other_node]-1
+ end
+
+ table.remove(self.rank_to_nodes[rank], pos)
+ self.node_to_rank[node] = nil
+ self.position_in_rank[node] = nil
+ end
+
+ if new_pos then
+ self.rank_to_nodes[rank] = self.rank_to_nodes[rank] or {}
+
+ for n = new_pos+1, #self.rank_to_nodes[rank] do
+ local other_node = self.rank_to_nodes[rank][new_pos]
+ self.position_in_rank[other_node] = self.position_in_rank[other_node]+1
+ end
+
+ table.insert(self.rank_to_nodes[rank], node)
+ self.node_to_rank[node] = rank
+ self.position_in_rank[node] = new_pos
+ end
+end
+
+
+
+function Ranking:normalizeRanks()
+
+ -- get the current ranks
+ local ranks = self:getRanks()
+
+ local min_rank = ranks[1]
+ local max_rank = ranks[#ranks]
+
+ -- clear ranks
+ self.rank_to_nodes = {}
+
+ -- iterate over all nodes and rerank them manually
+ for node in pairs(self.position_in_rank) do
+ local rank, pos = self:getNodeInfo(node)
+ local new_rank = rank - (min_rank - 1)
+
+ self.rank_to_nodes[new_rank] = self.rank_to_nodes[new_rank] or {}
+ self.rank_to_nodes[new_rank][pos] = node
+
+ self.node_to_rank[node] = new_rank
+ end
+end
+
+
+
+function Ranking:switchPositions(left_node, right_node)
+ local left_rank = self.node_to_rank[left_node]
+ local right_rank = self.node_to_rank[right_node]
+
+ assert(left_rank == right_rank, 'only positions of nodes in the same rank can be switched')
+
+ local left_pos = self.position_in_rank[left_node]
+ local right_pos = self.position_in_rank[right_node]
+
+ self.rank_to_nodes[left_rank][left_pos] = right_node
+ self.rank_to_nodes[left_rank][right_pos] = left_node
+
+ self.position_in_rank[left_node] = right_pos
+ self.position_in_rank[right_node] = left_pos
+end
+
+
+
+function Ranking:reorderRank(rank, get_index_func, is_fixed_func)
+ self:reorderTable(self.rank_to_nodes[rank], get_index_func, is_fixed_func)
+
+ for n = 1, #self.rank_to_nodes[rank] do
+ self.position_in_rank[self.rank_to_nodes[rank][n]] = n
+ end
+end
+
+
+
+function Ranking:reorderTable(input, get_index_func, is_fixed_func)
+ -- collect all allowed indices
+ local allowed_indices = {}
+ for n = 1, #input do
+ if not is_fixed_func(n, input[n]) then
+ table.insert(allowed_indices, n)
+ end
+ end
+
+ -- collect all desired indices; for each of these desired indices,
+ -- remember by which element it was requested
+ local desired_to_real_indices = {}
+ local sort_indices = {}
+ for n = 1, #input do
+ if not is_fixed_func(n, input[n]) then
+ local index = get_index_func(n, input[n])
+ if not desired_to_real_indices[index] then
+ desired_to_real_indices[index] = {}
+ table.insert(sort_indices, index)
+ end
+ table.insert(desired_to_real_indices[index], n)
+ end
+ end
+
+ -- sort the desired indices
+ table.sort(sort_indices)
+
+ -- compute the final indices by counting the final indices generated
+ -- prior to the current one and by mapping this number to the allowed
+ -- index with the same number
+ local final_indices = {}
+ local n = 1
+ for _,index in ipairs(sort_indices) do
+ local real_indices = desired_to_real_indices[index]
+ for _,real_index in ipairs(real_indices) do
+ final_indices[real_index] = allowed_indices[n]
+ n = n + 1
+ end
+ end
+
+ -- flat-copy the input table so that we can still access the elements
+ -- using their real index while overwriting the input table in-place
+ local input_copy = lib.copy(input)
+
+ -- move flexible elements to their final indices
+ for old_index, new_index in pairs(final_indices) do
+ input[new_index] = input_copy[old_index]
+ end
+end
+
+
+
+-- Done
+
+return Ranking \ No newline at end of file