[Solved] Project 4: Graphic Violence

Introduction

An army of bellowing, enraged traveling salesmen are descending on Elizabethtown College! Their mission: To find tours that will allow them to visit all of their clients in the shortest amount of time. They dont care if the problem is computationally infeasible to solve! They are willing to wait for a brute force solution. And, if you dont give them a brute force solution, they are prepared to use brute force on you!

Overview

Your job is to write a class that can load an (undirected) graph from a file. Then, your class should support a number of options, all accessed through a text-driven menu. Your class should be called Graphs and stored in Graphs.java. You are permitted to create other helper classes if you think it would be useful. A separate class to hold the representation of a graph is not a bad idea.

Lets list the things youre going to need to be able to do.

1. 1. Loading the GraphYou will need to open the file specified by the user and read in a representation of an undirected graph.

1. 1. Display a MenuDisplay a menu the user can make choices from. Each choice will either give information about the currently loaded graph or transform it in some way.

1. 1. Is ConnectedYou will need to determine whether or not the graph is connected.

1. 1. Minimum Spanning TreeIf the graph is connected, you will need to find a minimum spanning tree for the graph and print an error otherwise.

1. 1. Shortest PathPrompt the user for a node. Then, print the lengths of the shortest paths from that node to all other nodes and the actual paths as well.

1. 1. Is MetricYou will need to determine whether or not the graph is metric.

1. 1. Make MetricA graph that is not metric can be made metric by making it a complete graph and adjusting all of its edges so that every direct edge gives the shortest path between the two connected nodes.

1. 1. Traveling Salesman ProblemUse brute force to try all possible tours starting at node 0. Print the length of the shortest one and the sequence of nodes

1. Approximate TSPIf the graph is metric, use the doubled MST method of finding a 2-approximation to TSP. Otherwise, return an error.

Loading the Graph

When your program starts, you must prompt the user for a graph file. This graph file will start with a number saying the number of nodes in the graph. Then, each line after that will correspond to a particular node. Each such line will start with a number specifying the number of edges connected to a node. The rest of the line will give a series of pairs of numbers. The first number in the pair gives the number of node that the current node is connected to. The second gives the length of the edge connecting them.

We will use the following graph for many of our examples.

The input file for this graph is as follows.

62 1 5 5 62 0 5 2 33 1 3 3 4 5 22 2 4 4 52 3 5 5 73 0 6 2 2 4 7

Display a Menu

After the graph has been loaded, display a menu the user can make choices from. Each choice will either give information about the currently loaded graph or transform it in some way.

The choices for the menu are:

1. Is Connected
2. Minimum Spanning Tree
3. Shortest Path
4. Is Metric
5. Make Metric
6. Traveling Salesman Problem
7. Approximate TSP
8. Quit

The user should be able to pick any sequence of choices repeatedly until finally selecting Quit (8).

Sample output for the menu is as follows.

1. Is Connected2. Minimum Spanning Tree3. Shortest Path4. Is Metric5. Make Metric6. Traveling Salesman Problem7. Approximate TSP8. QuitMake your choice (1 - 8):

Is Connected

If the user selects choice 1, you will need to determine whether or not the graph is connected. If the graph is connected, print Graph is connected.Otherwise print Graph is not connected.

Output for the sample graph is as follows.

Graph is connected.

Minimum Spanning Tree

If the graph is connected, you will need to find a minimum spanning tree for the graph. Otherwise, print Error: Graph is not connected. Print the MST in the same general format that is used for the graph input file.

The MST for the sample graph is as follows.

Output for the sample graph is as follows.

61 1 52 0 5 2 33 1 3 3 4 5 22 2 4 4 51 3 51 2 2

Shortest Path

Prompt the user for a node. Then, print the lengths of the shortest paths from that node to all other nodes in parentheses. For the starting node, print (0). For unreachable nodes, print (Infinity). After the length of each shortest path, print a tab and then the nodes visited in the path itself, separated by arrows. Note that you will need to keep a back pointer giving the previous node in the path as well as the best distance found so far in order to produce each shortest path.

