-- 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/NodeRankingGansnerKNV1993.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $


local NodeRankingGansnerKNV1993 = {}


-- Imports

local Edge           = require "pgf.gd.deprecated.Edge"
local Node           = require "pgf.gd.deprecated.Node"

local NetworkSimplex = require "pgf.gd.layered.NetworkSimplex"



function NodeRankingGansnerKNV1993:run()

  local simplex = NetworkSimplex.new(self.graph, NetworkSimplex.BALANCE_TOP_BOTTOM)
  simplex:run()
  self.ranking = simplex.ranking

  return simplex.ranking
end



function NodeRankingGansnerKNV1993:mergeClusters()

  self.cluster_nodes = {}
  self.cluster_node = {}
  self.cluster_edges = {}

  self.original_nodes = {}
  self.original_edges = {}

  for _,cluster in ipairs(self.graph.clusters) do

    local cluster_node = Node.new{
      name = 'cluster@' .. cluster.name,
    }
    table.insert(self.cluster_nodes, cluster_node)

    for _,node in ipairs(cluster.nodes) do
      self.cluster_node[node] = cluster_node
      table.insert(self.original_nodes, node)
    end

    self.graph:addNode(cluster_node)
  end

  for _,edge in ipairs(self.graph.edges) do
    local tail = edge:getTail()
    local head = edge:getHead()

    if self.cluster_node[tail] or self.cluster_node[head] then
      table.insert(self.original_edges, edge)

      local cluster_edge = Edge.new{
        direction = Edge.RIGHT,
        weight = edge.weight,
        minimum_levels = edge.minimum_levels,
      }
      table.insert(self.cluster_edges, cluster_edge)

      if self.cluster_node[tail] then
        cluster_edge:addNode(self.cluster_node[tail])
      else
        cluster_edge:addNode(tail)
      end

      if self.cluster_node[head] then
        cluster_edge:addNode(self.cluster_node[head])
      else
        cluster_edge:addNode(head)
      end

    end
  end

  for _,edge in ipairs(self.cluster_edges) do
    self.graph:addEdge(edge)
  end

  for _,edge in ipairs(self.original_edges) do
    self.graph:deleteEdge(edge)
  end

  for _,node in ipairs(self.original_nodes) do
    self.graph:deleteNode(node)
  end
end



function NodeRankingGansnerKNV1993:createClusterEdges()
  for n = 1, #self.cluster_nodes-1 do
    local first_cluster = self.cluster_nodes[n]
    local second_cluster = self.cluster_nodes[n+1]

    local edge = Edge.new{
      direction = Edge.RIGHT,
      weight = 1,
      minimum_levels = 1,
    }

    edge:addNode(first_cluster)
    edge:addNode(second_cluster)

    self.graph:addEdge(edge)

    table.insert(self.cluster_edges, edge)
  end
end



function NodeRankingGansnerKNV1993:removeClusterEdges()
end



function NodeRankingGansnerKNV1993:expandClusters()

  for _,node in ipairs(self.original_nodes) do
    assert(self.ranking:getRank(self.cluster_node[node]))
    self.ranking:setRank(node, self.ranking:getRank(self.cluster_node[node]))
    self.graph:addNode(node)
  end

  for _,edge in ipairs(self.original_edges) do
    for _,node in ipairs(edge.nodes) do
      node:addEdge(edge)
    end
    self.graph:addEdge(edge)
  end
  
  for _,node in ipairs(self.cluster_nodes) do
    self.ranking:setRank(node, nil)
    self.graph:deleteNode(node)
  end

  for _,edge in ipairs(self.cluster_edges) do
    self.graph:deleteEdge(edge)
  end
end


-- done

return NodeRankingGansnerKNV1993