[QUIZ] Testing DiGraph (#73)

R

Ruby Quiz

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Robert Feldt

In this week's Ruby Quiz you will not only have fun and (hopefully) learn
something; you will also contribute to a research project evaluating automated
testing techniques. So please read on and then take the quiz!

The goal of this quiz is to write a good and extensive test suite for a Ruby
DiGraph (directed graph) class. The new (hotshot, and annoying ;)) quality
manager at your work has challenged all the developers. He is planning major
cutbacks since he claims that automated testing tools can do as good or better a
job! The focus of the testing is on the following two methods of the DiGraph
class:

# Return the length of the longest simple path (an arc/edge can only
# occur once in the path) that includes <node>.
DiGraph#max_length_of_simple_path_including_node(node)

# Returns the strongly connected component (itself a DirectedGraph)
# that includes <node>.
DiGraph#strongly_connected_component_including_node(node)

Any Ruby object can be a node in a graph and you create graphs by giving a
number of edges. Each edge is an Array with maximum two nodes where the first
node is the source node.

The quiz has two phases: first a black-box phase and then a white-box phase. In
the black-box phase you do not have access to the source code but do your
testing over the network via drb. When you are satisfied with your tests for
this phase you submit them, get the source code and start the white-box phase.
Now you can extend your test suite given the actual code, fix problems and even
refactor the code as you see fit (as long as you do not change the interface).

You need to download the file "rubyquiz73.rb" to participate in the distributed
testing:

http://rubyquiz.com/rubyquiz73.rb

After downloading and saving that file, here is how you get a reference to the
class under test (CUT):

require 'test/unit'
require 'rubyquiz73'

# You must insert your email address as <youremail> in this method call!
DiGraph = RubyQuiz73.class_under_test("<youremail>")

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...
end

Note that since we use drb for the distributed testing and we had to make some
performance trade-offs not every assertion or code might work exactly as it
would if run locally. However, most "normal" things will work.

When you consider yourself ready with the blackbox phase of the testing you
should submit your test suite. You do this by issuing the command:

ruby rubyquiz73.rb submit1 <test_filename.rb>

and giving the path to your test file. The script will get back the source code
for the class being tested and save it. You can now look at the source code and
add tests as you see fit. You can also alter and refactor the source code as
long as you do not change the interface. When you are done with this, whitebox
phase, you submit your test file and source file like so (you can add additional
files if you have split your tests over several files):

ruby rubyquiz73.rb submit2 <test_filename.rb> <src_filename.rb>

[Editor's Note: Please also send in your tests to Ruby Talk, after the spoiler
period, for use in the summary. --JEG2]

You can also get some help information by issuing:

ruby rubyquiz73.rb help

You are encouraged to briefly document (in comments or by other means) how and
why you arrived at and included the test cases you've chosen and why you think
your tests are thorough. You are also encouraged to add tests for additional
methods of the DiGraph class as you see fit. Note that the devious Quality
Manager has not eliminated all problems with the given code so you are expected
to find problems/faults!

If the specifications in the RDoc comments above are not complete enough then
please make additional, sound assumptions and make them clear in your tests /
documentation.

http://www.cs.odu.edu/~toida/nerzic/content/digraph/definition.html

http://www.nist.gov/dads/HTML/stronglyConnectedCompo.html
 
J

James Edward Gray II

by Robert Feldt

In this week's Ruby Quiz you will not only have fun and (hopefully)
learn
something; you will also contribute to a research project
evaluating automated
testing techniques. So please read on and then take the quiz!

