Starting from:
$30
Project 4: Graphic Violence Solved
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 don't care if the problem is computationally infeasible to solve! They are willing to wait for a brute force solution. And, if you don't 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.
Let's list the things you're going to need to be able to do.
Loading the Graph
You will need to open the file specified by the user and read in a representation of an undirected graph.
Display a Menu
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.
Is Connected
You will need to determine whether or not the graph is connected.
Minimum Spanning Tree
If the graph is connected, you will need to find a minimum spanning tree for the graph and print an error otherwise.
Shortest Path
Prompt 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.
Is Metric
You will need to determine whether or not the graph is metric.
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.
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
Approximate TSP
If 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.
6
2 1 5 5 6
2 0 5 2 3
3 1 3 3 4 5 2
2 2 4 4 5
2 3 5 5 7
3 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:
Is Connected
Minimum Spanning Tree
Shortest Path
Is Metric
Make Metric
Traveling Salesman Problem
Approximate TSP
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 Connected
2. Minimum Spanning Tree
3. Shortest Path
4. Is Metric
5. Make Metric
6. Traveling Salesman Problem
7. Approximate TSP
8. Quit
Make 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.
6
1 1 5
2 0 5 2 3
3 1 3 3 4 5 2
2 2 4 4 5
1 3 5
1 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): 0
0: (0) 0
1: (5) 0 - 1
2: (8) 0 - 1 - 2
3: (12) 0 - 1 - 2 - 3
4: (13) 0 - 5 - 4
5: (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:
The graph must be completely connected
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.
6
5 1 5 2 8 3 12 4 13 5 6
5 0 5 2 3 3 7 4 12 5 5
5 0 8 1 3 3 4 4 9 5 2
5 0 12 1 7 2 4 4 5 5 6
5 0 13 1 12 2 9 3 5 5 7
5 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:
Find a minimum spanning tree for the graph
Make a tour by doubling all the edges of the minimum spanning tree
Convert the tour to a Hamiltonian tour by shortcutting past some nodes (sounds messy, but it's 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, you'll 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. It's 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.
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 don't care if the problem is computationally infeasible to solve! They are willing to wait for a brute force solution. And, if you don't 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.
Let's list the things you're going to need to be able to do.
Loading the Graph
You will need to open the file specified by the user and read in a representation of an undirected graph.
Display a Menu
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.
Is Connected
You will need to determine whether or not the graph is connected.
Minimum Spanning Tree
If the graph is connected, you will need to find a minimum spanning tree for the graph and print an error otherwise.
Shortest Path
Prompt 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.
Is Metric
You will need to determine whether or not the graph is metric.
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.
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
Approximate TSP
If 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.
6
2 1 5 5 6
2 0 5 2 3
3 1 3 3 4 5 2
2 2 4 4 5
2 3 5 5 7
3 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:
Is Connected
Minimum Spanning Tree
Shortest Path
Is Metric
Make Metric
Traveling Salesman Problem
Approximate TSP
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 Connected
2. Minimum Spanning Tree
3. Shortest Path
4. Is Metric
5. Make Metric
6. Traveling Salesman Problem
7. Approximate TSP
8. Quit
Make 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.
6
1 1 5
2 0 5 2 3
3 1 3 3 4 5 2
2 2 4 4 5
1 3 5
1 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): 0
0: (0) 0
1: (5) 0 - 1
2: (8) 0 - 1 - 2
3: (12) 0 - 1 - 2 - 3
4: (13) 0 - 5 - 4
5: (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:
The graph must be completely connected
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.
6
5 1 5 2 8 3 12 4 13 5 6
5 0 5 2 3 3 7 4 12 5 5
5 0 8 1 3 3 4 4 9 5 2
5 0 12 1 7 2 4 4 5 5 6
5 0 13 1 12 2 9 3 5 5 7
5 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:
Find a minimum spanning tree for the graph
Make a tour by doubling all the edges of the minimum spanning tree
Convert the tour to a Hamiltonian tour by shortcutting past some nodes (sounds messy, but it's 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, you'll 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. It's 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.
1 file (11.7KB)
