Forum: Ruby Testing DiGraph (#73)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2006-03-31 18:32
(Received via mailing list)
The three rules of Ruby Q.:

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 Q. 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 T. follow the discussion.

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

by Robert F.

In this week's Ruby Q. 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 T., 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/digrap...

	http://www.nist.gov/dads/HTML/stronglyConnectedCompo.html
James G. (Guest)
on 2006-04-04 05:39
(Received via mailing list)
On Mar 31, 2006, at 8:30 AM, Ruby Q. wrote:

> by Robert F.
>
> In this week's Ruby Q. 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 G. II
Kev J. (Guest)
on 2006-04-04 06:09
(Received via mailing list)
James Edward G. II wrote:

>
> 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 M. (Guest)
on 2006-04-04 07:45
(Received via mailing list)
On 4/3/06, James Edward G. II <removed_email_address@domain.invalid> wrote:
> 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 C. (Guest)
on 2006-04-04 07:51
(Received via mailing list)
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?
Lutz H. (Guest)
on 2006-04-04 10:59
(Received via mailing list)
Hi,

* Kev J.:
> 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 F. (Guest)
on 2006-04-04 11:51
(Received via mailing list)
On 4/4/06, Lutz H. <removed_email_address@domain.invalid> wrote:
> Hi,
>
> * Kev J.:
> > 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

> 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 F.
Robert D. (Guest)
on 2006-04-04 11:55
(Received via mailing list)
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 F. (Guest)
on 2006-04-04 11:58
(Received via mailing list)
On 4/4/06, Robert D. <removed_email_address@domain.invalid> 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 F.
Himadri C. (Guest)
on 2006-04-04 13:09
(Received via mailing list)
Perhaps I can ask this in another way. Is it possible to pass a variable
collection of paths to create a DiGraph?
Robert F. (Guest)
on 2006-04-04 13:25
(Received via mailing list)
On 4/4/06, Himadri C. <removed_email_address@domain.invalid> 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
Himadri C. (Guest)
on 2006-04-04 13:43
(Received via mailing list)
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.
Robert F. (Guest)
on 2006-04-04 13:49
(Received via mailing list)
On 4/4/06, Himadri C. <removed_email_address@domain.invalid> wrote:
> 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)  # => [1,2]
a = [3,4]
m(*a)    # => [3,4]

Best Regards,

Robert
Paul N. (Guest)
on 2006-04-04 14:58
(Received via mailing list)
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.
James G. (Guest)
on 2006-04-04 21:26
(Received via mailing list)
On Mar 31, 2006, at 8:30 AM, Ruby Q. wrote:

> 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("removed_email_address@domain.invalid")

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 G. II
James G. (Guest)
on 2006-04-04 21:29
(Received via mailing list)
On Apr 4, 2006, at 5:55 AM, Paul N. wrote:

> 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 Q. discussions for your local Ruby brigade, so you are
now officially all out of good excuses not to submit...  ;)

James Edward G. II
James G. (Guest)
on 2006-04-05 03:19
(Received via mailing list)
On Apr 4, 2006, at 12:24 PM, James Edward G. II wrote:

>   def test_construction
>     assert_kind_of(DiGraph, graph)
>
>         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 G. II
Kev J. (Guest)
on 2006-04-05 05:33
(Received via mailing list)
> #     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
Himadri C. (Guest)
on 2006-04-05 05:45
(Received via mailing list)
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
James G. (Guest)
on 2006-04-05 17:48
(Received via mailing list)
On Apr 4, 2006, at 12:28 PM, James Edward G. II wrote:

> On Apr 4, 2006, at 5:55 AM, Paul N. wrote:
>
>> 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.

Robert and I have discussed this off list and we feel it's better to
go ahead and move on.  There were seven submissions to the black box
phase, plus one for the whitebox.  Some people did tough it out.

The problem did come out a little harder than we intended though,
which is my fault.  Sorry about that.

Let's move on.

James Edward G. II
James G. (Guest)
on 2006-04-05 18:34
(Received via mailing list)
On Apr 4, 2006, at 6:17 PM, James Edward G. II wrote:

> The above line has an error in it.  Since I am creating one-way
> paths here the assertion should be:
>
>   assert_equal(count - i, ... )

Actually, I was right the first time.  The graph is a simple one-way
path so the longest simple route is a straight line walking all of
the edges and it includes all of the nodes.

You can tell how little I know about directed graph theory!  :)

James Edward G. II
This topic is locked and can not be replied to.