CSE 373 Data Structures 09au, Homework 5 (55 points)

Electronic Turn-in due: 11:45pm Thursday, December 3rd, 2009.

This assignment will be equal to 1.5 assignments in weight, although it will only have one due date.  In the assignment, you will develop a graph implementation and then use it to implement at least one graph algorithm.  In particular, you will implement (at least) Dijkstra’s algorithm for finding the shortest path.

Part I.  Graph Representations (20 points) (recommended due date Friday 11/27/09)

In this part of the assignment you will implement a graph representation to be used later in Part II.

The assignment has these files provided:

 

You are to add code to MyGraph.java that implements the Graph.java interface.  Graph.java makes use of the Vertex.java and Edge.java classes provided.  You are free to add things to Vertex.java, Edge.java, or MyGraph.java, just don’t remove anything that is currently there.  You should not modify Graph.java.  Your code should be efficient and strive for the minimal big-Oh possible for the requested operations.  Although a simple list of vertices and edges is sufficient to store all information about a graph, it may not be the most efficient method for answering questions about the graph (like those described in part II.)

 

Grading (please note anything which fails these functions might lead points reduction): 

[2 pts] public Collection edges()  
[2 pts] public Collection vertices()  
[8 pts] public Collection adjacentVertices(Vertex v)  
[8 pts] public int isAdjacent(Vertex v, Vertex w)

 

Part II.  Graph Algorithms (20 points)

In this part of the assignment, you will use the graph representation you created in Part I to read a description of a graph and answer questions about it.  In particular, you should use Dijkstra's algorithm to find shortest paths in the graph.  You will do this by filling in code for the shortestPath method in MyGraph.java.  You may assume that graphs you are given will not contain negative cost edges.  A description of the shortestPath method from MyGraph.java appears below:

/**
Returns the shortest path from a to b in the graph.  Assumes positive edge weights. Uses Dijkstra's algorithm.
@param a the starting vertex
@param b the destination vertex
@param path a list in which the path will be stored, in order, the first being the start vertex and the last being the destination vertex.  The list will be empty if no such path exists.  NOTE: the list will be cleared of any previous data.  path is not expected to contain any data needed by the method when the method is called.  It is used to allow us to return multiple values from the function.
@return the length of the shortest path from a to b, -1 if no such path exists.
@throws IllegalArgumentException if a or b does not exist.
**/

public int shortestPath(Vertex a, Vertex b, List<Vertex> path) {

  // YOUR CODE HERE

}

Grading (please note anything which fails this function might lead points reduction): 

[20 pts] public int shortestPath(Vertex a, Vertex b, List<Vertex> path) 



Style (6 points)

Other Provided Files

Driver Program: We have provided a driver program to read in input from the user:

  • Paths.java – driver program that reads in vertex and edge files, creates a graph and prompts use for vertices to find shortest path between.


When the program begins execution, it reads the two data files and creates a representation of the graph.  Although not required, you may find it useful to provide some way to print or display the graph at this point to ensure that it has been read and stored properly.  Once the graph has been built, the program loops repeatedly and allows the user to ask for information about paths in the graph.  The user should enter two vertex names.  If there is a path from the first to the second vertex, the program will describe the shortest (cheapest) such path, including the vertex names on the path and the total length (cost).  For example, if the user enters vertices SEA DEF, then the output might look like SEA ABC DEF 520 if the shortest path from SEA to DEF runs through vertex ABC and has a total length of 520.

You should modify Paths.java so that if there is no path between the two requested vertices, a descriptive message should be printed.

Input file format:  You will need two input files, whose format is as follows:

  • Vertices: This file has one line per vertex and each line contains a text string with the vertex name.
  • Edges: This file has three lines per directed edge.  The first line gives the starting vertex.  The second line gives the ending vertex (the one being pointed to).  The third line is a string of digits that give the distance (or weight) on that edge (this line should be converted to a number to be stored in the graph).


You may assume that every vertex name that appears in an edge also appears in the vertex list.  Note that since data files are expected to represent directed graphs, the existence of an edge from a to b does not guarantee the existence of an edge from b to a (unless both edges exist in the data file), nor does it guarantee that the weight of the edge from a to b is the same as the weight of the edge from b to a.  You may assume that negative weight edges will not be present in input files you are given (although zero weight edges may exist).

Two sample data files are available representing information about airports and the cost of a flight between them.  File vertex.txt contains a list of 3-letter airport codes, each of which represents a vertex in a directed graph.  File edge.txt contains information about the directed edges in the graph.

 

What to Do

1)      Fill in the method bodies as described in Part I and Part II.

2)      Make the slight modification to the provided driver program as requested.

3)      Answer the write-up questions below.

Note: You may use Java collection classes for this assignment.

 

Write-up Questions (9 points):

Include the following in a file called readme.txt:

1)      A description of the worst case big-O running time of your implementations of these methods:

·        adjacentVertices

·        isAdjacent

·        shortestPath

Please use variables E and V in your answers and explain how you got the values you did.

2)      A short description of any extra credit extensions included in your code or data files.  Be sure to include a brief summary of how to operate your program, if you have added new features.

What to Turn In

You should turn in the following electronically:

  • ALL of the files that make up your program.  (Including at least:  Graph.java, Vertex.java, Edge.java, MyGraph.java, Paths.java)You should NOT change Graph.java however.  (Please turn these in as individual files, not zipped together.  Your TAs thank you!)
  • Your readme.txt file containing your write-up as described above.
  • Any additional data or other files you developed to work with your program.  (These should be described briefly in the readme.txt file.)
  • If you did any extra credit, please put those files in a separate folder/zip file.  Include all files needed to run any extra credit options in the zip file.

 

Above and Beyond

A small amount of extra credit will be awarded for interesting extensions.  Here are a few possibilities:

  • (3 points) Improve your implementation of Dijkstra’s by using a priority queue.  For this, you could modify code from the textbook or start from scratch.  Note that for Dijkstra's algorithm, we need to be able to find items in the priority queue and update their priorities.  The simplest implementation of this can just do a sequential scan to locate an item, then adjust the priority, and move the item to its proper place in the heap.  A more complex implementation would allow items in the priority queue to be accessed in constant time on average.  A simple sequential search of the priority queue is fine for small graphs, but for large graphs we would like to be able to find items in constant time so the total time needed to update a priority is a constant plus the log n time needed to reestablish the heap property in the priority queue.  There are various ways to do this, including keeping a back-pointer from each vertex to its entry in the priority queue.
  • (3 points) Find the unweighted shortest path.  In other words, find the minimum number of edges that must be traversed from the start to the destination, ignoring the weight of each edge.
  • (3 points) Given a vertex in the graph, compute a minimum spanning tree from that vertex and print a list of the edges in the MST in the order in which they are added to the tree.
  • (3 points) Other graph algorithms, check with the instructor first.
  • (3 points) Graphical displays: Display the graph as a drawing; allow the user to select endpoints by clicking on the screen; highlight the path visually; etc.
  • (1 point) More/better/interesting data files.  The supplied data files are quite minimal.  Data describing more extensive graphs, other kinds of graphs, or graphs with additional information such as coordinates or locations on a map would be great.

 

 

I’m open to others ideas as well, please talk to me if you have other ideas!