ECE 2574: Project VI
Introduction
In project six you will implement a minheap and use it as a min-priority queue with Dijkstra’s algorithm.
1 Min-Priority Queue
As we discussed in Lecture 26, unlike a FIFO queue, a priority queue returns the item with the highest (maxpriority queue) or lowest priority (min-priority queue). The heap is a natural way to implement a priority queue because all children nodes are guaranteed to have a lower (greater) value than their parents, and returning the root item would return the item with the greatest (lowest) priority (see CH 17.3). In this portion of the project you’ll create a heap-based min-priority queue (i.e., smallest priority at the root), therefore you’ll need a minheap implementation (we discussed maxheaps in Lecture 32).
The ADT for the priority queue is given in abstract_priority_queue.hpp. You should define a templated HeapPriorityQueue that publicly inherits from the AbstractPriorityQueue interface in the header file heap_priority_queue.hpp. This should override the following methods from the interface and provide a constructor, copy constructor, copy-assignment operator, and destructor.
• a method that indicates whether the queue is empty
• a method that adds an item to the queue
• a method that removes the item with the lowest priority from the queue
• a method that returns the item with the lowest priority from the queue
Your implementation will use a dynamic array to hold the heap. By default the array will hold ten items; when the heap becomes full and a another item is added to the heap, you should double its size. That is, you will need to be able to grow your array in the add method. You may add helper methods as private member functions but cannot modify the public interface for the priority queue.
Info: You are encouraged to re-use/be inspired by the StaticHeap code from Lecture 32. Please note that that code implements a maxheap and this assignment requires a minheap.
2 Dijkstra’s algorithm
The run time of Dijkstra’s algorithm can be significantly improved by using a min-priority queue to keep track of the vertex with the lowest weight not currently in the vertexSet. That is, the priority of a vertex in the queue is determined by the weight of its current shortest path. The pseudo-code for the modified algorithm is as follows (using the notation and nomenclature of your textbook): dijkstra (g: Graph , w: WeightArray )
Create a queue q
n = |V| ( number of vertices in g)
for (v = 0 through n -1)
w[v] = +∝
Insert vertex 0 into q with priority ( weight ) 0
while (q is not empty )
remove the lowest priority vertex v ( having weight k) from q
if (k < w[v])
w[v] = k
for ( all vertices u which are adjacent to v)
if (w[u] > w[v] + m[v][u])
if(u not already in q)
insert u into q with priority w[v] + m[v][u]
You are to implement the above using your HeapPriorityQueue class. Your implementation should be named dijkstra.cpp and it will need to read in an adjacency list for a graph from the file graph.csv and output to the file weight.csv the shortest path to each vertex from vertex zero. You should assume that both of these files are in the same directory as your executable.w[u] = w[v] + m[v][u]
Info: If you are not able to implement your own HeapPriorityQueue you may use the one provided by the STL (std::priority_queue) to receive credit for this portion of the assignment. A separate submission task will be setup on the grader.
2.1 Input/output Formats
The input file, graph.csv, will consist of a line for each vertex with adjacent nodes and their edge weight given as comma-separated pairs. For example, the graph of Figure 20–24 in your textbook would be specified as:1 ,8 ,3 ,9 ,4 ,4
2,1
1 ,2 ,3 ,3
2 ,2 ,4 ,7
2,1
The output file, weight.csv, produced by the algorithm would be:
0 ,7 ,5 ,8 ,4
Info: The .csv files do not have spaces between entries.
2.2 Graph Representation
Internally, your program should represent the adjacency list using an array of the List class from project four where the index of the array corresponds to the vertex number (starting at 0) and the entries in the list at that index are the vertex’s neighbors and their edge weights. Use std::pair to store the vertex number of the neighbor and the corresponding edge weight. Similarly, the shortest path to each vertex should be stored in a List. Info: Recall that we defined an array of Bags in the midterm and the solution has been posted.
2.3 Insertion into the Queue
One thing to note about the min-priority queue implementation is that type T must be orderable (support relational operators, operator<, etc.). To handle inserting vertices into your min-priority queue, an easy way to assign a priority key to an arbitrary item would be to use the std::pair class of the STL (i.e., make the key the first entry in the pair and the item the second). Check the STL documentation for std::pair to see how the relational operators work for it. Otherwise, define a struct containing the vertex number and its current weight at time of insertion, as well as the necessary comparison operators. 3 Testing
Each method in heap_priority_queue.hpp, aside from the destructor, should be tested. Tests should attempt to be comprehensive; i.e., cover all possible user interaction with the class. Each test case should include multiple assertions. You should perform manual or automatic testing of your dijkstra.exe application to be that it follows the specification above. You can generate test cases for your code by using the algorithm visualizer at: https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html
4 Grader
After your have tested your code against your own examples, you can use the grader to check your implementation against our tests. You should submit to the grader only after you’ve tested each of the methods using your own unit tests. For this assignment you should upload a zip file containing only the files: dijkstra.cpp, student_tests.cpp, list.txx, heap_priority_queue.hpp, and heap_priority_queue.txx. There is a build target called “submission” configured by default to create this file with the correct contents in your build directory. Info: If you did not implement your own HeapPriorityQueue then upload dijkstra.cpp, and list.txx to both the grader and canvas.
5 Submission
Once you are satisfied with your code, upload a zip file containing dijkstra.cpp, student_tests.cpp, list.txx, heap_priority_queue.hpp, and heap_priority_queue.txx through Canvas at the assignment link. You should not submit the other files from the starter code, nor your build directory. There is a build target called “submission” configured by default to create this file with the correct contents in your build directory. 6 Grading
There are 100 points allocated to this assignment.• Correctly submitting the required files: 2 points
• Your tests compile: 3 points
• Your tests pass: 15 points (proportional)
• Instructor tests compile with your code: 3 points
• Instructor tests pass: 27 points (proportional)
• No tests leak memory: 5 points
• dijkstra passes instructor tests: 35 points (proportional)
• Design requirements met (e.g., code and test quality, comments): 10 points
As per the syllabus, good faith efforts must be made to write comprehensive tests. Since there is no way to test for this at compile or run time (at this point), should the grader (person) deem your tests to be woefully lacking you will lose not only design points but also the points given by the autograder. Each method should be tested and each test case should consist of multiple assertions.
2019-12-11