Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New to the CF scene
    Join Date
    Aug 2009
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    ruby recursion and blocks

    hi all

    I have the following simple dependency graph to keep track of projects and their dependencies.
    Code:
    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
    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 )
    Code:
    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 ?

  • #2
    New to the CF scene
    Join Date
    Aug 2009
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Apologies. I made a mistake in the code.

    the Visitor should have a 'return false' as the last statement.
    Code:
    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


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •