complete_sink.rb determines if a given vertex is a sink for all other vertices

complete_sink.rb

=begin 
:mat utter, 10/18/2014
=end
class Graph
	def initialize()
		@graph = Hash.new(false)
		@visit = Hash.new(false)
	end
	def add(key,val)
		@visit	[key] = false

		if @graph.has_key?(key) 
			@graph[key].push( val )
		else
			@graph[key] = Array.new
			@graph[key].push( val )
		end
	end

	def to_s
		return "#{@graph}\n#{@visit}"
	end

	def is_sink( sym )
		@graph.each_key do | x |
			next if @visit[x]	
			print "\nstart(#{x})"
			return false if !self._check_cycle( x, sym ) 
		end
		puts
		return true
	end

	def _check_cycle( sym, targ )
		@graph[sym].each do | val |
			print " -> #{val} "
			return true if val == targ
			@visit[val] = true
			return self._check_cycle( val, targ ) if val
		end
		return false
	end

end

g = Graph.new
g.add(:A,:B)
g.add(:A,:E)
g.add(:B,:C)
g.add(:C,:F)
g.add(:C,:D)
g.add(:D,:E)
g.add(:E,:D)
g.add(:D,:B)
g.add(:F,false)

search = :D

if g.is_sink( search )
	puts
	puts "\n{#{search}} is a sink\n" 
else
	puts
	puts "\n{#{search}} is not a sink\n"
end