TSPUndirectedGraph that uses an adjacency matrix to represent undirected weighted graphs. Your class should support at least the public methods hasTriangleInequalityProperty, isComplete, TSP, and NewTSPApprox, as well as the methods of the UndirectedGraph class provided on the class web site. The constructors for the TSPUndirectedGraph class should correspond to the constructors for the UndirectedGraph class. It is recommended, but not required, that your TSPUndirectedGraph class inherit from the UndirectedGraph class. As in this class, you may assume that edge costs and vertices are always integers. An edge cost of 0 is to represent a missing edge; other edge costs may assumed to be positive.
The isComplete method should return true if the graph is complete and false otherwise. The hasTriangleInequalityProperty should return a boolean value that determines whether a graph has the property of that name. It should also print a counterexample to System.out if it finds one. The format of this message is unimportant, except that it should list the 3 vertices. The TSP and NewTSPApprox methods should return actual and approximate solutions, respectively, to the TSP problem for the given graph. These solutions should consist of Lists of Edges, where the Edge class is given as part of the UndirectedGraph class. The edges should be listed in the order of their appearance in the path. The TSP may return an empty list and print an error message if it is given a graph with more than 10 vertices. It needn't work efficiently -- in fact, no efficient algorithm is known for exact solution of the TSP problem. In particular, it may use an exhaustive search of all possible permutations.
The NewTSPApprox method should first construct a solution to the minimum spanning tree problem (this is why the input graph has to be undirected). Then, starting at vertex 0, it should perform a preorder traversal of this tree (considered as an ordered tree with children ordered in numerical order). The sequence of vertices visited, together with vertex 0 at the end, will be the approximate solution.
Note that this approximation algorithm, given an input graph with the triangle inequality property, is guaranteed to return an approximation that is no more than twice the cost of the optimal TSP solution. This is because the aproximation returned, considered as a sequence of vertices, is a subsequence of an Euler tour of the directed version of the minimial spanning tree. This Euler tour has cost equal to twice the cost of the minimal spanning tree, which itself has cost less than that of a TSP solution (since removing any edge from a TSP solution gives a spanning tree). The triangle inequality property is needed so that when vertices are removed from an Euler tour, the cost of the tour does not increase.
Make sure to document the algorithms you use for your public methods, and for any important private auxiliary methods.
Use the file A5.java (available on the class web site) to test your implementation. Classes
BinaryHeap.java, PriorityQueue.java, and DisjSetsFast.java are available on the web site to support the UndirectedGraph class, and its kruskal method in particular. The main function in the class A5 sends a message GreedyTSPApprox to graphs. You are encouraged but not required to understand the corresponding method; it's just another algorithm for finding an approximate TSP solution, provided to give you something to compare your own approximation method to.
No late submissions will be accepted for this assignment.