------art_19506_20929006.1144201448562
Content-Type: multipart/alternative; 
	boundary---art_19507_2709631.1144201448563"

------art_19507_2709631.1144201448563
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Here is my submission.

Files:
rubyquiz73_test_bbox.rb - black box test
rubyquiz73_test_wbox.rb - white box test
digraph.rb  - modified source code

Basically I tried to create digraphs is a somewhat automated and random way
using the function 'generate_dg'
This function generates a dg in @dg, an array of nodes in @nodes, and an
adjacency hash in @paths.
In the adjacency hash, called @paths, @path[X]  is an array of all the nodes
coming out of node X.

The functions test_03 and test_04 attempt to test the
max_length_of_simple_path_including_node and
strongly_connected_component_including_node functions. I created a
'reference' model for these functions to test against.

During whitebox testing I created a few additional tests to test cases where
I found bugs.

Thanks for the interesting problem.
From my earlier post I think you can tell I'm pretty new to ruby.
I really learned a lot, especially by looking at the source code for digraph

Himadri

------art_19507_2709631.1144201448563
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Here is my submission.<br><br>Files:<br>rubyquiz73_test_bbox.rb - black boxest<br>rubyquiz73_test_wbox.rb - white box test<br>digraph.rb&nbsp; - modified source code<br><br>Basically I tried to create digraphs is a somewhatutomated and random way using the function 'generate_dg'
<br>This function generates a dg in @dg, an array of nodes in @nodes, and an adjacency hash in @paths.<br>In the adjacency hash, called @paths, @path[X]&nbsp; is an array of all the nodes coming out of node X.<br><br>The functions test_03 and test_04 attempt to test the max_length_of_simple_path_including_node and strongly_connected_component_including_node functions. I created a 'reference' model for these functions to test against.
<br><br>During whitebox testing I created a few additional tests to test cases where I found bugs.<br><br>Thanks for the interesting problem.<br>From my earlier post I think you can tell I'm pretty new to ruby.<br>I really learned a lot, especially by looking at the source code for digraph
<br><br>Himadri<br>

------art_19507_2709631.1144201448563--

------art_19506_20929006.1144201448562
Content-Type: application/octet-stream; name=rubyquiz73_test_bbox.rb
Content-Transfer-Encoding: 7bit
X-Attachment-Id: f_elmzwx3a
Content-Disposition: attachment; filename="rubyquiz73_test_bbox.rb"

#!/usr/bin/env ruby


require 'test/unit'
require 'rubyquiz73'

# You must insert your email address as <youremail> in this method call!
DiGraph  ubyQuiz73.class_under_test("hchoudh / gmail.com")

class DiGraph
    @path_strs
    def equal?(g)
        if (g.size ! elf.size)
            return false
        end
        # XXX: Must be better way to initialize @path_strs. Perhaps using initialize method?
        if (not @path_strs)
            g_str  elf.to_s
            @paths_strs  ash.new
            g_arr  _str.split(/[,\[\]]/)
            g_arr.shift
            g_arr.each do |s|
                s.strip!
                @paths_strs[s]  
            end
        end

        g_str  .to_s
        g_arr  _str.split(/[,\[\]]/)
        g_arr.shift
        g_arr.each do |s|
            s.strip!
            if (not @paths_strs[s])
                return false
            end
        end
        return true 
    end
end

