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



--- The Iterators class is a singleton object.
--
-- It provides advanced iterators.

local Iterators = {}

-- Namespace

local lib = require("pgf.gd.lib")



--- Iterator for traversing a \meta{dag} using a topological sorting.
--
-- A topological sorting of a directed graph is a linear ordering of its
-- nodes such that, for every edge |(u,v)|, |u| comes before |v|.
--
-- Important note: if performed on a graph with at least one cycle a
-- topological sorting is impossible. Thus, the nodes returned from the
-- iterator are not guaranteed to satisfy the ``|u| comes before |v|''
-- criterion. The iterator may even terminate early or loop forever.
--
-- @param graph A directed acyclic graph.
--
-- @return An iterator for traversing \meta{graph} in a topological order.
--
function Iterators.topologicallySorted(dag)
  -- track visited edges 
  local deleted_edges = {}

  -- collect all sources (nodes with no incoming edges) of the dag
  local sources = lib.imap(dag.nodes, function (node) if node:getInDegree() == 0 then return node end end)

  -- return the iterator function
  return function () 
    while #sources > 0 do
      -- fetch the next sink from the queue
      local source = table.remove(sources, 1)

      -- get its outgoing edges
      local out_edges = source:getOutgoingEdges()
      
      -- iterate over all outgoing edges we haven't visited yet
      for _,edge in ipairs(out_edges) do
	if not deleted_edges[edge] then 
	  -- mark the edge as visited
	  deleted_edges[edge] = true
	  
	  -- get the node at the other end of the edge
	  local neighbour = edge:getNeighbour(source)
	  
	  -- get a list of all incoming edges of the neighbour that have
	  -- not been visited yet
	  local in_edges = lib.imap(neighbour:getIncomingEdges(),
				    function (edge) if not deleted_edges[edge] then return edge end end)
	  
	  -- if there are no such edges then we have a new source
	  if #in_edges == 0 then
	    sources[#sources+1] = neighbour
	  end
	end
      end

      -- return the current source
      return source
    end

    -- the iterator terminates if there are no sources left
    return nil
  end
end



-- Done

return Iterators