Exercise

This project will allow you to writte a program to get more practice with the map, set and priority queue data structures. This lab will also allow you some practice with implementing algorithms of medium complexity.

need writing a program that computes the shortest path between two cities. Consider the map of the USA below. This map shows a (small) group of fights between major US cities. Each dot is a major US city. Each line is a connection between two cities. Each line also has a numeric value, representing the (approximate) flight time of a journey between the two connected cities. For example, the map below shows that a flight between Seattle, WA and Chicago, IL will take approximately 3 hours.

We can abstract the connections above off the diagram of the map into a mathematical structure known as a graph. Below is a graph model of the flight connections given above. Note that it is exactly like the model above, except that we no longer have the map underneath the cities and paths. In this model, each "dot" is known as a node. Two nodes are said to be adjacent to each other if there is a path connecting them. (So the nodes representing Seattle and Chicago are adjacent according to this defintion).

We can store information about a graph in a structure known as an adjacency list. In an adjacency list, each node has an associated list of adjacent nodes. For example, the adjacency list for the above graph (assuming that each node is named after the city is represents) would be:

Atlanta: StLouis, Dallas, Miami

Boston: Chicago, NewYork

Chicago: Columbus, NewYork, Boston, StLouis, Denver, Seattle

Columbus: Chicago, Miami

Dallas: StLouis, Atlanta, Miami, LosAngeles

Denver: Chicago, SanFrancisco, LasVegas, Seattle

LasVegas: LosAngeles, SanFrancisco, Denver

LosAngeles: Dallas, SanFrancisco, LasVegas

Miami: Columbus, Atlanta, Dallas

NewYork: Chicago, Boston

SanFrancisco: LosAngeles, LasVegas, Seattle, Denver

Seattle: Chicago, SanFrancisco, Denver

StLouis: Chicago, Atlanta, Dallas

The adjacency list can be augmented with path costs. In this case, the list contains both the name of the node and the path cost from the start node to that node:

Atlanta: (StLouis:1.0), (Dallas:1.0), (Miami:1.0)

Boston: (Chicago:2.0), (NewYork:0.5)

Chicago: (Columbus:0.5), (NewYork:1.5), (Boston:2.0), (StLouis:0.5), (Denver:2.5), (Seattle:3.0)

Columbus: (Chicago:0.5), (Miami:2.0)

Dallas: (StLouis:1.0), (Atlanta:1.0), (Miami:2.0), (LosAngeles:2.5)

Denver: (Chicago:2.5), (SanFrancisco:2.0), (LasVegas:1.0), (Seattle:2.0)

LasVegas: (LosAngeles:0.5), (SanFrancisco:1.0), (Denver:1.0)

LosAngeles: (Dallas:2.5), (SanFrancisco:1.0), (LasVegas:0.5)

Miami: (Columbus:2.0), (Atlanta:1.0), (Dallas:2.0)

NewYork: (Chicago:1.5), (Boston:0.5)

SanFrancisco: (LosAngeles:1.0), (LasVegas:1.0), (Seattle:2.0), (Denver:2.0)

Seattle: (Chicago:3.0), (SanFrancisco:2.0), (Denver:2.0)

StLouis: (Chicago:0.5), (Atlanta:1.0), (Dallas:1.0)

The shortest path cost between two nodes in a graph is the minimum cost it takes to get from one node to another. For example, there are many different paths between Chicago and Los Angeles. We could choose to travel from Chicago to Seattle, then to San Francisco, then to Las Vegas and finally to Los Angeles. This route would have a path cost of 6.5 hours. But the shortest path cost between Chicago and Los Angeles is 4.0 hours - the path from Chicago to Denver, then to Las Vegas and then to Los Angeles. Given a graph, an algorithm for finding the shortest path cost from a start node to all of the possible terminal nodes is:

Begin with our initial location and call it start.

Assume we have a data structure for Paths. A Path has two attributes - a destination name and a path cost to that destination.

Creatte an empty Map data structure named shortestDistances. This will map names to final path costs.

Creatte an empty PriorityQueue of Paths. The PriorityQueue will prioritize Paths in order of path cost.

Add the Path (start:0.0) to the PriorityQueue (representing the distance from the inital node to itself, which is always 0.0).

