-- 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/NodePositioningGansnerKNV1993.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $



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