Project 2

Introduction

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

Part 1: A Unit Testing Framework (30 points)

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"}

The result is a Hash that records for each test method whether it 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!
setup was called!
teardown was called!
=> {"testOne"=>"pass", "testTwo"=>"pass"}

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 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 creates an entry in a hash with the name of the test as the key and a string pass, FAIL, or EXN as the value, depending on whether the test case passed, failed, or threw an exception. After all tests are run, run returns the hash.

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 (30 points)

Your next task is to write a class Graph that implements simple 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(v) - Adds a new node to the graph, identified by object v. Typically v 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(u, v) - Adds an edge in the graph connecting the nodes u and v. 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 u and v 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 connecting any two nodes, and adding the same edge a second time has no effect. The order of the arguments u and v is interchangeable, that is, calling G.add_edge(u, v) is the same as calling G.add_edge(v, u).
• has_node?(v) - Returns true if v has been added to the graph, via either a call to add_node or add_edge, and false otherwise.
• has_edge?(u, v) - Returns true if the graph has an edge connecting u and v, and false otherwise.
• remove_node(v) - Removes the node identified by object v from the graph. This should remove all edges that are incident to v as well. Throws an exception if there is no such node in the graph. (You may throw any exception you like.)
• remove_edge(u, v) - Removes the edge connecting u and v, 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 of distinct nodes [n1, n2, ... , nk] such that n1 == from, nk == to, and there is an edge between ni and ni+1 for all i. If there is more than one path, it may return any path. If from==to, this method may return []. Returns nil if there is no path, or either path endpoint is not a node in the graph.

Part 3: Testing the Graph Class (40 points)

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. Also, do not call require "Graph.rb" inside your graphtest.rb file.

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.