If a user entered node 0 for this choice, the output for the sample graph would be as follows. User input is shown in green.

From which node would you like to find the shortest paths (0 - 5): 00: (0)	01: (5)	0 -> 12: (8)	0 -> 1 -> 2	3: (12) 0 -> 1 -> 2 -> 34: (13)	0 -> 5 -> 45: (6)	0 -> 5

Is Metric

You will need to determine whether or not the graph is metric. There are two conditions to be a metric graph:

1. The graph must be completely connected
2. The every edge in the graph must be obey the triangle inequality

There are three possible outputs. If the graph is not completely connected, print Graph is not metric: Graph is not completely connected. If the graph is completely connected but its edges do not obey the triangle inequality, print Graph is not metric: Edges do not obey the triangle inequality.

Output for the sample graph would be as follows:

Graph is not metric:  Graph is not completely connected.

Make Metric

A graph that is not metric can be made metric by making it a complete graph and adjusting all of its edges so that every direct edge gives the shortest path between the two connected nodes.

This choice is the only choice that changes the structure of the graph. If the graph is connected, you must add edges between every node that does not already have an edge. Then, you must set every direct edge to have the cost of the shortest path between those edges. Afterwards, print the graph data as if it were a graph input file. If the graph is not connected, print Error: Graph is not connected.

For the sample graph, the resulting graph is below. Edge weights have been omitted for clarity, but they are listed in the sample output.

65 1 5 2 8 3 12 4 13 5 65 0 5 2 3 3 7 4 12 5 55 0 8 1 3 3 4 4 9 5 25 0 12 1 7 2 4 4 5 5 65 0 13 1 12 2 9 3 5 5 75 0 6 1 5 2 2 3 6 4 7

Traveling Salesman Problem

Use brute force to try all possible tours starting at node 0. Print the length of the shortest one and the sequence of nodes it takes.

There are two possible errors. If the graph is not connected, print Error: Graph is not connected. Remember that a TSP path can only cross an edge once. If there is no path that returns to the starting node without re-crossing an edge, print Error: Graph has no tour.

The sample graph has the following (obvious) TSP tour:

For the sample graph, output is below. The length of the tour is given first, followed by a colon, followed by the sequence of nodes, separated by arrows.

30: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0

Warning: If you try this on a large problem instance, you will be waiting for the Universe to grow cold. If you execute it efficiently, you should be able to run TSP on an instance with around 30 edges. Graph structure makes a big difference.

Approximate TSP

If the graph is metric, we can approximate the best TSP tour with the following steps:

1. Find a minimum spanning tree for the graph
2. Make a tour by doubling all the edges of the minimum spanning tree
3. Convert the tour to a Hamiltonian tour by shortcutting past some nodes (sounds messy, but its really just a preorder walk, AKA depth-first traversal, of the MST)

Because the MST cannot be longer than the best TSP tour, and shortcutting past nodes in a metric graph will not increase the distance, a doubled MST means that the resulting tour is no more than twice the optimum TSP tour.

Other decent explanations of this algorithm are given here and here.

If the graph is not metric, print Error: Graph is not metric.

For our unchanged sample graph, the output would be Error: Graph is not metric. However, if we had modified the graph so that it is metric, the result would be the same as the brute force TSP. In this case, the approximation gets the optimal tour.

Note: You can compare your results against the example on this webpage. An applet there will also do this approximation. You can compare your results, but it does not allow you to enter nodes at specific locations. So, youll have to approximate your graphs in the Euclidean plane to use it. Search around. There are probably other TSP applets out there.

Hints

• • Start early. Try to work on the pieces in the order they are given to you. There is a natural dependence in many cases. For example, making the final TSP approximation is dependent on MST and making the graph metric. Making the graph metric is dependent on knowing whether or not the graph is connected.

• • You are allowed to implement the graph with an adjacency matrix or with adjacency lists. Its up to you.

• • Think before you code. 1 minute of design == 10 minutes of coding == 100 minutes of debugging.

• You may use the Java Collection Framework if you need lists, queues, or stacks. Very little there is likely to help you much. You are (naturally) forbidden from using graph libraries such as JGraph and JGraphT.