-- 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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $



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