No takers on this one? You guys obviously have no idea how much
effort Robert put into setting this up... :(

James Edward Gray II
 
K

Kev Jackson

James said:
No takers on this one? You guys obviously have no idea how much
effort Robert put into setting this up... :(

I've just tried it, but I'm getting problems with my email
@it.fts-vn.com - the '-' isn't recognized in the self.valid_email?
method, small alteration to regexp fixed that, now I have firewall
issues here - off to speak to the network people.... I'm suprised too.
Normally I get in after the weekend and browse through everyones
solutions to learn more ruby, but this Monday, nothing.

Still I'll give it a try and see what I can do (probably not a lot,
still learning ruby)

Kev
 
M

Matthew Moss

No takers on this one? You guys obviously have no idea how much
effort Robert put into setting this up... :(


Apologies... Maybe it was the density of the problem (or the density
of my head), but I really didn't have a clue as to what was being
asked. And as I usually avoid the longer ruby quizzes due to time, I
made no attempt.
 
H

Himadri Choudhury

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

I don't quite understand what is being passed to new
dg2 =3D DiGraph.new([1,2], [2,3])

If I try to pass an array of arrays to new, it doesn't work.
Is there a way to use reflection to figure this out?

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion.


-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D

by Robert Feldt

In this week's Ruby Quiz you will not only have fun and (hopefully) learn
something; you will also contribute to a research project evaluating
automated
testing techniques. So please read on and then take the quiz!

The goal of this quiz is to write a good and extensive test suite for a
Ruby
DiGraph (directed graph) class. The new (hotshot, and annoying ;)) qualit= y
manager at your work has challenged all the developers. He is planning
major
cutbacks since he claims that automated testing tools can do as good or
better a
job! The focus of the testing is on the following two methods of the
DiGraph
class:

# Return the length of the longest simple path (an arc/edge can
only
# occur once in the path) that includes <node>.
DiGraph#max_length_of_simple_path_including_node(node)

# Returns the strongly connected component (itself a
DirectedGraph)
# that includes <node>.
DiGraph#strongly_connected_component_including_node(node)

Any Ruby object can be a node in a graph and you create graphs by giving = a
number of edges. Each edge is an Array with maximum two nodes where the
first
node is the source node.

The quiz has two phases: first a black-box phase and then a white-box
phase. In
the black-box phase you do not have access to the source code but do your
testing over the network via drb. When you are satisfied with your tests
for
this phase you submit them, get the source code and start the white-box
phase.
Now you can extend your test suite given the actual code, fix problems an= d
even
refactor the code as you see fit (as long as you do not change the
interface).

You need to download the file "rubyquiz73.rb" to participate in the
distributed
testing:

http://rubyquiz.com/rubyquiz73.rb

After downloading and saving that file, here is how you get a reference t= o
the
class under test (CUT):

require 'test/unit'
require 'rubyquiz73'

# You must insert your email address as <youremail> in this metho= d
call!
DiGraph =3D RubyQuiz73.class_under_test("<youremail>")

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

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

# Add/write your own tests here...
end

Note that since we use drb for the distributed testing and we had to make
some
performance trade-offs not every assertion or code might work exactly as
it
would if run locally. However, most "normal" things will work.

When you consider yourself ready with the blackbox phase of the testing
you
should submit your test suite. You do this by issuing the command:

ruby rubyquiz73.rb submit1 <test_filename.rb>

and giving the path to your test file. The script will get back the sourc= e
code
for the class being tested and save it. You can now look at the source
code and
add tests as you see fit. You can also alter and refactor the source code
as
long as you do not change the interface. When you are done with this,
whitebox
phase, you submit your test file and source file like so (you can add
additional
files if you have split your tests over several files):

ruby rubyquiz73.rb submit2 <test_filename.rb> <src_filename.rb>

[Editor's Note: Please also send in your tests to Ruby Talk, after the
spoiler
period, for use in the summary. --JEG2]

You can also get some help information by issuing:

ruby rubyquiz73.rb help

You are encouraged to briefly document (in comments or by other means) ho= w
and
why you arrived at and included the test cases you've chosen and why you
think
your tests are thorough. You are also encouraged to add tests for
additional
methods of the DiGraph class as you see fit. Note that the devious Qualit= y
Manager has not eliminated all problems with the given code so you are
expected
to find problems/faults!

