Homework 9: Handed out: 4/15/99; Due: 4/29/99
Description
This assignment will give you a chance to implement some of the most important graph algorithms known to mankind: Dijkstra's Shortest-Path Algorithm, Breadth-First Search (BFS), and Depth-First Search (DFS). In addition, you will be implementing simple conversions to adjacency-list and adjacency-matrix representations.
Now that you have been through the rigors of the first programming assignments, we've decided to make this one more open-ended. Essentially, we're giving you a list of functions that you need to implement. All you need to do is to make it happen... make them return the right answers and you're done.
There are five methods that must be implemented and that we will be testing. All five methods operate on directed and positively weighted graphs. You can assume that the vertices in the graph are numbered 0, ..., |V|-1. [**CHANGED** IT USED TO SAY 1, ..., |V|.] We represent a graph by a number (which represents the number of vertices) and a collection of triplets (i,j,w), which denotes that there is an edge from vertex i to vertex j that has weight w. We assume that the weights are integers. When coding up your algorithms and a decision must be made between several vertices, always choose the lowest-numbered vertex first. (This means that all the algorithms should generate the same minimum-length path, for example.)
Here are the algorithms you need to implement:
GraphToAdjMatrix – Creates an adjacency matrix
Parameters: Input Graph
Output: An Adjacency Matrix - a two dimensional array with 0 if no edge and the edge’s weight if there is one.
GraphToAdjList – Creates an adjacency list
Parameters: Input Graph
Output: An Adjacency List -- a vector whose the ith element is a vector consisting of the vertices j adjacent to vertex i together with the weight of edge (i,j) - use the EdgeForList class to hold neighboring vertex and weight information. [**CHANGED** Slight change in description] The vectors must be sorted in increasing order by vertex number.
BFS – Breadth First Search
Parameters: Input Graph, Start
Output: vector of vertices that list the order in which the vertices are traversed, starting with the Start vertex.
DFS – Depth First Search
Parameters: Input Graph, Start
Output: vector of vertices that list the order in which the vertices are traversed, starting with the Start vertex.
Dijkstra – Dijkstra’s algorithm for shortest path
Parameters: Input Graph, Start, Goal
"Output: [**CHANGED DESCRIPTION**] A vector in which the first entry is the length of the shortest path (use an Integer object), and the rest of the entries are the order of the nodes in the shortest path, starting with Start and ending with Goal. Note that in Dijkstra's algorithm, you may implement the priority queue as you wish.
In addition, the files you will be needing are:
Testing
Your assignments will be tested by our test program. For this reason, make sure you keep the function names unchanged. Do not mess with the provided interfaces. If your programs fails the tests because the interfaces don't match up, you won't do very well. Also, make sure that each functions returns exactly what is required, because otherwise it probably won't pass our tests. What you will probably need to do is to make a small test program of your own to test your code for the assignment.
Grading
Here is the grading breakdown for this assignment:
Questions? Ask either Randy Fernando (prf3@cornell.edu), Rami Baalbaki (rsb11@cornell.edu) or David Welte (welte@cs.cornell.edu), or, even better, post them on netnews.
Good luck.