While the PriorityQueue is not empty:

Remove the Path with the smallest path cost from the PriorityQueue and call it current.

If the name of the node in the Path current is NOT in the shortestDistances map:

Get the distance noted in the Path current. Call it d.

Get the destination name noted in the Path current. Call it dest.

Add the pair (dest, d) to the shortestDistances map. You now have the shortest distance from the initial node to that destination.

For each node/path cost pair n in the adjacency list of the node destination:

Add a path to the priority queue (n.nodename, d + n.pathcost)

When the PriorityQueue is empty, the Map shortestDistances contains the shortest distance between your start location and every other location in the graph

Your job in this project will be to implement this algorithm for a graph like the one above. It is IMPORTANT that you work through each section step by step - do not try to jump right to coding this algorithm all at once. Get each piece working in turn before you move onto the next piece.

Project 05 Instructions

Creatte a new Project folder named Project05 and a new program named Project05.java, then look at the instructions below.

Part I - Understanding the algorithm

Before you start any coding for this project, make sure you understand the algorithm that is outlined above. Using the adjacency list above, follow the instructions for computing the shortest distance from Columbus to all of the nodes in the graph by hand in a plain text file. Show the intial setup, and each iteration of the algorithm. Show your PriorityQueue as a sorted list of paths.

As an example, here are the intial setup and first few steps showing this algorithm starting from Seattle. You should do something similar for Columbus:

Initial Setup

=============

shortestDistances: empty

PriorityQueue: (Seattle:0.0)

After Iteration 0

=================

shortestDistances: {Seattle:0.0}

PriorityQueue: (San Francisco:2.0), (Denver:2.0), (Chicago:3.0)

After Iteration 1

=================

shortestDistances: {Seattle:0.0}, {San Francisco:2.0}

PriorityQueue: (Denver:2.0), (Chicago:3.0), (Los Angeles:3.0), (Las Vegas:3.0), (Seattle:4.0), (Denver:4.0)

After Iteration 2

=================

shortestDistances: {Seattle:0.0}, {San Francisco:2.0}, {Denver:2.0}

PriorityQueue: (Chicago:3.0), (Los Angeles:3.0), (Las Vegas:3.0), (Las Vegas:3.0), (Seattle:4.0), (Denver:4.0), (San Francisco:4.0), (Seattle:4.0), (Chicago:4.5), (Las Vegas:5.0)

etc.

Your text file should show the complette algorithm starting in Columbus and running until the priority queue is empty. Notice that with this basic algorithm only the first encounter with each city is added to the shortest distance map (since the way the priority queue works the first one you encounter will have the shortest distance).

Part II - Building the adjacency list

Note that for this assignment we need a few pieces. We need to have a Path class that stores distances, we need to somehow build an adjacency list, and then we need to implement the algorithm described above. The Path class is provided for you below - download it and import it into your Project05 folder.

Path.java

public class Path implements Comparable<Path>{ /* * Declaring these private members final means that * they cannot be changed - they are immutable once they've * been assigned in the constructor. */ private final String endpoint; private final double cost; public Path(String nodename, double cost) { this.endpoint=nodename; this.cost=cost; } /* * getEndPoint * * @return the name of the endpoint for this path */ public String getEndpoint() { return this.endpoint; } /* * getCost * * @return the cost for this path */ public double getCost() { return this.cost; } /* * compareTo * * Paths are ordered by their cost. We return a positive * value if our cost is greater than the one we're comparing * to, a negative cost if it's less than, and 0 when they * are actually equal. * * Cast this to int since compareTo must return an int. * (non-Javadoc) * @see java.lang.Comparable#compareTo(java.lang.Object) */ @Override public int compareTo(Path other) { if (this.cost>other.getCost()) { return 1; } else if (this.costreturn -1; } else { return 0; } } /* * toString * * (non-Javadoc) * @see java.lang.Object#toString() */ @Override public String toString() { return "Path [end=" + endpoint + ", cost=" + cost + "]"; } /* * hashCode * * This is the autogenerated hashCode method from eclipse * (non-Javadoc) * @see java.lang.Object#hashCode() */ @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + (int) cost; result = prime * result + ((endpoint == null) ? 0 : endpoint.hashCode()); return result; } /* * equals * * Two paths are equal when their endpoint is the same and * they have the same cost. * (non-Javadoc) * @see java.lang.Object#equals(java.lang.Object) */ @Override public boolean equals(Object obj) { boolean eq = true; if ((obj == null) || (getClass() != obj.getClass())) eq=false; else { Path other = (Path) obj; if ((cost != other.cost) || (!endpoint.equals(other.endpoint))) { eq=false; } } return eq; } 

