------ 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 - 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] 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--