------=_Part_19506_20929006.1144201448562
Content-Type: multipart/alternative;
boundary="----=_Part_19507_2709631.1144201448563"
------=_Part_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 node=
s
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 wher=
e
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 digrap=
h
Himadri
------=_Part_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 box=
test<br>rubyquiz73_test_wbox.rb - white box test<br>digraph.rb - mod=
ified source code<br><br>Basically I tried to create digraphs is a somewhat=
automated and random way using the function 'generate_dg'
<br>This function generates a dg in @dg, an array of nodes in @nodes, and a=
n 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 func=
tions test_03 and test_04 attempt to test the max_length_of_simple_path_inc=
luding_node and strongly_connected_component_including_node functions. I cr=
eated a 'reference' model for these functions to test against.
<br><br>During whitebox testing I created a few additional tests to test ca=
ses 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 le=
arned a lot, especially by looking at the source code for digraph
<br><br>Himadri<br>
------=_Part_19507_2709631.1144201448563--
------=_Part_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 = RubyQuiz73.class_under_test("hchoudh / gmail.com")
class DiGraph
@path_strs
def equal?(g)
if (g.size != self.size)
return false
end
# XXX: Must be better way to initialize @path_strs. Perhaps using initialize method?
if (not @path_strs)
g_str = self.to_s
@paths_strs = Hash.new
g_arr = g_str.split(/[,\[\]]/)
g_arr.shift
g_arr.each do |s|
s.strip!
@paths_strs[s] = 1
end
end
g_str = g.to_s
g_arr = g_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 = DiGraph.new
assert_kind_of(DiGraph, dg1)
assert_equal(0, dg1.size)
end
def test_02_size
dg2 = DiGraph.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 = Array.new
# 10 nodes total
10.times do
nodes << rand(10)
end
nodes.uniq!
@paths = Hash.new
nodes.each do |n|
num_paths_from_each_node = rand(3) + 1
next_nodes = Array.new
num_paths_from_each_node.times do
next_nodes << nodes[rand(nodes.length)]
end
next_nodes.uniq!
@paths[n] = next_nodes
end
arr = Array.new
@paths.each do |key,vals|
@paths[key].each do |val|
arr << [key,val]
end
end
@dg = DiGraph.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 = 0
if (@paths[node])
@paths[node].each_index do |next_idx|
next_node = @paths[node][next_idx]
@paths[node].delete_at(next_idx)
tmp = 1 + search(next_node)
@paths[node].insert(next_idx,next_node)
if (longest_path < tmp)
longest_path = tmp
end
end
end
return longest_path
end
def find(start,last)
next_nodes = Array.new
next_nodes << start
visited = {}
while (not next_nodes.empty?)
next_node = next_nodes.shift
next if visited[next_node]
visited[next_node] = true
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 = Array.new
nodes_hash = Hash.new
already_seen = Hash.new
queue = [node]
while (not queue.empty?)
next_node = queue.shift
next if already_seen[next_node]
already_seen[next_node] = true
@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] = true
elsif (find(next_next_node,next_node))
# make sure there is a reverse path
queue << next_next_node
nodes_hash[next_node] = true
nodes_hash[next_next_node] = true
end
end
end
nodes = nodes_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 = search(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 = DiGraph.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
------=_Part_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 != self.size)
return false
end
# XXX: Must be better way to initialize @path_strs. Perhaps using initialize method?
if (not @path_strs)
g_str = self.to_s
@paths_strs = Hash.new
g_arr = g_str.split(/[,\[\]]/)
g_arr.shift
g_arr.each do |s|
s.strip!
@paths_strs[s] = 1
end
end
g_str = g.to_s
g_arr = g_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 = DiGraph.new
assert_kind_of(DiGraph, dg1)
assert_equal(0, dg1.size)
end
def test_02_size
dg2 = DiGraph.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 = Array.new
# 10 nodes total
10.times do
nodes << rand(10)
end
nodes.uniq!
@paths = Hash.new
nodes.each do |n|
num_paths_from_each_node = rand(3) + 1
next_nodes = Array.new
num_paths_from_each_node.times do
next_nodes << nodes[rand(nodes.length)]
end
next_nodes.uniq!
@paths[n] = next_nodes
end
arr = Array.new
@paths.each do |key,vals|
@paths[key].each do |val|
arr << [key,val]
end
end
@dg = DiGraph.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 = 0
if (@paths[node])
@paths[node].each_index do |next_idx|
next_node = @paths[node][next_idx]
@paths[node].delete_at(next_idx)
tmp = 1 + search(next_node)
@paths[node].insert(next_idx,next_node)
if (longest_path < tmp)
longest_path = tmp
end
end
end
return longest_path
end
# find whether there is a path from node start to last
def find(start,last)
next_nodes = Array.new
next_nodes << start
visited = {}
while (not next_nodes.empty?)
next_node = next_nodes.shift
next if visited[next_node]
visited[next_node] = true
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 = Array.new
nodes_hash = Hash.new
already_seen = Hash.new
queue = [node]
while (not queue.empty?)
next_node = queue.shift
next if already_seen[next_node]
already_seen[next_node] = true
@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] = true
elsif (find(next_next_node,next_node))
# make sure there is a reverse path
queue << next_next_node
nodes_hash[next_node] = true
nodes_hash[next_next_node] = true
end
end
end
nodes = nodes_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 = search(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 = DiGraph.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 = DiGraph.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 = Hash.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 = DiGraph.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 = DiGraph.new([5,9],[0,3],[3,8],[8,9],[9,0])
@paths = Hash.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 = DiGraph.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 = DiGraph.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 = Hash.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 = DiGraph.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
------=_Part_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 = edges.flatten.uniq
@edges = edges.select {|e| e.length == 2}
@adjacency_list = calc_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 ||= self.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 = nodes_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 = 0
adj.each do |an|
if (not visited[node] or not visited[node][an])
if (not visited[node])
visited[node] = {}
end
visited[node][an] = true
tmp = 1 + length_of_longest_path_from(an, visited)
if (max_len < tmp)
max_len = tmp
end
visited[node][an] = false
end
end
return max_len
end
protected
def depth_first_search_from(start, visited = {}, &block)
return if visited[start]
visited[start] = true
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 += newly_visited
sccs << newly_visited
numbered -= newly_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 = Hash.new {|h,k| h[k] = Array.new}
edges.each do |e|
if e.length > 1
h[e.first] << e.last
h[e.last] ||= Array.new # ensure all nodes are in the hash
end
end
h
end
end
------=_Part_19506_20929006.1144201448562--