Look over the code in Path.java above. It is a fully implemented class, but you should make sure you know how it works. Note specifically that the class does not have any mutators. This class is an example of an immutable type - once you have instantiated values in a Path object you cannot change them. The class has fully implemented equals(), hashCode() and compareTo() methods if you need them, so you do not need to implement these for yourself, but you SHOULD understand how they work and make sure you convince yourself that they will work for our purposes (that compareTo() fulfills the requirements that compareTo() needs, that two things that are equal will have the same hashCode, etc.)

Take a look at the adjacency list structure above. Unlike a standard map, one key maps to multiple values. We can use the multimap structure discussed in class to implement this in our code. Remember - in Java a multimap is implemented as a Map where the values in the key/value pair are Lists of items. You can implement an adjacency list as a multimap from node names to a List of Path objects:

Map< String, List > adj_list

For your first coding step, in your Project05.java file writte a static method named readPathsFromFile with the following method signature:

public static Map< String, List > readPaths(String fname)

This method should take a filename as an argument. It should creatte a new multimap, and then it should read paths from the file and store them in the multimap to make an adjacency list. Each line of the file will use the following format:

node1,node2,distance

For example, the graph above in the Overview section could be written in the file this way:

Columbus,Chicago,0.5

Columbus,Miami,2.0

Chicago,NewYork,1.5

Chicago,Boston,2.0

Chicago,StLouis,0.5

Chicago,Denver,2.5

Chicago,Seattle,3.0

Boston,NewYork,0.5

StLouis,Atlanta,1

StLouis,Dallas,1.0

Atlanta,Dallas,1.0

Atlanta,Miami,1.0

Dallas,Miami,2.0

Dallas,LosAngeles,2.5

LosAngeles,SanFrancisco,1.0

LosAngeles,LasVegas,0.5

SanFrancisco,LasVegas,1.0

SanFrancisco,Seattle,2.0

SanFrancisco,Denver,2.0

Denver,LasVegas,1.0

Denver,Seattle,2.0

You can read in a line at a time and use the String split method to get out individual values from a line. For example, the following code will break up a comma separated line named input into an array of Strings (you will need to use the Double.parseDouble() method to turn the last element of the array into a Double value yourself):

String[] tokens = input.split(",");

Note that each path between nodes is listed only once, but each path needs to be added twice to the adjacency list. For example, the file lists a path between Columbus and Chicago on the first line. This needs to be added to the adjacency list for Columbus as a path with a destination of Chicago AND it needs to be added to the adjacency list for Chicago with a destination of Columbus (the same adjacency list structure can be used to show one-way paths, but all of the paths for this assignment work in both directions). Your code must be written to add both paths.

Your code should also have a static method named displayPaths that has the following method signature:

public static void displayAdjacencyList(Map< String,List > map)

This method should display the entire adjacency list stored in the multimap named map that is passed in as a parameter. The output for this method should be similar to how the adjacency list is displayed above. For example, for the file give above, the following would be displayed:

Miami: (Columbus:2.0), (Atlanta:1.0), (Dallas:2.0)

SanFrancisco: (LosAngeles:1.0), (LasVegas:1.0), (Seattle:2.0), (Denver:2.0)

Atlanta: (StLouis:1.0), (Dallas:1.0), (Miami:1.0)

Chicago: (Columbus:0.5), (NewYork:1.5), (Boston:2.0), (StLouis:0.5), (Denver:2.5), (Seattle:3.0)

Boston: (Chicago:2.0), (NewYork:0.5)

StLouis: (Chicago:0.5), (Atlanta:1.0), (Dallas:1.0)

NewYork: (Chicago:1.5), (Boston:0.5)

LasVegas: (LosAngeles:0.5), (SanFrancisco:1.0), (Denver:1.0)