class TestDiGraph < Test::Unit::TestCase
    def test_01_digraph_creation
        dg1  iGraph.new
        assert_kind_of(DiGraph, dg1)
        assert_equal(0, dg1.size)
    end

    def test_02_size
        dg2  iGraph.new([1,2], [2,3])
        assert_equal(3, dg2.size)
        assert_equal(2, dg2.num_edges)
    end

    # Add/write your own tests here...

    # @dg is the generated DiGraph. Store the paths in a hash called @paths
    @dg
    # @paths is a hash. Each element of the hash is an array that contains all the paths 
    # from that node
    @paths
    # @nodes is an array which contains a list of all the nodes
    @nodes

    # Randomly generate @dg and the corresponding @paths
    def generate_dg
        nodes  rray.new
        # 10 nodes total
        10.times do 
            nodes << rand(10)
        end
        nodes.uniq!
        @paths  ash.new
        nodes.each do |n|
            num_paths_from_each_node  and(3) + 1
            next_nodes  rray.new
            num_paths_from_each_node.times do
                next_nodes << nodes[rand(nodes.length)]
            end
            next_nodes.uniq!
            @paths[n]  ext_nodes
        end
        arr  rray.new
        @paths.each do |key,vals|
            @paths[key].each do |val|
                arr << [key,val]
            end
        end
        @dg  iGraph.new(*arr)
        @nodes  paths.keys
    end

    # Depth first search for the longest simple path starting from 'node'
    # Simple path means a path that doesn't contain any duplicate edges
    # Note: I'm not suing the definition of simply connected based on no duplicate nodes
    def search(node)
        longest_path  
        if (@paths[node])
            @paths[node].each_index do |next_idx|
                next_node  paths[node][next_idx]
                @paths[node].delete_at(next_idx)
                tmp   + search(next_node)
                @paths[node].insert(next_idx,next_node)
                if (longest_path < tmp)
                    longest_path  mp
                end
            end
        end
        return longest_path
    end

    def find(start,last)
        next_nodes  rray.new
        next_nodes << start
        visited  }
        while (not next_nodes.empty?)
            next_node  ext_nodes.shift
            next if visited[next_node]
            visited[next_node]  rue
            return true if next_node last
            @paths[next_node].map do |x| next_nodes << x end
        end
        return false
    end

    # Flood fill to find the largest strongly connected component starting from node
    # Strongly connected means that there is a path from u->v and from v->u
    # Paths does not mean edges. Paths could have multiple edges
    def fill(node)
        filled_so_far  rray.new
        nodes_hash  ash.new
        already_seen  ash.new
        queue  node]
        while (not queue.empty?)
            next_node  ueue.shift
            next if already_seen[next_node]
            already_seen[next_node]  rue
            @paths[next_node].each do |next_next_node|
                if (next_next_node next_node)
                    # special case. we consider a node connected to itself to be strongly connected
                    nodes_hash[next_node]  rue
                elsif (find(next_next_node,next_node)) 
                    # make sure there is a reverse path
                    queue << next_next_node
                    nodes_hash[next_node]  rue
                    nodes_hash[next_next_node]  rue
                end
            end
        end
        nodes  odes_hash.keys
        @paths.each do |k,v|
            if nodes.include?(k)
                v.each do |v|
                    if nodes.include?(v)
                        filled_so_far << [k,v]
                    end
                end
            end
        end
        return filled_so_far
    end

    def test_03_max_length_of_simple_path_including_node
        generate_dg
        @nodes.each do |node|
            longest_path  earch(node)
#            if (longest_path ! dg.max_length_of_simple_path_including_node(node))
#                puts "test_03 failed..."
#                puts "DiGraph  #{@dg.to_s}"
#                puts "node     #{node}"
#                puts "expected #{longest_path}"
#                puts "received #{@dg.max_length_of_simple_path_including_node(node)}"
#            end
            assert_equal(longest_path,@dg.max_length_of_simple_path_including_node(node))
        end
    end

    def test_04_strongly_connected_component_including_node
        generate_dg
        @nodes.each do |node|
            filled_dg  iGraph.new(*fill(node))
            received_dg  dg.strongly_connected_component_including_node(node)
#           if (not filled_dg.equal?(received_dg))
#               puts "test_04 failed..."
#               puts "DiGraph  #{@dg.to_s}"
#               puts "node     #{node}"
#               puts "expected #{filled_dg.to_s}"
#               puts "received #{received_dg.to_s}"
#           end
            assert_equal(true,filled_dg.equal?(received_dg))
        end
    end
end



------art_19506_20929006.1144201448562
Content-Type: application/octet-stream; name=rubyquiz73_test_wbox.rb
Content-Transfer-Encoding: 7bit
X-Attachment-Id: f_elmzx5xw
Content-Disposition: attachment; filename="rubyquiz73_test_wbox.rb"