If the specifications in the RDoc comments above are not complete enough
then
please make additional, sound assumptions and make them clear in your
tests /
documentation.


http://www.cs.odu.edu/~toida/nerzic/content/digraph/definition.html

http://www.nist.gov/dads/HTML/stronglyConnectedCompo.html

------=_Part_13059_32825444.1144122587653--
 
L

Lutz Horn

Hi,

* Kev Jackson:
I've just tried it, but I'm getting problems with my email
@it.fts-vn.com - the '-' isn't recognized in the self.valid_email?
method, small alteration to regexp fixed that,

Same here. '-' should be included in the email regexp.
now I have firewall
issues here - off to speak to the network people.... I'm suprised too.

Dito, the message being:

Could not connect to druby://pronovomundo.com:2000
Could not connect to druby://aquas.htu.se:8954

And there is no way to open these ports in the firewall :(

Sorry, but I can't work on this interesting problem.

Regards
 
R

Robert Feldt

Hi,

* Kev Jackson:

Same here. '-' should be included in the email regexp.
Sorry about that bug. Will fix
Dito, the message being:

Could not connect to druby://pronovomundo.com:2000
Could not connect to druby://aquas.htu.se:8954

And there is no way to open these ports in the firewall :(

Sorry, but I can't work on this interesting problem.
If I can find a server were I can use port 80 it should work for you?
If so I'll try to set it up. I'm in academia where these things tends
to be less controlled so I didn't think about the common situation
when in the commercial world... ;)

If there is enough interest I would like to extend this quiz so that
more people can make a stab at it before we summarize.

Regards,

Robert Feldt
 
R

Robert Dober

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

I got through the black box phase, but I did not make it through the white
box phase.
Just could not get the time assigned to.
Really sorry for Robert that nobody had, but maybe this weekend?

Cheers
Robert



--
Deux choses sont infinies : l'univers et la b=EAtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

------=_Part_10842_20468120.1144137191173--
 
R

Robert Feldt

I got through the black box phase, but I did not make it through the whit= e
box phase.
Just could not get the time assigned to.
I understand that; thanks for your efforts. I really tried to take a
"small" example to keep the time down but it has to have at least the
potential for some interesting quirks/situations and thus cannot be
too simple or trivial. It is a hard balance to strike.
Really sorry for Robert that nobody had, but maybe this weekend?
I sure hope so; the servers will keep running and I'll try to migrate
one of them to port 80.

Regards,

Robert Feldt
 
H

Himadri Choudhury

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

Perhaps I can ask this in another way. Is it possible to pass a variable
collection of paths to create a DiGraph?

I don't quite understand what is being passed to new
dg2 =3D DiGraph.new([1,2], [2,3])

If I try to pass an array of arrays to new, it doesn't work.
Is there a way to use reflection to figure this out?

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this qui= z
until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion.


-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=
=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D
by Robert Feldt

In this week's Ruby Quiz you will not only have fun and (hopefully) learn
something; you will also contribute to a research project evaluating
automated
testing techniques. So please read on and then take the quiz!

The goal of this quiz is to write a good and extensive test suite for a
Ruby
DiGraph (directed graph) class. The new (hotshot, and annoying ;)) quality
manager at your work has challenged all the developers. He is planning
major
cutbacks since he claims that automated testing tools can do as good or
better a
job! The focus of the testing is on the following two methods of the
DiGraph
class:

# Return the length of the longest simple path (an arc/edge can
only
# occur once in the path) that includes <node>.
DiGraph#max_length_of_simple_path_including_node(node)

# Returns the strongly connected component (itself a
DirectedGraph)
# that includes <node>.
DiGraph#strongly_connected_component_including_node(node)

Any Ruby object can be a node in a graph and you create graphs by givin=
g
a
number of edges. Each edge is an Array with maximum two nodes where the
first
node is the source node.

