Unit Testing Ideas for Project 3

Unit testing is a very useful technique in software engineering; it allows you to test sub-systems of large projects, to better isolate bugs, performance issues and other code problems.

Good unit testing should address at least the following general cases:

• Basic operations. Are the basic requirements of your data structure exercised by your test programs?
• Boundary conditions. Do your tests exercise the data structure at its boundary conditions, in terms of input size, extreme input values, etc.?
• Error handling. Do your tests exercise the data structure in error cases (null pointers, unexpected input, etc.)?
• Major client scenarios. Do your tests incorporate the required scenarios for your data structure’s major client systems?

Project 3 has several major sub-systems:

• A hash table, which supplies dictionary capability.
• A heap, which supplies priority queue capability, and which is a client of the dictionary.
• A graph, which supports Dijkstra’s Algorithm, and which is a client of the priority queue.

We will supply some limited test programs for these components, but you will need to implement more sophisticated unit tests for each of them.

Hash Table Unit Testing

To be supplied.

Priority Queue Unit Testing

Our priority queue test driver performs a few simple tests with integer and string inputs, but it does not test the queue under large-scale inputs, nor does it allow the user to enter arbitrary test inputs of their own choosing.

Here is a simple testing technique that could address both of these issues: 1) Allow the user to enter two integers, which you will use as the lower and upper bounds for a range of keys; 2) Generate a sorted array of all integers between the user’s chosen lower and upper bounds; 3) Randomly “shuffle” your array, then insert the randomly-shuffled integer keys into your priority queue; 4) Extract all items from your priority queue, and verify that they come out in sorted order.

Here is a simple technique for doing a random shuffle of N items: make a single linear pass through the sorted array; for entry I in the sorted array, generate a random number R between 0 and N-1, inclusive, and swap the I^th and R^th items in the array.

You should also test for other possible input conditions not covered by the random shuffle approach. For example, how does your priority queue handle multiple occurrences of a single key value? (Very important for Dijkstra’s Algorithm – why?)

Graph Unit Testing

Graphs are inherently complex data structures, so unit testing them is inherently complex. For this project, your unit tests need to verify that: 1) your graph data structure is correctly implemented, i.e. that it correctly represents adjacency of vertices and edges; 2) your implementation of Dijkstra’s Algorithm works as expected.

It helps to first verify that your code works on a simple input case (simple enough that you can verify the correct answer “by hand”).

However, you should also verify your code on large data sets, like a dense graph.

Finally, you should construct for yourself a range of “in-between” cases, by taking a subset of the data from the dense graph. These other cases might include:

• Sparse graph, containing all vertices of the dense graph, but with relatively few edges.
• Disconnected graph, consisting of two or more “islands” (subsets of vertices) not connected by an edge.

How could you use spanning tree concepts to generate such sparse and disconnected graphs?