Lots of software systems need to be able to compute the shortest path through a graph. For example, in various high-traffic portions of the Internet, protocols such as OSPF and IS-IS require each computer in the network to keep track of a complete (though possibly obsolete) graph of the network, and to route each packet along the shortest paths to its destination. Similarly, you can solve "six degrees of separation" sorts of problems and compute MapQuest-style directions via shortest-path graph computations.
If you wrote an implementation of a shortest-path algorithm (such as Dijkstra's algorithm or the Bellman-Ford algorithm), you would probably embed it in some sort of command-line program that would read a graph from a file and perform requested path computations. Let's imagine a program with a command-line syntax like this:
pathfinder graphfile pathrequestfile
where "graphfile" is the name of a file containing a textual representation of the graph, and "pathrequestfile" contains a list of shortest paths you want to compute. The graph file's format will be as in this example:
# Blank lines and lines beginning with '#' are ignored, # and leading and trailing spaces should be eliminated. # Lines not containing a colon are names of nodes. Minneapolis Chicago Rapid City Des Moines # Lines containing colons are edges, with two node names and # the edge's distance (weight). Minneapolis : Chicago : 362 Rapid City : Minneapolis : 483 Minneapolis : Omaha : 289 Omaha : Chicago : 436 Omaha : Rapid City : 414
The request file's format will be:
# Blank lines and lines beginning with '#' are ignored. # There's one request per line, consisting of a pair of node names, # separated by a colon. Chicago : Rapid City Chicago : Omaha
The output should go to standard output, and should look like this, showing each shortest path from end to end, with nodes separated by colons, and ending with the total distance.
Chicago : Minneapolis : Rapid City : 845 Chicago : Omaha : 436
For this assignment, you will not be writing the pathfinder program described above. Instead, you will develop a set of test cases and a way of applying them automatically. In addition to sample input and the corresponding expected output, you may wish to write a program that runs the tests. Alternatively, you may be able to find a combination of standard Unix tools that will run the tests for you. In any case, your goal in constructing your testing infrastructure will be to make it very easy to run the tests. Ideally, I should be able to cd to an appropriate directory, type a single command, and then see a collection of reports on the various tests. These reports should be easy to read and understand.
You should hand in a directory named "pathfindertest", containing all the files involved in your testing system. This directory should also include a file named readme.txt that describes in detail (1) how to use your testing system, (2) what kinds of test cases you have designed and why, and (3) anything else you think I should know.
Be creative. You want to devise a system that will be easy to use and also good at ferretting out lots of sneaky bugs in the pathfinder program. Keep in mind that you will want to test not just for incorrect computation of shortest paths, but also for mishandling of badly formatted input files. (For example, pathfinder should warn the user if the graph file or the path request file is incorrectly formatted.)
Have fun.