The quiz has two phases: first a black-box phase and then a white-box
phase. In
the black-box phase you do not have access to the source code but do your
testing over the network via drb. When you are satisfied with your test= s
for
this phase you submit them, get the source code and start the white-box
phase.
Now you can extend your test suite given the actual code, fix problems and
even
refactor the code as you see fit (as long as you do not change the
interface).

You need to download the file "rubyquiz73.rb" to participate in the
distributed
testing:

http://rubyquiz.com/rubyquiz73.rb

After downloading and saving that file, here is how you get a reference to
the
class under test (CUT):

require 'test/unit'
require 'rubyquiz73'

# You must insert your email address as <youremail> in this method
call!
DiGraph =3D RubyQuiz73.class_under_test("<youremail>")

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

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

# Add/write your own tests here...
end

Note that since we use drb for the distributed testing and we had to make
some
performance trade-offs not every assertion or code might work exactly a= s
it
would if run locally. However, most "normal" things will work.

When you consider yourself ready with the blackbox phase of the testing
you
should submit your test suite. You do this by issuing the command:

ruby rubyquiz73.rb submit1 <test_filename.rb>

and giving the path to your test file. The script will get back the source
code
for the class being tested and save it. You can now look at the source
code and
add tests as you see fit. You can also alter and refactor the source code
as
long as you do not change the interface. When you are done with this,
whitebox
phase, you submit your test file and source file like so (you can add
additional
files if you have split your tests over several files):

ruby rubyquiz73.rb submit2 <test_filename.rb> <src_filename.rb>

[Editor's Note: Please also send in your tests to Ruby Talk, after the
spoiler
period, for use in the summary. --JEG2]

You can also get some help information by issuing:

ruby rubyquiz73.rb help

You are encouraged to briefly document (in comments or by other means) how
and
why you arrived at and included the test cases you've chosen and why yo= u
think
your tests are thorough. You are also encouraged to add tests for
additional
methods of the DiGraph class as you see fit. Note that the devious Quality
Manager has not eliminated all problems with the given code so you are
expected
to find problems/faults!

If the specifications in the RDoc comments above are not complete enoug= h
then
please make additional, sound assumptions and make them clear in your
tests /
documentation.


http://www.cs.odu.edu/~toida/nerzic/content/digraph/definition.html

http://www.nist.gov/dads/HTML/stronglyConnectedCompo.html

------=_Part_14263_12843638.1144141611594--
 
R

Robert Feldt

Perhaps I can ask this in another way. Is it possible to pass a variable
collection of paths to create a DiGraph?
I don't understand what you mean by "variable collection".

DiGraph.new([1,2]) create a DiGraph like so

1 -> 2

and DiGraph.new([1,2], [2,3]) creates a DiGraph like so

1 -> 2 -> 3

Does this help?

Regards,

Robert
 
H

Himadri Choudhury

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

Then you have to manually enter all the edges?
I wanted to be able to pass an array of edges, so that the array can be
generated programmatically.



Perhaps I can ask this in another way. Is it possible to pass a variabl= e
collection of paths to create a DiGraph?
I don't understand what you mean by "variable collection".

DiGraph.new([1,2]) create a DiGraph like so

1 -> 2

and DiGraph.new([1,2], [2,3]) creates a DiGraph like so

1 -> 2 -> 3

Does this help?

Regards,

Robert

------=_Part_14363_32064191.1144143740588--
 
R

Robert Feldt

Then you have to manually enter all the edges?
I wanted to be able to pass an array of edges, so that the array can be
generated programmatically.
Well this is valid in Ruby and should give a hint (notch, notch):

def m(*a)
p a
end

m(1, 2) # =3D> [1,2]
a =3D [3,4]
m(*a) # =3D> [3,4]

Best Regards,

Robert
 
P

Paul Novak

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

This is a very interesting quiz, but it takes some time just to understand
the problem domain, if it is new to you. I second the idea of extending
this quiz.

Regards,

Paul.

