Project 3

Project 3 description: pdf . Due Friday, April 28.
Here is code from the textbook that you can use and modify for your project: Graph1.cpp , binary_heap.h
Here is a simple file, rpinet.txt , that contains the initial state of the graph. When the graph is created and processed using the command
```
 graph rpinet.txt  < queries.txt > results.txt
```
the output resulting from the queries in the query file queries.txt gives the resulting output of results results.txt .
Here is another example (actually, a modification of the one above). When the graph is created and processed using the command
```
 graph rpinet.txt  < queries2.txt > results2.txt
```
the output resulting from the queries in the query file queries2.txt gives the resulting output of results results2.txt .
You MUST match your output format to the example output format above. There will be at least a 5 point penalty if your program output does not match the example output.
Please follow the academic integrity guidelines as you work on your projects. Be sure to submit your own work. Remember that you learn the most by doing the work. We will be using software to automatically compare and detect submissions that violate the integrity guidelines.
Project Submission:
Important: Please verify you are submitting your project under the correct section. You will be penalized for submitting to an incorrect section.
- Section 2, (Wednesday 10:00-11:50am; Sage 4101), TA: Ethan Glasser-Camp
- Section 4, (Wednesday 4:00-5:50pm; Sage 2715), TA: Brandi Hill
- Section 7, (Wednesday 2:00-3:50pm; Sage 4101), TA: Vineet Chaoji

FAQ and Clarifications

Last updated 3:00pm, Thursday, May 4.

Files used for grading your projects are here .
We will not issue shortest path queries from/to a down vertex. Similarly, we will not issue a shortest path query to an unreachable vertex.
When the addedge command is called on an edge that already exists, it may change the edge weight. However the up/down state of the edge will be changed only by the edgeup/edgedown commands.
When analyzing the running time of the reachable algorithm, analyze the running time of the algorithm that computes the reachable vertices from all vertices (that is, for every vertex find all reachable vertices).
You may assume the vertices and edges sent to the queries Deleteedge, Edgedown, Edgeup, Vertex up, Vertex down are valid edges and vertices.
For the "reachable" query, we have asked you to print the vertices in alphabetical order to make grading easier. This may require a final sorting step. You can analyze and specify the complexity of your basic reachable algorithm and the sorting step separately.
Clarification on addedge and deleteedge commands: these act on only the specified directed edge, not its twin edge in the other direction.
Your remaining late days may be used for Project 3. However, any submission that exceeds the total limit of 3 days (over all three projects) will not receive any credit.
Clarification: You should run Dijkstra's algorithm every time the "path" query to find the shortest path is given.
You must not use Dijkstra's algorithm (or the author's unweighted shortest paths code) for the "reachable" query. You will not receive many points if you do.
Please make sure to add comments in your code to explain your algorithm for the "reachable" query, and justify its running time in terms of V and E using "O" notation. Your algorithm should be as efficient as possible, and should certainly be more efficient than using Dijkstra's algorithm on every vertex in the graph.
Well explained and easy to understand code will be graded more favorably.
You should test your code extensively by creating your own examples. The data files provided above merely provide a starting point for your tests.
Please include all source code needed to compile and run your program in your submission, including code that we provided.