
c m s c 214
f a l l 2 0 0 1 
Saturday is 1 day late (10 points off), Sunday is 2 days late (20 points off), Monday is 3 days late (30 points off). No submissions accepted after that without permission of YOUR instructor.
This was updated December 4, 2001. This should be the final posting. Read FAQ for any minor updates.
This was posted November 29, 2001. More to be posted soon.
VIOLATIONS OF ACADEMIC HONESTY INCLUDE:
IT IS THE RESPONSIBILITY, UNDER THE UNIVERSITY HONOR POLICY, OF ANY STUDENT WHO LEARNS OF AN INCIDENT OF ACADEMIC DISHONESTY TO REPORT IT TO THEIR INSTRUCTOR.
<sitelist> <site> Tatooine </site> <site> Alderaan </site> <site> Coruscant </site> <site> Dagobah </site> </sitelist> <adjacencylist> <entry> <site> Coruscant </site> <neighborlist> <neighbor> <site> Dagobah </site> <distance> 10 </distance> </neighbor> <neighbor> <site> Alderaan </site> <distance> 20 </distance> </neighbor> </neighborlist> </entry> <entry> <site> Alderaan </site> <neighborlist> <neighbor> <site> Coruscant </site> <distance> 20 </distance> </neighbor> </neighborlist> </entry> </adjacencylist> <cmmdlist> <cmmd> SHORTEST_PATH Dagobah Alderaan </cmmd> <cmmd> SHORTEST_ALL Dagobah </cmmd> </cmmdlist>
It's important that you sort the list so that everyone numbers their vertices the same. For example, there are four sites listed. In alphabetical order, they are: Alderaan, Coruscant, Dagobah, and Tatooine, and would be numbered 0 thorough 3.
You may assume this list is nonempty, and there are no duplicates.
You may assume that the graph that is produced is undirected. The list of neighbors may therefore not be complete. If Alderaan is listed as a neighbor of Tatooine, then it's not necessary for Tatooine to list Alderaan as a neighbor. If they do list each other, you may assume the distances will be the same. Thus if Alderaan is a neighbor of Coruscant and Coruscant is a neighbor of Alderaan, both should have equal distances.
You should enter edges in both directions into the adjacency list, even if it's only listed in one direction.
The graph does not have to be connected.
To remove the minimum value, sort the vector (where the operator< compares the weights of two nodes) and pick the minimum. Remove this from the vector using erase(). Then, update the neighbors costs using linear search in the vector. This is easy to implement, although it runs slowly.
You will also need to write a file called "dijkstra.cpp" which will contain all the functions to compute shortest path. You will be provided "dijkstra.h" to work with.
First, some corrections. The word "hash" should really be heap. There is no hash table in this implementation.
What are these arrays? You will enter elements into the heap in order starting from vertex 0 up to vertex N  1, where N is the number of elements in the heap.
The heap will store the "current minimum cost" of each vertex. Initially, the start vertex has weight 0 and the other vertices have infinity (pick a large number, like 100000 for the weight).
In Dijkstra's algorithm, you have a "decrease key" operation which occurs when the cost of a vertex is smaller due to the "relax" operation. When this happens, you, the user of the "heap" will want to specify the vertex whose cost has been decreased (you simply put the new value of the cost as argument to the function call).
However, even though you may specify vertex 5, that may not be the index where it is located in the heap. This is what vertexToHeap is about. You call vertexToHeap[ 5 ] and it should return the index in the heap.
vertexToHeap and heapToVertex are "inverses" of each other (as taught in CMSC 250). Thus, vertexToHeap[ heapToVertex [ i ] ] == i and vice versa.
You must maintain this relation, even as you do the "heapify" or "upheapify" operation.
"upheapify" is used in decreaseKey and insert operations. It assumes a node has a small cost/weight and needs to be moved up the heap (closer to the root). Swaps only occur with parents.
Should you choose not to do either one, you should change the name to "PriorityQueue". If you do not implement "MinHeap" with both features, then you will be deducted 5 points for trying to "fool the TA".
A posting on STL will be provided to give you enough background to use this. You should be familiar with how to use most of it, since you had to use vectors back in Project 1, and have implemented classes similar to that provided in STL.
The message will look like:
After parsing sites ****** Vertex 0 : Alderaan Vertex 1 : Coruscant Vertex 2 : Dagobah Vertex 3 : TatooineYou may assume there is at least one site. The syntax can be deduced from the above. (Add one blank line after the last vertex).
You may assume the source and destination are valid vertex numbers. The cost is assumed to be positive float. If successful print a message like:
[ADD_EDGE] Edge from (<source>) to (<dest>) with cost <cost> successfully addedAgain, add a blank line afterwards. Recall that this is a undirected graph, so edges are added in both directions.
If the edge already exists, then print
[ADD_EDGE] Edge from (<source>) to (<dest>) already existsand don't add edge.
You may assume the source and destination are valid vertex numbers. The cost is assumed to be positive float. If successful print a message like:
[UPDATE_EDGE] Edge from (<source>) to (<dest>) with cost <cost> successfully updatedAgain, add a blank line afterwards. Recall that this is a undirected graph, so edges are updated in both directions.
If the edge does not exist, then print
[UPDATE_EDGE] Edge from (<source>) to (<dest>) does NOT existand don't update edge.
You may assume the source and destination are valid vertex numbers. If successful print a message like:
[REMOVE_EDGE] Edge from (<source>) to (<dest>) with cost <cost> successfully removedAgain, add a blank line afterwards. Recall that this is a undirected graph, so edges are removed in both directions.
If the edge does not exist, then print
[REMOVE_EDGE] Edge from (<source>) to (<dest>) does NOT existand don't remove edge.
Print the following for the current graph
[NUM_EDGES] The graph has <num> undirected edgeswhere <num> is replaced by the number of undirected edges.
Again, add a blank line afterwards. Recall that this is a undirected graph, so edges are updated in both directions.
You may assume <source> and <dest> are valid vertices (in the graph). However, there may not be a path between the two.
If there is a path, print:
[SHORTEST_PATH] The shortest path from (<source>) and (<dest>) Dagobah to Coruscant (10 parsecs) Coruscant to Alderaan (20 parsecs) ****** Total: 30 parsecsBut list intermediates sites. For example, if the path is from site A to site C to site B to site E, then print "A to C" on the first line and the distance, followed by "C to B" on the next line, and the distance between the two, followed by "B to E" on the next line. Then, put the dashes as shown above, and provide the total distance.
If no path exists, print
[SHORTEST_PATH] No path exists from (<source>) and (<dest>)
This lists the shortest path to all vertices. The vertices be listed in alphabetical order. You should assume shortest path to the source vertex is itself. Here is an example:
[SHORTEST_ALL] Shortest distance from (Dagobah) to: Alderaan (30 parsecs) Coruscant (10 parsecs) Dagobah (0 parsecs) Tatooine (UNREACHABLE)Since there is at least one vertex, you shouldn't worry about the case of no vertices.
Print the current graph using the print function from the adjacency list.
This takes one argument, a source, and prints something like:
[DEBUG] Vertex To Heap *** 1 > 2 2 > 1 4 > 0 Heap To Vertex *** 0 > 4 1 > 2 2 > 1 Heap Cost *** 0 > 10 1 > 25 2 > 14This will print the heap after ONE step of Dijkstra's algorithm. This is the step AFTER the source vertex has been selected as the min cost vertex, and its neighbors "relaxed". For example, suppose source vertex A has neighbors B, C, and D with edge weights 3, 7, and 2 respectively. It should print out the information just after A has been selected and B, C, and D have their weights modified to 3, 7, and 2, and the heap has been re "heapified".
This prints the contents of vertex to heap (there may be "gaps" in the vertex index, so only print the vertices that remain the heap), then heap to vertex, then the cost in each heap. You should be able to write this by modifying the "debug()" function in the MinHeap.
If you choose not to do MinHeap, just treat this as an illegal command and print the illegal command message as in previous projects.
submit p5.tar 5 SUBMITYour executable must be called exactly p5. Any other name will cause your program not to be submitted.
You can name the tar whatever you want. However, you should wait until a primary input and output have been posted. (If you submit before that, then if your project does not pass the primary input/output, you will receive a poor grade on the project, most likely a zero).
Please do not submit until a primary input and output have been posted. If you do, you may receive a 0 for failing to pass the primary.