Then you have to manually enter all the edges?
I wanted to be able to pass an array of edges, so that the array can be
generated programmatically.
Well this is valid in Ruby and should give a hint (notch, notch):

def m(*a)
p a
end

m(1, 2) # =3D> [1,2]
a =3D [3,4]
m(*a) # =3D> [3,4]

Best Regards,

Robert

------=_Part_3266_22134291.1144148131103--
 
J

James Edward Gray II

When you consider yourself ready with the blackbox phase of the
testing you
should submit your test suite. You do this by issuing the command:

ruby rubyquiz73.rb submit1 <test_filename.rb>

For this phase, I decided to just try some common sense tests and
stop whenever something that looked like a bug. Here's my set of
tests so far:

require 'test/unit'
require 'rubyquiz73'

DiGraph = RubyQuiz73.class_under_test("(e-mail address removed)")

class TestDiGraph < Test::Unit::TestCase
def test_construction
graph = nil
assert_nothing_raised(Exception) { graph = DiGraph.new }
assert_not_nil(graph)
assert_kind_of(DiGraph, graph)

assert_nothing_raised(Exception) do
graph = DiGraph.new(Array.new(rand(10)) { |i| [i * 2, i * 2 +
1] })
end
assert_not_nil(graph)
assert_kind_of(DiGraph, graph)
end

def test_size
graph = DiGraph.new
assert_equal(0, graph.size)
assert_equal(0, graph.num_edges)

graph = DiGraph.new([1,2], [2,3])
assert_equal(3, graph.size)
assert_equal(2, graph.num_edges)

graph = DiGraph.new([1,2], [2,3], [3, 2])
assert_equal(3, graph.size)
assert_equal(3, graph.num_edges)
end

def test_max_length_of_simple_path_including_node
10.times do |count|
graph_straight_line(count)
assert_equal(count, @graph.num_edges)
0.upto(count) do |i|
assert_equal(count,
@graph.max_length_of_simple_path_including_node(i))
end
end

# BUG: [0, 1], [1, 0] => 6 # there are only two edges
# 10.times do |count|
# graph_down_and_back(count)
# assert_equal(count * 2, @graph.num_edges)
# 0.upto(count) do |i|
# assert_equal( @graph.num_edges,
#
@graph.max_length_of_simple_path_including_node(i) )
# end
# end
end

def test_strongly_connected_component_including_node
10.times do |count|
graph_down_and_back(count)
0.upto(count) do |i|
scc = @graph.strongly_connected_component_including_node(i)
assert_equal(@graph.size, scc.size)
assert_equal(@graph.num_edges, scc.num_edges)
end
end

# BUG: [0, 1], [1, 2] => [0, 1], [1, 2] # one-way is not a
strong connect
# 10.times do |count|
# graph_straight_line(count)
# 0.upto(count) do |i|
# scc = @graph.strongly_connected_component_including_node(i)
# assert_equal(count.zero? ? 0 : 1, scc.size)
# assert_equal(0, scc.num_edges)
# end
# end
end

private

def straight_line( size )
Array.new(size) { |i| [i, i + 1] }
end

def graph_straight_line( size )
@graph = DiGraph.new(*straight_line(size))
end

def graph_down_and_back( size )
data = straight_line(size)
@graph = DiGraph.new(*(data + data.reverse.map { |edge|
edge.reverse }))
end
end

__END__

James Edward Gray II
 
J

James Edward Gray II

This is a very interesting quiz, but it takes some time just to
understand
the problem domain, if it is new to you. I second the idea of
extending
this quiz.

Alright, we will extend the quiz one week.

I expect to see your solution Paul. A little bird tells me that you
lead Ruby Quiz discussions for your local Ruby brigade, so you are
now officially all out of good excuses not to submit... ;)

James Edward Gray II
 
J

James Edward Gray II

For this phase, I decided to just try some common sense tests and
stop whenever something that looked like a bug. Here's my set of
tests so far:

