# This file contains the algorithms for the connected components of an
# undirected graph (each_connected_component) and strongly connected components
# for directed graphs (strongly_connected_components).
#
require 'rgl/traversal'

module RGL
  module Graph
	# Compute the connected components of an undirected graph using a DFS-based
	# approach. A <b>connected component</b> of an undirected graph is a set of
	# vertices that are all reachable from each other.
	#
	# The function is implemented as an iterator which calls the client with an
	# array of vertices for each component.
	#
	# It raises an exception if the graph is directed.
	def each_connected_component
	  raise NotUndirectedError, "each_connected_component only works for undirected graphs." if directed?
	  comp = []
	  vis = DFSVisitor.new(self)
	  vis.set_finish_vertex_event_handler {|v| comp << v}
	  vis.set_start_vertex_event_handler {|v|
		yield comp unless comp.empty?
		comp = []
	  }
	  depth_first_search(vis) {|v|}
	  yield comp unless comp.empty?
	end

	# This GraphVisitor is used by strongly_connected_components to compute the
	# strongly connected components of a directed graph.
	#
	# 
	class TarjanSccVisitor < DFSVisitor
	  attr_reader :comp_map

	  # Creates a new TarjanSccVisitor for graph _g_, which should be directed.
	  def initialize(g)
		super g
		@root_map = {}
		@comp_map = {}
		@discover_time_map = {}
		@dfs_time = 0
		@c_index = 0
		@stack = []
	  end

	  def handle_examine_vertex(v)
		@root_map[v] = v
		@comp_map[v] = -1
		@dfs_time += 1
		@discover_time_map[v] = @dfs_time
		@stack.push v
	  end

	  def handle_finish_vertex(v)
		# Search adjacent vertex w with earliest discover time
		root_v = @root_map[v]
		graph.each_adjacent(v) do |w|
		  if @comp_map[w] == -1
			root_v = min_discover_time(root_v,@root_map[w])
		  end
		end
		@root_map[v] = root_v
		if root_v == v			# v is topmost vertex of a SCC
          begin					# pop off all vertices until v
            w = @stack.pop
            @comp_map[w] = @c_index
          end until w == v
          @c_index += 1
        end
	  end

	  # Return the number of components found so far.
	  def num_comp
		@c_index
	  end

	  private

	  def min_discover_time(u,v)
		@discover_time_map[u] < @discover_time_map[v] ? u : v
	  end
	end							# TarjanSccVisitor

	# This is Tarjan's algorithm for strongly connected components
	# from his paper "Depth first search and linear graph algorithms".
	# It calculates the components in a single application of DFS.
	# We implement the algorithm with the help of the DFSVisitor
	# TarjanSccVisitor.
	#
	# === Definition
	# 
	# A <b>strongly connected component</b> of a directed graph G=(V,E) is a
	# maximal set of vertices U which is in V such that for every pair of
	# vertices u and  v in U, we have both a path from u to v and path from v to
	# u. That is to say that u and v are reachable from each other.
	# 
	# @Article{Tarjan:1972:DFS,
	#   author =       "R. E. Tarjan",
	#   key =          "Tarjan",
	#   title =        "Depth First Search and Linear Graph Algorithms",
	#   journal =      "SIAM Journal on Computing",
	#   volume =       "1",
	#   number =       "2",
	#   pages =        "146--160",
	#   month =        jun,
	#   year =         "1972",
	#   CODEN =        "SMJCAT",
	#   ISSN =         "0097-5397 (print), 1095-7111 (electronic)",
	#   bibdate =      "Thu Jan 23 09:56:44 1997",
	#   bibsource =    "Parallel/Multi.bib, Misc/Reverse.eng.bib",
	# }
	# 
	# The output of the algorithm is recorded in a TarjanSccVisitor _vis_.
	# vis.comp_map will contain numbers giving the component ID assigned to each 
	# vertex. The number of components is vis.num_comp.
	def strongly_connected_components
	  raise NotDirectedError, "strong_components only works for directed graphs." unless directed?
	  vis = TarjanSccVisitor.new(self)
	  depth_first_search(vis) {|v|}
	  vis
	end
  end
end