# This file contains the definition of the class RGL::ImplicitGraph which
# defines vertex and edge iterators using blocks (which again call blocks).
# 
# An ImplicitGraph provides a handy way to define graphs on the fly using two
# blocks for the two iterators defining a graph. The directed cyclic graph with
# 5 vertices can be created as follows:
#
#   g = RGL::ImplicitGraph.new { |g|
# 	  g.vertex_iterator { |b| 0.upto(4,&b) }
# 	  g.adjacent_iterator { |x, b| b.call((x+1)%5) }
# 	  g.directed = true
#   }
#   g.to_s => "(0-1)(1-2)(2-3)(3-4)(4-0)"
#
# Other examples are given by the methods vertices_filtered_by and
# edges_filtered_by, which can be applied to any graph.
require 'rgl/base'

module RGL
  class ImplicitGraph
	include Graph

	attr_writer :directed

	EMPTY_VERTEX_ITERATOR = proc { |b| }
	EMPTY_NEIGHBOR_ITERATOR = proc { |x, b| }
	
	# Create a new ImplicitGraph, which is by default empty. The caller should
	# configure the with vertex and neighbor iterators. If the graph is directed
	# the client should set directed to true. The default value for _directed_
	# is false. 
	def initialize
	  @directed = false
	  @vertex_iterator = EMPTY_VERTEX_ITERATOR
	  @adjacent_iterator = EMPTY_NEIGHBOR_ITERATOR
	  yield self if block_given?				# let client overwrite defaults
	end

	# Returns the value of @directed.
	def directed?; @directed; end
	
	def each_vertex (&block)	# :nodoc:
	  @vertex_iterator.call(block)
	end

	def each_adjacent (v, &block) # :nodoc:
	  @adjacent_iterator.call(v,block)
	end

	def each_edge (&block) # :nodoc:
	  if defined? @edge_iterator
		@edge_iterator.call(block)
	  else
		super					# use default implementation
	  end
	end

	# Sets the vertex_iterator to _block_ which must be a block of one parameter
	# which again is the block called by each_vertex.
	def vertex_iterator (&block)
	  @vertex_iterator = block
	end

	# Sets the adjacent_iterator to _block_ which must be a block of two
	# parameters: 
	# The first parameter is the vertex the neighbors of which are to be
	# traversed. The second is the block which will be called for each neighbor
	# of this vertex.
	def adjacent_iterator (&block)
	  @adjacent_iterator = block
	end

	# Sets the edge_iterator to _block_ which must be a block of two parameters:
	# The first parameter is the source of the edges an the second is the target
	# of the edge.
	def edge_iterator (&block)
	  @edge_iterator = block
	end
  end

  module Graph
	# ---
	# === Graph adaptors
	#
	# Return a new ImplicitGraph which has as vertices all vertices of the
	# receiver which satisfy the predicate _filter_.
	#
	# The methods provides similar functionaty as the BGL graph adapter
	# filtered_graph (see BOOST_DOC/filtered_graph.html). 
	#
	# ==== Example
	#
	# 	def complete (n)
	# 	  set = n.integer? ? (1..n) : n
	# 	  RGL::ImplicitGraph.new { |g|
	# 		g.vertex_iterator { |b| set.each(&b) }
	# 		g.adjacent_iterator { |x, b|
	# 		  set.each { |y| b.call(y) unless x == y }
	# 		}
	# 	  }
	# 	end
	#
	# 	complete(4).to_s =>	"(1=2)(1=3)(1=4)(2=3)(2=4)(3=4)"
	# 	complete(4).vertices_filtered_by {|v| v != 4}.to_s => "(1=2)(1=3)(2=3)"
	def vertices_filtered_by (&filter)
	  implicit_graph {|g|
		g.vertex_iterator { |b|
		  self.each_vertex { |v| b.call(v) if filter.call(v) }
		}
		g.adjacent_iterator { |v, b|
		  self.each_adjacent(v) { |u| b.call(u) if filter.call(u) }
		}
	  }
	end

	# Return a new ImplicitGraph which has as edges all edges of the receiver
	# which satisfy the predicate _filter_ (a block with to parameters).
	#
	# ==== Example
	#
	# 	g = complete(7).edges_filtered_by {|u,v| u+v == 7}
	#	g.to_s => "(1=6)(2=5)(3=4)"
	#	g.vertices => [1, 2, 3, 4, 5, 6, 7]
	def edges_filtered_by (&filter)
	  implicit_graph {
		|g|
		g.adjacent_iterator { |v, b|
		  self.each_adjacent(v) { |u|
			b.call(u) if filter.call(v,u)
		  }
		}
		g.edge_iterator { |b|
		  self.each_edge {|u,v| b.call(u,v) if filter.call(u,v)}
		}
	  }
	end

	# Return a new ImplicitGraph which is isomorphic (i.e. has same edges and
	# vertices) to the receiver. It is a shortcut also used by
	# edges_filtered_by and vertices_filtered_by.
	def implicit_graph
	  result = ImplicitGraph.new {|g|
		g.vertex_iterator { |b| self.each_vertex(&b)}
		g.adjacent_iterator { |v, b| self.each_adjacent(v,&b)}
		g.directed = self.directed?
	  }
	  yield result if block_given? # let client overwrite defaults
	  result
	end
  end							# module Graph
end