For this assignment, you are to start by defining an abstract class A5Graph that has methods as given below, and inherits from the abstract class Graph, which is provided for you on the class web site. Note that the Graph class implements the Combiner interface, which is also provided for you on the class web site. The A5Graph class needn't implement the methods of the Combiner interface, but it should implement the other abstract methods of the Graph class. It should also have a constructor that takes a 2-dimensional array of Objects and constructs the graph that would the given array as its adjacency matrix. This constructor needn't clone the array. The A5Graph class should also determine a representation with appropriate instance variables.

You are also to define classes TransitivizerGraph, PathCounterGraph, FloydGraph, NaiveAllPairsGraph, and FloydPathGraph, that inherit from A5Graph, and also implement the methods of the Combiner interface. You may assume that the entries of the first of these classes are instances of the Boolean class, and that the entries of next three are instances of the Integer class. For A5Graph, the elements should be arbitrary Objects.

The FloydGraph, FloydPathGraph, and NaiveAllPairsGraph classes are to have a method allpairs that uses the combine method to solve the all-pairs shortest paths problem. The first two of these should use Floyd's algorithm; the third should find the shortest paths of length 1, 2, 3, etc. For each class, this method is to return an object of that class, and is to have a boolean parameter. The graph resulting from each pass is to be printed iff the corresponding argument has value true. Note that a static print method is provided for Graphs as part of the A5 class; you may use this method to do the printing.

The difference between the FloydGraph andFloydPathGraph classes is that the second of these should return enough information to reconstruct the path, rather than just its cost. So each entry in a FloydPathGraph graph should have path information as well as Integer cost information.

The combine method, when applied to an instance of the PathCounter class, is to compute the number of paths of length r + s between any two vertices, given graphs that store the number of paths of length r and s respectively. Note that the corresponding computation is identical to ordinary matrix multiplication. Similarly, instances of the TransitivizerGraph class are to determine whether there are any paths between two vertices of length at most r, so that the combine method should be able to take two such graphs for lengths r and s, and construct a result that determines which two vertices are connected by a path of length at most r + s. For full credit, your combine method should have O(n²) time complexity when applied to instances of FloydGraph andFloydPathGraph. It should have O(n³) time complexity in all other cases. The getEntry, getRow, and getColumn methods should have O(1) time complexity (so they shouldn't involve copying of an entire row or column). One way to achieve this time complexity is to have two adjacency matricies that are transpositions of each other.

Use the test file A5.java (available on the class web site) to test your implementation. Also use the Graph.java and Combiner.java file provided on that web site.