From: Ruby Quiz <james@...>
Date: 2006-03-31T23:30:54+09:00
Subject: [QUIZ] Testing DiGraph (#73)

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