#!/usr/bin/env ruby


require 'test/unit'
require 'digraph'


class DiGraph
    @path_strs
    def equal?(g)
        if (g.size ! elf.size)
            return false
        end
        # XXX: Must be better way to initialize @path_strs. Perhaps using initialize method?
        if (not @path_strs)
            g_str  elf.to_s
            @paths_strs  ash.new
            g_arr  _str.split(/[,\[\]]/)
            g_arr.shift
            g_arr.each do |s|
                s.strip!
                @paths_strs[s]  
            end
        end

        g_str  .to_s
        g_arr  _str.split(/[,\[\]]/)
        g_arr.shift
        g_arr.each do |s|
            s.strip!
            if (not @paths_strs[s])
                return false
            end
        end
        return true 
    end
end

class TestDiGraph < Test::Unit::TestCase
    def test_01_digraph_creation
        dg1  iGraph.new
        assert_kind_of(DiGraph, dg1)
        assert_equal(0, dg1.size)
    end

    def test_02_size
        dg2  iGraph.new([1,2], [2,3])
        assert_equal(3, dg2.size)
        assert_equal(2, dg2.num_edges)
    end

    # Add/write your own tests here...

    # @dg is the generated DiGraph. Store the paths in a hash called @paths
    @dg
    # @paths is a hash. Each element of the hash is an array that contains all the paths 
    # from that node
    @paths
    # @nodes is an array which contains a list of all the nodes
    @nodes

    # Randomly generate @dg and the corresponding @paths
    def generate_dg
        nodes  rray.new
        # 10 nodes total
        10.times do 
            nodes << rand(10)
        end
        nodes.uniq!
        @paths  ash.new
        nodes.each do |n|
            num_paths_from_each_node  and(3) + 1
            next_nodes  rray.new
            num_paths_from_each_node.times do
                next_nodes << nodes[rand(nodes.length)]
            end
            next_nodes.uniq!
            @paths[n]  ext_nodes
        end
        arr  rray.new
        @paths.each do |key,vals|
            @paths[key].each do |val|
                arr << [key,val]
            end
        end
        @dg  iGraph.new(*arr)
        @nodes  paths.keys
    end

    # Depth first search for the longest simple path starting from 'node'
    # Simple path means a path that doesn't contain any duplicate edges
    # Note: I'm not suing the definition of simply connected based on no duplicate nodes
    def search(node)
        longest_path  
        if (@paths[node])
            @paths[node].each_index do |next_idx|
                next_node  paths[node][next_idx]
                @paths[node].delete_at(next_idx)
                tmp   + search(next_node)
                @paths[node].insert(next_idx,next_node)
                if (longest_path < tmp)
                    longest_path  mp
                end
            end
        end
        return longest_path
    end

    # find whether there is a path from node start to last
    def find(start,last)
        next_nodes  rray.new
        next_nodes << start
        visited  }
        while (not next_nodes.empty?)
            next_node  ext_nodes.shift
            next if visited[next_node]
            visited[next_node]  rue
            return true if next_node last
            @paths[next_node].map do |x| next_nodes << x end
        end
        return false
    end

    # Flood fill to find the largest strongly connected component starting from node
    # Strongly connected means that there is a path from u->v and from v->u
    def fill(node)
        filled_so_far  rray.new
        nodes_hash  ash.new
        already_seen  ash.new
        queue  node]
        while (not queue.empty?)
            next_node  ueue.shift
            next if already_seen[next_node]
            already_seen[next_node]  rue
            @paths[next_node].each do |next_next_node|
                if (next_next_node next_node)
                    # special case. we consider a node connected to itself to be strongly connected
                    nodes_hash[next_node]  rue
                elsif (find(next_next_node,next_node)) 
                    # make sure there is a reverse path
                    queue << next_next_node
                    nodes_hash[next_node]  rue
                    nodes_hash[next_next_node]  rue
                end
            end
        end
        nodes  odes_hash.keys
        @paths.each do |k,v|
            if nodes.include?(k)
                v.each do |v|
                    if nodes.include?(v)
                        filled_so_far << [k,v]
                    end
                end
            end
        end
        return filled_so_far
    end

    def test_03_max_length_of_simple_path_including_node
        generate_dg
        @nodes.each do |node|
            longest_path  earch(node)