Seattle: (Chicago:3.0), (SanFrancisco:2.0), (Denver:2.0)

Columbus: (Chicago:0.5), (Miami:2.0)

Denver: (Chicago:2.5), (SanFrancisco:2.0), (LasVegas:1.0), (Seattle:2.0)

Dallas: (StLouis:1.0), (Atlanta:1.0), (Miami:2.0), (LosAngeles:2.5)

LosAngeles: (Dallas:2.5), (SanFrancisco:1.0), (LasVegas:0.5)

(Note that the ordering here is different than in the Overview section above. This output uses a HashMap as its underlying map - try calling the method with both a HashMap and a TreeMap to see the difference in output.)

Your initial main method should prompt for a filename, then read the adjacency list from that file and display it to the screen in the format given above. Once you get this working, move to Part III.

Part III - The Shortest Path algorithm

Once Part II is finished, you can use it as a building block for Part III. You should writte a method named findDistances with the following signature:

public static Map findDistances(String start, Map> adj_list)

This method takes a start node name and the adjacency list you built in Part I as arguments and returns a new Map of node names and distances. The keys in this Map are destination city names, and the values in this map are the shortest distances from the start city to the key city, as determined by the shortest path algorithm given in the Overview above.

Your program should also contain a method named displayDistances with the following signature:

public static void displayShortest(String start, Map shortest)

This method displays the shortest distances constructed by findDistances as a nicely formatted report. For example, the shortest paths from the graph above using Seattle as a start point would be displayed like this:

Distances from Seattle to each city:

Dest. CityDistance

-------------- --------

Miami5.50

NewYork4.50

LasVegas3.00

Seattle0.00

Columbus3.50

Dallas4.50

LosAngeles3.00

Denver2.00

SanFrancisco2.00

Atlanta4.50

Boston5.00

StLouis3.50

Chicago3.00

(This example uses a HashMap - try using either both a HashMap and a TreeMap to track your distances.)

Part IV - Putting it all together

Once you have Parts I, II and III finished, put them together into a final program. The program performs the following actions:

Ask the user to enter the name of the file that contains the paths. Verify that the user has actually entered a value and not an empty line.

Load that file into an adjacency list.

Display the adjacency list to the console in a nicely formatted report.

Prompt the user for the name of a start city.

Find the shortest paths from that start city to all destinations and display that as a nicely formatted report.

Continue asking for start cities until the user enters a blank line.

An sample transcript of a single run of this program is below:

Enter a filename with paths: project05_paths.txt

Start CityPaths

-------------- ------------------------------

Miami(Columbus:2.0), (Atlanta:1.0), (Dallas:2.0)

SanFrancisco(LosAngeles:1.0), (LasVegas:1.0), (Seattle:2.0), (Denver:2.0)

Atlanta(StLouis:1.0), (Dallas:1.0), (Miami:1.0)

Chicago(Columbus:0.5), (NewYork:1.5), (Boston:2.0), (StLouis:0.5), (Denver:2.5), (Seattle:3.0)

Boston(Chicago:2.0), (NewYork:0.5)

StLouis(Chicago:0.5), (Atlanta:1.0), (Dallas:1.0)

NewYork(Chicago:1.5), (Boston:0.5)

LasVegas(LosAngeles:0.5), (SanFrancisco:1.0), (Denver:1.0)

Seattle(Chicago:3.0), (SanFrancisco:2.0), (Denver:2.0)

Columbus(Chicago:0.5), (Miami:2.0)

Denver(Chicago:2.5), (SanFrancisco:2.0), (LasVegas:1.0), (Seattle:2.0)

Dallas(StLouis:1.0), (Atlanta:1.0), (Miami:2.0), (LosAngeles:2.5)

LosAngeles(Dallas:2.5), (SanFrancisco:1.0), (LasVegas:0.5)

Enter a start city (empty line to quit): Seattle

Distances from Seattle to each city:

Dest. CityDistance

-------------- --------

Miami5.50

NewYork4.50

LasVegas3.00

Seattle0.00

Columbus3.50

Dallas4.50

LosAngeles3.00

Denver2.00

SanFrancisco2.00

Atlanta4.50

Boston5.00

StLouis3.50

Chicago3.00

Enter a start city (empty line to quit):

Goodbye!