CMSC 330, Fall 2008

Organization of Programming Languages

Project 2

Due October 3, 2008
11:59:59pm

Updates

  • Sep 28 Clarified that assert_true(nil) also causes the test case to fail.
  • Sep 27 Clarified that succ returns the empty array for a node that has no edges from it.
  • Sep 26 Clarified that in add_edge, there can be at most on edge between each pair of nodes. (So one node can have more than one edge from it, for example.)
  • Sep 25 Clarified that is_list? should return false if the graph is empty.
  • Sep 24 Minor remark: if a test case throws an exception at any point in execution, we count it as an exception (EXN) instead of considering that it failed or succeeded, regardless of whether assert_true was called previously.

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/fall2008/cmsc/330/0101/public/projects/p2/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. If the test case throws an exception at any point in execution, we regard it as an exception instead of as passing or failing, regardless of whether assert_true was called previously.

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 a graph with 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 is 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) or assert_true(nil) are ever called, then the test case continues to run to completion, but is marked as failing (unless it throws an exception, in which case it should be marked as EXN instead). If the test method reaches the end without calling assert_true(false), without calling assert_true(nil), 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 has no edges. You may or may not need to create an initialize method, depending on your implementation. Each different instance of Graph has its own set of edges.
  • add_edge(from, to) - Adds an edge in the graph from the node identified by from to the node identified by to. Typically from and to would be something like an integer or a string; you may use== to compare nodes, and hash to hash them. The return value of add_edge method is unspecified (it can be anything). There can be at most one edge between each pair of nodes, and adding that edge more than once has no effect. As an example, to build a graph with two nodes and an edge between them, we might write:
    g = Graph.new
    g.add_edge("A", "B")
    
    If we called g.add_edge("A", "B") again, g would be unchanged.
  • has_edge?(from, to) - Returns true if the graph has an edge from from to to, and false otherwise.
  • succ(from) - Returns an array [n1, ..., nk] containing a list of nodes such that there are edges from from to each of n1 through nk. If there are no edges from from (even if there have never been any edges added from from), returns the empty array.
  • remove_edge(from, to) - Removes the edge from from to to. Does nothing if there is no such edge in the graph. Returns true if an edge was actually removed, or false if there was no such edge.
  • has_node?(n) - Return true if there is either an edge to or from n in the graph. Note that we are following the Ruby spirit here: Rather than add nodes separately to the graph, we just add edges, and nodes are assumed to exist if they are part of an edge.
  • remove_node(n) - Removes all edges from the graph that either begin or end at n. Does nothing if there are no such edges in the graph. Returns true if a node was actually removed, or false if there was no such node.
  • each_edge { |f,t| block } - Takes a code block as an argument, and calls the code block once for each edge in the graph, passing two arguments: f is the start of the edge, and t is the end of the edge.
  • transpose! - Flips the edge directions in the graph, so that if there was an edge from "A" to "B" before, then there is now an edge from "B" to "A". Returns self.
  • is_list? - Return true if and only if the edges in the graph form an acyclic linked list. In other words, this method returns true if there is a node x0 such that succ(x0) = [x1], succ(x1) = [x2], ..., succ(xn-1) = [xn], the xi are the only nodes in the graph, and all the xi are distinct. The is_list? method should return false if the graph is empty. Hint: Make sure that if the graph has a cycle in it, your is_list? method does not go in to an infinite loop.

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!