#            if (longest_path ! dg.max_length_of_simple_path_including_node(node))
#                puts "test_03 failed..."
#                puts "DiGraph  #{@dg.to_s}"
#                puts "node     #{node}"
#                puts "expected #{longest_path}"
#                puts "received #{@dg.max_length_of_simple_path_including_node(node)}"
#            end
            assert_equal(longest_path,@dg.max_length_of_simple_path_including_node(node))
        end
    end

    def test_04_strongly_connected_component_including_node
        generate_dg
        @nodes.each do |node|
            filled_dg  iGraph.new(*fill(node))
            received_dg  dg.strongly_connected_component_including_node(node)
            if (not filled_dg.equal?(received_dg))
                puts "test_04 failed..."
                puts "DiGraph  #{@dg.to_s}"
                puts "node     #{node}"
                puts "expected #{filled_dg.to_s}"
                puts "received #{received_dg.to_s}"
            end
            assert_equal(true,filled_dg.equal?(received_dg))
        end
    end

    # Bug found using this test case
    def test_05
        @dg  iGraph.new([0,7],[1,9],[1,4],[7,4],[7,0],[7,9],[3,7],[9,4],[9,7],[9,9],[4,1],[4,4],[4,7])
        @paths  ash.new
        @paths[0]  7]
        @paths[1]  9,4]
        @paths[7]  4,0,9]
        @paths[3]  7]
        @paths[9]  4,7,9]
        @paths[4]  1,4,7]
        @nodes  paths.keys
        received_dg  dg.strongly_connected_component_including_node(0);
        filled_dg  iGraph.new(*fill(0));
        if (not filled_dg.equal?(received_dg))
            puts "test_05 failed..."
            puts "DiGraph  #{@dg.to_s}"
            puts "node     0"
            puts "expected #{filled_dg.to_s}"
            puts "received #{received_dg.to_s}"
        end
        assert_equal(true,filled_dg.equal?(received_dg))
    end

    # Bug found using this test case
    def test_06
        @dg  iGraph.new([5,9],[0,3],[3,8],[8,9],[9,0])
        @paths  ash.new
        @paths[5]  9]
        @paths[0]  3]
        @paths[3]  8]
        @paths[8]  9]
        @paths[9]  0]
        @nodes  paths.keys
        received_dg  dg.strongly_connected_component_including_node(0);
        filled_dg  iGraph.new(*fill(0));
        if (not filled_dg.equal?(received_dg))
            puts "test_06 failed..."
            puts "DiGraph  #{@dg.to_s}"
            puts "node     0"
            puts "expected #{filled_dg.to_s}"
            puts "received #{received_dg.to_s}"
        end
        assert_equal(true,filled_dg.equal?(received_dg))
    end
    # Bug found using this test case
    def test_07
        @dg  iGraph.new([0,0],[6,0],[6,8],[2,6],[8,8],[3,4],[3,2],[3,9],[9,4],[9,6],[4,3],[4,8])
        @paths  ash.new
        @paths[0]  0]
        @paths[6]  0,8]
        @paths[2]  6]
        @paths[8]  8]
        @paths[3]  4,2,9]
        @paths[9]  4,6]
        @paths[4]  3,8]
        @nodes  paths.keys
        received_dg  dg.strongly_connected_component_including_node(6);
        filled_dg  iGraph.new(*fill(6));
        if (not filled_dg.equal?(received_dg))
            puts "test_07 failed..."
            puts "DiGraph  #{@dg.to_s}"
            puts "node     6"
            puts "expected #{filled_dg.to_s}"
            puts "received #{received_dg.to_s}"
        end
        assert_equal(true,filled_dg.equal?(received_dg))
    end
end



