ruby recursion and blocks

hi all

I have the following simple dependency graph to keep track of projects and their dependencies.

class Project
attr_accessor :name,:major,:minor,:suffix,:platform,:config,:build_num,:built
attr_accessor :parent
attr_reader :deps
def initialize(n,mj,mi=nil,suf=nil,plat=nil,config=nil,build=nil)
@name=n;
@major=mj;
@minor=mi;
@suffix=suf
@platform=plat
@config=config
@build_num=build
@deps = Array.new
@parent=nil
end

def is_built?
return @built
end

def add_dep(dep)
@deps.push(dep)
end

def has_children
return @deps.length > 0
end

end

##
# DependencyGraph
# A way to keep track of all the dependencies
##
class DependencyGraph
def initialize()
@nodes = Hash.new
@log = Logger.new(STDOUT)
end

def add_node(node)
if @nodes.has_key?(node.name) then
@log.debug("trying to add a project that is already in the graph")
return
end
@nodes[node.name] = node
end

def add_child(parent,child)
@nodes[parent].deps.each { |c|
if c == child then
@log.debug("child already exists in the list")
return
end
}
@nodes[parent].add_dep(child)
end

def have_cycles?(node)
if node.deps.length == 0 then
return false
end
node.deps.each {|c| if visitor(@nodes[c],node.name) then
return true
end

}
return false
end

def visitor(node,root)
#debug
puts "visiting #{node.name} and #{root}"
if node.name == root then
puts "#{node.name} -- #{root}"
puts "returning true**"
return true
end
node.deps.each do |c|
#debug
puts "calling visitor with #{@nodes[c].name} and #{root}"
if visitor(@nodes[c],root) then
puts "returning true"
return true
end
end
end

def to_s
puts 'depencency graph'
@nodes.each do |key,value|
puts "#{key}"
value.deps.each { |c|
puts " #{c}"
}
end
end

end


this is the unit test code

$:.unshift File.join(File.dirname(__FILE__),"..","lib")
require 'test/unit'
require 'lib/Dependency'
require 'logger'

class DependencyGraphTest < Test::Unit::TestCase
def setup
@dep_graph = DependencyGraph.new
end

def test_single_cycle
# one single cycle
# p1 <----------
# p2 p3 |
# p4 p5 ------------
dep1 = Project.new("p1",10)
dep2 = Project.new("p2",10)
dep3 = Project.new("p3",10)
dep4 = Project.new("p4",10)
dep5 = Project.new("p5",10)
@dep_graph.add_node(dep1)
@dep_graph.add_child("p1","p2")
@dep_graph.add_child("p1","p3")
@dep_graph.add_node(dep2)
@dep_graph.add_child("p2","p4")
@dep_graph.add_child("p2","p5")
@dep_graph.add_node(dep3)
@dep_graph.add_node(dep4)
@dep_graph.add_node(dep5)
@dep_graph.add_child("p5","p1")
puts @dep_graph
assert_equal(true,@dep_graph.have_cycles?(dep1))
end
end


The test code will construct a simple graph and check if there are any cycles in the graph. Unfortunately, regardless of whether there are cycles or not it always, for the call have_cycles?, it outputs "true"

The output of this program ( with debug messages )

depencency graph
p1
p2
p3
p2
p4
p5
p3
p4
p5
p1
#<DependencyGraph:0x32a7710>
visiting p2 and p1
calling visitor with p4 and p1
visiting p4 and p1
returning true

Basically the code behaves strangely, it basically jumps over a set of instructions.

After "visiting p4 and p1" message it has to print either "returning true**" or "calling visitor with ....".

Is there a certain restriction in ruby when it comes to using code blocks and recursion ?

Apologies. I made a mistake in the code.

the Visitor should have a 'return false' as the last statement.

def visitor(node,root)
#debug
puts "visiting #{node.name} and #{root}"
if node.name == root then
puts "#{node.name} -- #{root}"
puts "returning true**"
return true
end
node.deps.each do |c|
#debug
puts "calling visitor with #{@nodes[c].name} and #{root}"
if visitor(@nodes[c],root) then
puts "returning true"
return true
end
end
return false
end