summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua342
1 files changed, 342 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua
new file mode 100644
index 0000000000..da9ff9698c
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua
@@ -0,0 +1,342 @@
+-- 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 CrossingMinimizationGansnerKNV1993 = {}
+
+
+-- Imports
+
+local lib = require "pgf.gd.lib"
+local DepthFirstSearch = require "pgf.gd.lib.DepthFirstSearch"
+
+
+
+function CrossingMinimizationGansnerKNV1993:run()
+
+ self:computeInitialRankOrdering()
+
+ local best_ranking = self.ranking:copy()
+ local best_crossings = self:countRankCrossings(best_ranking)
+
+ for iteration=1,24 do
+ local direction = (iteration % 2 == 0) and 'down' or 'up'
+
+ self:orderByWeightedMedian(direction)
+ self:transpose(direction)
+
+ local current_crossings = self:countRankCrossings(self.ranking)
+
+ if current_crossings < best_crossings then
+ best_ranking = self.ranking:copy()
+ best_crossings = current_crossings
+ end
+ end
+
+ self.ranking = best_ranking:copy()
+
+ return self.ranking
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:computeInitialRankOrdering()
+
+ local best_ranking = self.ranking:copy()
+ local best_crossings = self:countRankCrossings(best_ranking)
+
+ for _,direction in ipairs({'down', 'up'}) do
+
+ local function init(search)
+ for i=#self.graph.nodes,1,-1 do
+ local node = self.graph.nodes[i]
+ if direction == 'down' then
+ if node:getInDegree() == 0 then
+ search:push(node)
+ search:setDiscovered(node)
+ end
+ else
+ if node:getOutDegree() == 0 then
+ search:push(node)
+ search:setDiscovered(node)
+ end
+ end
+ end
+ end
+
+ local function visit(search, node)
+ search:setVisited(node, true)
+
+ local rank = self.ranking:getRank(node)
+ local pos = self.ranking:getRankSize(rank)
+ self.ranking:setRankPosition(node, pos)
+
+ if direction == 'down' then
+ local out = node:getOutgoingEdges()
+ for i=#out,1,-1 do
+ local neighbour = out[i]:getNeighbour(node)
+ if not search:getDiscovered(neighbour) then
+ search:push(neighbour)
+ search:setDiscovered(neighbour)
+ end
+ end
+ else
+ local into = node:getIncomingEdges()
+ for i=#into,1,-1 do
+ local neighbour = into[i]:getNeighbour(node)
+ if not search:getDiscovered(neighbour) then
+ search:push(neighbour)
+ search:setDiscovered(neighbour)
+ end
+ end
+ end
+ end
+
+ DepthFirstSearch.new(init, visit):run()
+
+ local crossings = self:countRankCrossings(self.ranking)
+
+ if crossings < best_crossings then
+ best_ranking = self.ranking:copy()
+ best_crossings = crossings
+ end
+ end
+
+ self.ranking = best_ranking:copy()
+
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:countRankCrossings(ranking)
+
+ local crossings = 0
+
+ local ranks = ranking:getRanks()
+
+ for rank_index = 2, #ranks do
+ local nodes = ranking:getNodes(ranks[rank_index])
+ for i = 1, #nodes-1 do
+ for j = i+1, #nodes do
+ local v = nodes[i]
+ local w = nodes[j]
+
+ -- TODO Jannis: We are REQUIRED to only check edges that lead to nodes
+ -- on the next or previous rank, depending on the sweep direction!!!!
+ local cn_vw = self:countNodeCrossings(ranking, v, w, 'down')
+
+ crossings = crossings + cn_vw
+ end
+ end
+ end
+
+ return crossings
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:countNodeCrossings(ranking, left_node, right_node, sweep_direction)
+
+ local ranks = ranking:getRanks()
+ local _, rank_index = lib.find(ranks, function (rank)
+ return rank == ranking:getRank(left_node)
+ end)
+ local other_rank_index = (sweep_direction == 'down') and rank_index-1 or rank_index+1
+
+ assert(ranking:getRank(left_node) == ranking:getRank(right_node))
+ assert(rank_index >= 1 and rank_index <= #ranks)
+
+ -- 0 crossings if we're at the top or bottom and are sweeping down or up
+ if other_rank_index < 1 or other_rank_index > #ranks then
+ return 0
+ end
+
+ local left_edges = {}
+ local right_edges = {}
+
+ if sweep_direction == 'down' then
+ left_edges = left_node:getIncomingEdges()
+ right_edges = right_node:getIncomingEdges()
+ else
+ left_edges = left_node:getOutgoingEdges()
+ right_edges = right_node:getOutgoingEdges()
+ end
+
+ local crossings = 0
+
+ local function left_neighbour_on_other_rank(edge)
+ local neighbour = edge:getNeighbour(left_node)
+ return ranking:getRank(neighbour) == ranking:getRanks()[other_rank_index]
+ end
+
+ local function right_neighbour_on_other_rank(edge)
+ local neighbour = edge:getNeighbour(right_node)
+ return ranking:getRank(neighbour) == ranking:getRanks()[other_rank_index]
+ end
+
+ for _,left_edge in ipairs(left_edges) do
+ if left_neighbour_on_other_rank(left_edge) then
+ local left_neighbour = left_edge:getNeighbour(left_node)
+
+ for _,right_edge in ipairs(right_edges) do
+ if right_neighbour_on_other_rank(right_edge) then
+ local right_neighbour = right_edge:getNeighbour(right_node)
+
+ local left_position = ranking:getRankPosition(left_neighbour)
+ local right_position = ranking:getRankPosition(right_neighbour)
+
+ local neighbour_diff = right_position - left_position
+
+ if neighbour_diff < 0 then
+ crossings = crossings + 1
+ end
+ end
+ end
+ end
+ end
+
+ return crossings
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:orderByWeightedMedian(direction)
+
+ local median = {}
+
+ local function get_index(n, node) return median[node] end
+ local function is_fixed(n, node) return median[node] < 0 end
+
+ if direction == 'down' then
+ local ranks = self.ranking:getRanks()
+
+ for rank_index = 2, #ranks do
+ median = {}
+ local nodes = self.ranking:getNodes(ranks[rank_index])
+ for _,node in ipairs(nodes) do
+ median[node] = self:computeMedianPosition(node, ranks[rank_index-1])
+ end
+
+ self.ranking:reorderRank(ranks[rank_index], get_index, is_fixed)
+ end
+ else
+ local ranks = self.ranking:getRanks()
+
+ for rank_index = 1, #ranks-1 do
+ median = {}
+ local nodes = self.ranking:getNodes(ranks[rank_index])
+ for _,node in ipairs(nodes) do
+ median[node] = self:computeMedianPosition(node, ranks[rank_index+1])
+ end
+
+ self.ranking:reorderRank(ranks[rank_index], get_index, is_fixed)
+ end
+ end
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:computeMedianPosition(node, prev_rank)
+
+ local positions = lib.imap(
+ node.edges,
+ function (edge)
+ local n = edge:getNeighbour(node)
+ if self.ranking:getRank(n) == prev_rank then
+ return self.ranking:getRankPosition(n)
+ end
+ end)
+
+ table.sort(positions)
+
+ local median = math.ceil(#positions / 2)
+ local position = -1
+
+ if #positions > 0 then
+ if #positions % 2 == 1 then
+ position = positions[median]
+ elseif #positions == 2 then
+ return (positions[1] + positions[2]) / 2
+ else
+ local left = positions[median-1] - positions[1]
+ local right = positions[#positions] - positions[median]
+ position = (positions[median-1] * right + positions[median] * left) / (left + right)
+ end
+ end
+
+ return position
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:transpose(sweep_direction)
+
+ local function transpose_rank(rank)
+
+ local improved = false
+
+ local nodes = self.ranking:getNodes(rank)
+
+ for i = 1, #nodes-1 do
+ local v = nodes[i]
+ local w = nodes[i+1]
+
+ local cn_vw = self:countNodeCrossings(self.ranking, v, w, sweep_direction)
+ local cn_wv = self:countNodeCrossings(self.ranking, w, v, sweep_direction)
+
+ if cn_vw > cn_wv then
+ improved = true
+
+ self:switchNodePositions(v, w)
+ end
+ end
+
+ return improved
+ end
+
+ local ranks = self.ranking:getRanks()
+
+ local improved = false
+ repeat
+ local improved = false
+
+ if sweep_direction == 'down' then
+ for rank_index = 1, #ranks-1 do
+ improved = transpose_rank(ranks[rank_index]) or improved
+ end
+ else
+ for rank_index = #ranks-1, 1, -1 do
+ improved = transpose_rank(ranks[rank_index]) or improved
+ end
+ end
+ until not improved
+end
+
+
+
+function CrossingMinimizationGansnerKNV1993:switchNodePositions(left_node, right_node)
+ assert(self.ranking:getRank(left_node) == self.ranking:getRank(right_node))
+ assert(self.ranking:getRankPosition(left_node) < self.ranking:getRankPosition(right_node))
+
+ local left_position = self.ranking:getRankPosition(left_node)
+ local right_position = self.ranking:getRankPosition(right_node)
+
+ self.ranking:switchPositions(left_node, right_node)
+
+ local nodes = self.ranking:getNodes(self.ranking:getRank(left_node))
+end
+
+
+
+-- done
+
+return CrossingMinimizationGansnerKNV1993