------art_19506_20929006.1144201448562
Content-Type: application/octet-stream; name=digraph.rb
Content-Transfer-Encoding: 7bit
X-Attachment-Id: f_elmzxe78
Content-Disposition: attachment; filename="digraph.rb"

# A simple and untested DiGraph implementation.
#

class DiGraph
  attr_reader :edges, :nodes
  def adjacency_list
      return @adjacency_list 
  end
  # The edges are given as arrays of size 1 (simply adding a node without
  # any edges) or size 2 (adding both nodes with an edge from the first one
  # to the second one). Nodes can be any Ruby object.
  def initialize(*edges)
    @nodes  dges.flatten.uniq
    @edges  dges.select {|e| e.length 2}
    @adjacency_list  alc_adjacencies(edges)
  end

  def class_name
    self.class.inspect.split('::').last
  end
  
  def to_s
    class_name + "[" +
      edges.map {|e| e.first.to_s + " -> " + e.last.to_s}.join(', ') + "]"
  end

  def inspect; to_s; end
  def num_nodes; @nodes.length; end
  alias_method :size, :num_nodes
  def num_edges; @edges.length; end

  def transpose
    @transpose || elf.class.new(*(@edges.map {|e| e.reverse}))
  end

  def depth_first_search
    unvisited, visited  nodes.clone, {} #nodes -> @nodes
    while unvisited.length > 0
      depth_first_search_from(unvisited.first, visited) do |node|
        unvisited.delete(node)
        yield(node)
      end
    end
  end

  # Test target 1
  def max_length_of_simple_path_including_node(node)
    return 0 unless nodes.include?(node)
    length_of_longest_path_from(node)# + 
    # XXX: removed transpose
    # transpose.length_of_longest_path_from(node)
  end

  # Test target 2
  def strongly_connected_component_including_node(node)
    c  odes_in_scc_with(node)
    edges_in_scc        edges.select {|e| c.include?(e.first) && c.include?(e.last)} 
    self.class.new(*edges_in_scc)
  end

  # The 
  def length_of_longest_path_from(node, visited  })
#    return 1 if visited[node]
    # XXX: Changed code so that edges are tracked not vertices. My unserstanding of the definition
      # of 'simply connected' was based on no duplicated edges, not no duplicate veritices
    adj  adjacency_list[node]
    return 0 if adj.length < 1
    max_len  
    adj.each do |an|
        if (not visited[node] or not visited[node][an])
            if (not visited[node])
                visited[node]  }
            end
            visited[node][an]  rue
            tmp   + length_of_longest_path_from(an, visited)
            if (max_len < tmp)
                max_len  mp
            end
            visited[node][an]  alse
        end
    end
    return max_len
  end

  protected

  def depth_first_search_from(start, visited  }, &block)
    return if visited[start]
    visited[start]  rue
    block.call(start) if block
    @adjacency_list[start].each do |n| 
        depth_first_search_from(n, visited, &block)
    end
  end

  def nodes_in_strongly_connected_components
    numbered  ]
    depth_first_search() {|n| numbered << n}
    #self.transpose self
    sccs, gt, visited  ], self.transpose, {} 
    newly_visited, already_visited  ], []
    #XXX: reworked this to use two hashes to keep track of forward and backward paths
    while numbered.length > 0
      visited1, visited2,{}
      self.depth_first_search_from(numbered.last, visited1)
      gt.depth_first_search_from(numbered.last, visited2)
      newly_visited  visited1.keys & visited2.keys) - already_visited
      already_visited + ewly_visited
      sccs << newly_visited
      numbered - ewly_visited
    end
    sccs
  end

  private

  def nodes_in_scc_with(node)
    nodes_in_strongly_connected_components.detect {|c| c.include?(node)}
  end

  def calc_nodes(edges)
    edges.map {|e| e.to_a}.flatten.uniq.compact
  end

  def calc_adjacencies(edges)
    h  ash.new {|h,k| h[k]  rray.new}
    edges.each do |e|
      if e.length > 1
        h[e.first] << e.last
        h[e.last] || rray.new  # ensure all nodes are in the hash
      end
    end
    h
  end
end

------art_19506_20929006.1144201448562--