require 'test/unit'
require 'rubyquiz73'

DiGraph = RubyQuiz73.class_under_test("(e-mail address removed)")

class TestDiGraph < Test::Unit::TestCase
def test_construction
graph = nil
assert_nothing_raised(Exception) { graph = DiGraph.new }
assert_not_nil(graph)
assert_kind_of(DiGraph, graph)

assert_nothing_raised(Exception) do
graph = DiGraph.new(Array.new(rand(10)) { |i| [i * 2, i * 2 +
1] })
end
assert_not_nil(graph)
assert_kind_of(DiGraph, graph)
end

def test_size
graph = DiGraph.new
assert_equal(0, graph.size)
assert_equal(0, graph.num_edges)

graph = DiGraph.new([1,2], [2,3])
assert_equal(3, graph.size)
assert_equal(2, graph.num_edges)

graph = DiGraph.new([1,2], [2,3], [3, 2])
assert_equal(3, graph.size)
assert_equal(3, graph.num_edges)
end

def test_max_length_of_simple_path_including_node
10.times do |count|
graph_straight_line(count)
assert_equal(count, @graph.num_edges)
0.upto(count) do |i|
assert_equal(count,
@graph.max_length_of_simple_path_including_node(i))

The above line has an error in it. Since I am creating one-way paths
here the assertion should be:

assert_equal(count - i, ... )

After seeing the code, I found this and other bugs.

James Edward Gray II
end
end

# BUG: [0, 1], [1, 0] => 6 # there are only two edges
# 10.times do |count|
# graph_down_and_back(count)
# assert_equal(count * 2, @graph.num_edges)
# 0.upto(count) do |i|
# assert_equal( @graph.num_edges,
#
@graph.max_length_of_simple_path_including_node(i) )
# end
# end
end

def test_strongly_connected_component_including_node
10.times do |count|
graph_down_and_back(count)
0.upto(count) do |i|
scc = @graph.strongly_connected_component_including_node(i)
assert_equal(@graph.size, scc.size)
assert_equal(@graph.num_edges, scc.num_edges)
end
end

# BUG: [0, 1], [1, 2] => [0, 1], [1, 2] # one-way is not a
strong connect
# 10.times do |count|
# graph_straight_line(count)
# 0.upto(count) do |i|
# scc = @graph.strongly_connected_component_including_node(i)
# assert_equal(count.zero? ? 0 : 1, scc.size)
# assert_equal(0, scc.num_edges)
# end
# end
end

private

def straight_line( size )
Array.new(size) { |i| [i, i + 1] }
end

def graph_straight_line( size )
@graph = DiGraph.new(*straight_line(size))
end

def graph_down_and_back( size )
data = straight_line(size)
@graph = DiGraph.new(*(data + data.reverse.map { |edge|
edge.reverse }))
end
end

__END__

James Edward Gray II
 
K

Kev Jackson

# BUG: [0, 1], [1, 0] => 6 # there are only two edges
# 10.times do |count|
# graph_down_and_back(count)
# assert_equal(count * 2, @graph.num_edges)
# 0.upto(count) do |i|
# assert_equal( @graph.num_edges,
#
@graph.max_length_of_simple_path_including_node(i) )
# end
# end
end
I got this result with [1,2], [2,1], the 6 really threw me off - was I
not understanding the concepts of digraph (so back to the web to check
my knowledge), or was it one of those bugs referred to in the quiz...?

Nice to know that someone else thought that this was a bug - I couldn't
get why 1=>2=>1 would have 6 edges/vertices :)

Thanks for posting the black box stuff James, I've been wondering about
those 6 vertices since yesterday!

Kev
 
H

Himadri Choudhury

------=_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&nbsp; - 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]&nbsp; 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("(e-mail address removed)")

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 = 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)
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 = 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)
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--
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,990
Messages
2,570,211
Members
46,796
Latest member
SteveBreed

Latest Threads

Top