ruby recursion and blocks

[roshanlen]

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 ?

[roshanlen]

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