CMSC 330, Fall 2006

Organization of Programming Languages

Project 2

Due October 12, 2006
11:59:59pm

Updates

  • Clarification: There can be at most one edge from one node to another. So if there is an edge from A to B, adding an edge from A to B again has no effect. But adding an edge from B to A does have an effect, and adds that other edge to the graph.

Introduction

Testing is an essential component of good software engineering practice. We can divide testing into two main categories. Integration testing is when you check that a program as a whole behaves correctly. For example, when we grade project 1, we will be performing integration testing: we'll treat your program as a black box, giving it various text files as input and then looking at what it writes to standard output.

Unit testing is when you check individual methods, classes, or other sub-parts of a program. For example, we might write a test case that calls x = foo(37) and then makes sure that x contains the correct result. Unit testing is very fine-grained, and unit tests are typically developed as you develop your code.

This project has three parts. First, you will develop a simple unit testing framework for Ruby, along the lines of JUnit, that will let you quickly and easily write and run unit tests. Second, you will develop a Ruby class to represent directed graphs. Third, as you develop your graph implementation, you will write unit tests for checking your implementation. We will grade your unit tests by running them against our own buggy implementations of the graph class to see if they can find the bugs.

What to Submit

Your should submit three files: runit.rb will contain your unit testing framework; graph.rb will contain your directed graph implementation; and graphtest.rb will contain test cases for your graph.

You can get a (very minimal) skeleton for runit.rb and graph.rb, along with a .submit file, at

/afs/glue.umd.edu/class/fall2006/cmsc/330/0201/public/p2.tar.gz

Part 1: A Unit Testing Framework

The first part of this project is to develop a unit testing framework, which you will store in a file called runit.rb. Before we give a detailed description of what you must write, let's begin with some examples.

Using the Framework

In our framework, a test suite is a collection of tests grouped together. Test suites are created by inheriting from the TestSuite class, which you will write. Here is a simple test suite that uses our framework to check some basic properties of addition and subtraction:

class SampleTest < TestSuite
  def testAdd
    assert_true(1+2 == 3)
  end

  def testSub
    assert_true(3-1 == 1)
  end
end

Here we create a test suite by inheriting from TestSuite. Each test case in this class is a method whose name begins with the string test. Test methods record whether the test fails or not by calling assert_true. The test case fails if running it causes assert_true to be called with a false argument; otherwise the test case succeeds.

To run a test suite, we invoke its run method, which is inherited from TestSuite:

irb> SampleTest.new.run
testSub: FAIL
testAdd: pass
1 pass, 1 FAIL, 0 EXN

The result is text output that records for each test method whether it passed, and then the last line summarizes how many tests passed, failed, or threw an exception when run.

Many times, several different test cases start from a common initial state. For example, when testing the graph class described in part 2 of this project, we might create an initial graph with nodes "A" and "B" and an edge from "A" to "B", and then want to run several different test cases. This code can be placed in a "setup" method in our framework. Since the setup code might allocate resources, our framework also has a "teardown" method that is run after each method is invoked. Here's an example:

class SampleTest2 < TestSuite
  def setup
    @x = 4
    puts "setup was called!"
  end

  def teardown
    puts "teardown was called!"
  end

  def testOne
    assert_true (@x == 4)
    @x = @x + 2
  end

  def testTwo
    assert_true (@x == 4)
    assert_true (@x - 1 == 3)
    @x = @x + 1
  end
end

irb> SampleTest2.new.run
setup was called!
teardown was called!
testTwo: pass
setup was called!
teardown was called!
testOne: pass
2 pass, 0 FAIL, 0 EXN

In this code, the setup method initializes field @x. Then each test method checks that the value of @x contains 4. Notice that the setup method is called before each test is invoked, which resets the value of @x. This example also shows that assert_true may be called multiple times in a test method. If it ever called with false as an argument, then the test is determined to have failed.

Note that by default, TestSuite has empty setup and teardown methods, and these are inherited unless the user overrides them.

Writing TestSuite

