Asp Forum - [QUIZ] Testing DiGraph (#73

James Gray

3/31/2006 2:31:00 PM

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

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/rub...

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/defin...

http://www.nist.gov/dads/HTML/stronglyConnected...

18 Answers

James Gray

4/4/2006 1:38:00 AM

On Mar 31, 2006, at 8:30 AM, Ruby Quiz wrote:

> 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

Kev Jackson

4/4/2006 2:09:00 AM

James Edward Gray II wrote:

> On Mar 31, 2006, at 8:30 AM, Ruby Quiz wrote:
>
>> 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... :(

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

matthew.moss.coder

4/4/2006 3:42:00 AM

On 4/3/06, James Edward Gray II <james@grayproductions.net> wrote:
> On Mar 31, 2006, at 8:30 AM, Ruby Quiz wrote:
>
> > 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... :(

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.

Himadri Choudhury

4/4/2006 3:50:00 AM

I don't quite understand what is being passed to new

>> dg2 = 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?

On 3/31/06, Ruby Quiz <james@grayproductions.net> wrote:
>
> 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.rub...
>
> 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/rub...
>
> 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/defin...
>
> http://www.nist.gov/dads/HTML/stronglyConnected...
>
>

Lutz Horn

4/4/2006 6:55:00 AM

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

Robert Feldt

4/4/2006 7:49:00 AM

On 4/4/06, Lutz Horn <dev-random@arcor.de> wrote:
> 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.
>
Sorry about that bug. Will fix

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

Robert Dober

4/4/2006 7:53:00 AM

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êtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

Robert Feldt

4/4/2006 7:58:00 AM

On 4/4/06, Robert Dober <robert.dober@gmail.com> wrote:
> 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.
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

Himadri Choudhury

4/4/2006 9:07:00 AM

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

On 4/3/06, Himadri Choudhury <hchoudh@gmail.com> wrote:
>
> I don't quite understand what is being passed to new
>
> >> dg2 = 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?
>
> On 3/31/06, Ruby Quiz <james@grayproductions.net> wrote:
> >
> > 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.rub...
> >
> > 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/rub...
> >
> > 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/defin...
> >
> > http://www.nist.gov/dads/HTML/stronglyConnected...
> >
> >
>
>

Robert Feldt

4/4/2006 9:22:00 AM

On 4/4/06, Himadri Choudhury <hchoudh@gmail.com> wrote:
> 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

comp.lang.ruby

[QUIZ] Testing DiGraph (#73

James Gray

James Gray

Kev Jackson

matthew.moss.coder

Himadri Choudhury

Lutz Horn

Robert Feldt

Robert Dober

Robert Feldt

Himadri Choudhury

Robert Feldt

x Login to ForumsZone