This assignment is a pure programming assignment.

Define an immutable class Graph with public methods naiveAllPairs, floydAllPairs, gtAllPairs, bfAllPairs, getSize, equals, and toString. The first four of these are to return solutions in the form of a Graph object to the all-pairs shortest path problem with the graph as an instance. The gtAllPairs method is to use the divide-and-conquer algorithm for computing the closure of Goodrich & Tamassia, Section 7.2.2. It is to return an unpadded graph. The floydAllPairs is to use the Floyd-Warshall algorithm, described in Section 7.2.1 of that text. The naiveAllPairs method is to use the approach of p. 356 of that text, which is to compute the matrices A^k directly from the definition. The bfAllPairs method is to use the Bellman-Ford algorithm (using an adjacency matrix representation) once for each vertex in the graph. It need not return an indication of whether there is a negative cost cycle. None of these four methods needs to check that its input satisfies the preconditions for correctness of its associated algorithm.

The getSize method is to return the number of vertices in the graph. It takes no argument. The toString method is to return a String representing the graph's adjacency matrix as a 2-dimensional table. It takes no argument. Note that the String to be returned by this method will consist of more than one line, so you should handle new lines in a platform-independent way. Infinite values are to be represented as asterisks. The columns of the table should be aligned. The equals method, like the toString method, is to override the method inherited from the Object class. It simply checks whether the adjacency matrices are identical.

Your class is to have a two constructors. The zero-argument constructor is to return a complete graph on 8 vertices with all edge costs being zero. For any of the Graph-valued methods whose definition you cannot complete, the method should return the Graph built by this constructor.

The second constructor is to take as its single argument a 2-dimensional array of integers, to be used as the adjacency matrix subject to the constraints of this paragraph. Infinite edge costs are to be represented by the value Integer.MAX_VALUE. The constructor is not to modify (i.e., mutate) this input array. However diagonal elements of the input array are to be replaced in the adjacency matrix by zero if they are nonzero. Otherwise, edge costs that are negative or zero are permitted and are not to be replaced. To guarantee that the adjacency matrix is square, you are to assume that the number of vertices in the graph is equal to the number of rows of the input array, with short rows padded at the end with zeros, and long rows truncated.

You may assume that all path costs are small enough to be represented as an int, unless one of its edge costs is infinite. Of course you should make sure that infinite costs are handled correctly by your arithmetic operations.

You are to test your Graph class by executing the (main method of) the A3 class, available on the class web site. You are to turn in hard and soft copies of your class definitions. You are also to turn in a hard copy of the results of your tests.

As always, you may add any other public or private methods or classes you find useful. Your private methods needn't do any error checking that is already done by your public methods (or your other private methods). Your private methods needn't try to economize on the amount of copying they do, although you should feel free to take advantage of any safe and simple way you can find to avoid copying. In this assignment it's primarily the asymptotic time complexity that's important. Of course, it's wise to look at the actual elapsed times provided by the test class as a guide to whether you're using the right approach. Do keep in mind that the elapsed times are noisy can vary considerable from run to run of the test program.

Add a method bfSinglePair to your graph class that takes a source and destination vertex and uses the Bellman-Ford algorithm to find the cheapest path from the source vertex to the desination vertex. This method is to return the path as an array of ints. If you do not do the extra credit, then make sure the given method returns an array of size 0, so that the test program will run.