Your task for this part is to write the class TestSuite. Programmers will write test cases by inheriting from this class and invoking various methods. Your TestSuite class must have at least the following methods (it may have more):

  • assert_true(x) - Subclasses invoke the assert_true method to register the result of a test. While running a test method, if assert_true(false) is ever called, then the test case continues to run to completion, but is marked as failing. If the test method reaches the end without calling assert_true(false) and without raising any exception, then the test succeeds.
  • setup and teardown - Subclasses will override these methods if they want to add setup and teardown code. The setup method should be called once before each test, and the teardown method should be called once after each test. The teardown method should be called whether or not the test succeeds. You should invoke teardown before printing out the test result. You may assume that setup and teardown never throw any exceptions. We've given you the default methods, which are empty.
  • run - Here's where the main work happens. This method invokes each of the test methods (those whose names begin with test) in the current class, in any order. The setup method is invoked before each test method, and the teardown method is invoked after each test method. For each test, run prints out one line containing the test method name, followed by a colon and one space, followed by either pass, FAIL, or EXN, depending on whether the test case passed, failed, or threw an exception. After all tests are run, run prints a summary line of the form a pass, b FAIL, c EXN, where a, b, and c indicate the number of test methods that passed, failed, and raised exceptions, respectively.

Hints:

  • This part is actually very easy to write in Ruby; most of the effort you spend will simply be in understanding what we want you to write.
  • You'll need to use reflection in order to find and invoke the test methods. This is straightforward in Ruby. You'll want to use the methods method to get an array of strings of all the method names in the class. Then you'll use the send method to invoke a method by name. For example, suppose that s = "Ruby". Then the following are equivalent: s.sub("y", "i") and s.send("sub", "y", "i"). (The name send comes from older terminology for OO programming: invoking a method m on an object o is sometimes called sending message m to o.)
  • Your TestSuite class may run the tests in any order. (It is up to the test suite designer to make sure that any order makes sense.)

Part 2: A Graph Class

Your next task is to write a class Graph that implements simple directed graphs in Ruby. Your solution should go in a file graph.rb. Your Graph class should have the following eight methods:

  • initialize - A newly constructed graph should be empty. You may or may not need to create an initialize method, depending on your implementation. Each different instance of Graph has its own nodes and edges.
  • add_node(n) - Adds a new node to the graph, identified by object n. Typically n would be something like an integer or a string. The return value of this method is unspecified (it can be anything). A graph may only have one node identified with a given object, and adding the same node more than once has no effect.
  • add_edge(from, to) - Adds an edge in the graph from the node identified by from to the node identified by to. The return value of this method is unspecified. As an example, to build a graph with two nodes and an edge between them, we might write:
    g = Graph.new
    g.add_node "A"
    g.add_node "B"
    g.add_edge("A", "B")
    
    Following the dynamic spirit of Ruby, add_edge should add the from and to nodes to the graph if they are not already present. Thus the previous code snippet could also be written as
    g = Graph.new
    g.add_edge("A", "B")
    
    A graph may have only a single edge from one node to another, and adding the same edge a second time has no effect.
  • has_node?(n) - Returns true if n has been added to the graph, via either a call to add_node or add_edge, and false otherwise.
  • has_edge?(from, to) - Returns true if the graph has an edge from from to to, and false otherwise.
  • remove_node(n) - Removes the node identified by object n from the graph. This should remove all incoming and outgoing edges from n as well. Throws an exception if there is no such node in the graph. (You may throw any exception you like.)
  • remove_edge(from, to) - Removes the edge from from to to, and throws an exception if there is no such edge in the graph. (You may throw any exception you like.)
  • find_path(from, to) - Returns an array [n1, n2,..., nk] such that n1 == from, nk == to, and there is an edge from ni to ni+1 for all i. If there is more than one path, it may return any path. If from==to, this method may return []. If there is no path, returns nil.
Hint: You may assume that any object used as a node has a sensible hash method, and you should compare such objects with == if you need.

Part 3: Testing the Graph Class

Your last task is to develop a set of unit tests for Graph. Write a class GraphTest < TestSuite and put it in a file graphtest.rb. Your class should have a series of test methods that check for correct behavior of the graph class. (It probably makes sense to develop your test suite as you implement Graph.)

We will test GraphTest by running it against various buggy implementations of Graph. You will receive points for a particular buggy implementation if you have at least one test method such that (1) that method succeeds on a correct implementation of Graph and (2) that method fails on the buggy implementation. For example, you won't get any points for a GraphTest class that fails all Graph classes.

As a general principle, and also because of the way grading works, we recommend that GraphTest contain many small test methods. That way if one of them happens to have an error (i.e., it fails a correct implementation), there's still a good chance you might detect the buggy implementations with some of your other tests. In other words, don't write just one testEverything method that has lots of calls to assert_true -- write lots of little methods instead.

Warning: We will evaluate graphtest.rb using our own solution for part 1 above. Thus, you may not add any special features to TestSuite to support your graph tests.

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.

Valid HTML 4.01!