Assigned: | Monday, March 13 |
Due: | Tuesday, March 28, 11:59pm |
The purpose of this assignment is to develop your abilities to write a larger application involving arrays, structures and linked lists. It also introduces switchable tracing.
Warning. In the past, many students have started too late on this assignment, and have submitted programs that did not compile or were only the beginnings of full programs. Start early. Resolve to finish early. This assignment will take more time than you expect it to.
This assignment uses weighted graphs, as described in assignment 4. Be sure that you are familiar with weighted graphs.
Two vertices are said to be adjacent if there is an edge that connects them directly to one another. A given edge is incident on each of the vertices that it connects.
Think of the vertices of a weighted graph as towns and the edges as roads. The weight of an edge is the length of the road. One thing that you might like to know is how to get from one town to another by the shortest possible route. For example, in the following weighted graph, the shortest route from vertex 1 to vertex 5 is to go from 1 to 3 and then from 3 to 5, and the length of that route is 27. The total distance is the sum of the weights of the edges in the path.
For this assignment, the weights are real numbers (type double). All of the weights are required to be nonnegative. Edges of weight 0 are allowed.
Write a program that reads information about a weighted graph from the standard input. The input format is described in detail below. After the edges, the input has two vertex numbers, s and t.
Your program should print a description of the graph, followed by the shortest path from s to t and the distance from s to t via that path, on the standard output.
For example, the input might look
like this.
5
1 2 9.0
1 3 12.0
2 4 18.0
2 3 6.0
2 5 20.0
3 5 15.0
0
1 5
That says that there are five vertices. There is an edge from
vertex 1 to vertex 2 with weight 9.0, an edge from vertex 1 to vertex 3
with weight 12.0, etc. The 0 indicates the end of the edges.
The start vertex s
is 1, and the end vertex t is 5.
The output for this input would be as follows.
There are 5 vertices and 6 edges.
The edges are as follows.
(1,3) weight 12.000
(1,2) weight 9.000
(2,5) weight 20.000
(2,3) weight 6.000
(2,4) weight 18.000
(3,5) weight 15.000
The shortest path from 1 to 5 has length 27.000 and is
1 -> 3 -> 5
Create a directory to hold assignment 6 and call your program dijkstra.cpp. Start with the standard template.
Below is a description of an algorithm, based on Dijkstra's algorithm, for solving this problem. You are required to use that algorithm, and to follow the guidelines for its implementation. It is not acceptable to rely on a different approach to the problem. Follow the design.
Make variable and function names sensible. Use sensible terminology. If something is a graph, do not call it an edge. If something is an edge, do not call it a vertex. Keep functions short and simple. Remember that a function cannot have more than 15 noncomment lines in its body.
As always, you must follow the coding standards for this course.
This assignment uses a different graph representation from assignment 4. Here, we use the adjacency list representation.
Types and information representation |
---|
1. Type VertexCreate and document type Vertex. Each vertex v has the following pieces of information.
Create a constructor for type Vertex that takes no parameters and sets signaled to false and sets the linked list to NULL. |
2. Type EdgeCreate and document type Edge. Type Edge is used for a cell in an adjacency list. The Edge structure stores:
Create a constructor that takes four parameters (two vertex numbers, a weight and a next pointer) and installs them into the four fields. Important note. An edge between u and v must occur in two adjacency lists, the list for vertex u and the list for vertex v, since it can be used to go from u to v or from v to u. |
3. Type GraphCreate and document type Graph. A graph stores the following.
Create a contructor for Graph that takes a number of vertices as a parameter. It should allocate an array for the vertices and set the number of edges to 0. Notice that it is not necessary to have a maximum number of vertices. You allocate the array after you know how many vertices there are. |
Input and echoing |
---|
4. Reading the GraphDocument and define a function to read a graph. You can use your function from assignment 4 as a starting point, but be careful to notice that the graph representation has changed. Do not change the graph representation to make the old graph reader work unchanged. Use the adjacency list representation. Only store the graph once. The contract for this function should describe the input format and show an example input. |
5. Printing a GraphDocument and define a function to print a graph. Again, you can use your function from assignment 4 as a starting point, but make sure to convert it to the new graph representation. |
6. TestingTest reading and echoing the graph. Do not move on until you are satisfied that this much works. |
Dijkstra's algorithm is a well-known algorithm for computing shortest paths in a graph.
Imagine yourself at the start vertex. You send out a signal from there along each edge, where the signal takes w seconds to traverse an edge of weight w. For example, if the start vertex is vertex 1 and there is an edge between vertices 1 and 2 of weight 5.1, then the signal sent from vertex 1 reaches vertex 2 after 5.1 seconds.
The first time a signal reaches a vertex v, you record the time at which the signal arrived as v's distance the vertex that the signal came from at v's previous vertex. (We are computing distances, so the time is really a distance. It is easier to understand the algorithm if you think in terms of time. So we use time and distance interchangeably.)
When vertex 2 receives a signal from vertex 1 at time 5.1, it sends a signal to all vertices that are adjacent to it. For example, if there is an edge from vertex 2 to vertex 3 of weight 2.0, then the signal from vertex 2 to vertex 3 arrives at vertex 3 at time 7.1 (It was sent after 5.1 seconds into the simulation, and it arrives at vertex 3 two seconds later.).
A vertex can receive more than one signal. Only the first signal that it receives is meaningful. The second and subsequent signals are ignored.
The algorithm is finished when a signal reaches the end vertex. The time at which the signal arrived at the end vertex tells the distance from the start vertex to the end vertex.
Let's write prev(u) for u's previous vertex: the number of the vertex from which the first signal reached vertex u. Then path [u, prev(u), prev(prev(u)), …, s] is the shortest path from u back to the start vertex s. The path from s to u is the reversal of that.
This program must simulate sending and receiving signals. To do that, it keeps a list of events, where an event holds three pieces of information, (sender, receiver, time), and indicates the arrival of a signal from vertex sender at vertex receiver at time time. The time of an event is always the total time since the beginning of the simulation.
The idea is to store the events in increasing order by time into an event queue. The program repetitively performs the following steps. This loop is called the event loop. For brevity, I write prev(v) for g.vertices[v].prev, dist(v) for g.vertices[v].distance and signaled(v) for g.vertices[v].signaled.
Get the next event E = (sender, receiver, t) representing the arrival of a signal from sender to receiver at time t. The next event is the one that occurs next in chronological order. So it is the one with the smallest time. An event only happens once, so remove this event from the event queue.
If no signal has yet arrived at vertex receiver, then process event E, as follows. I will refer to receiver as v.
Record signaled(v) = true, prev(v) = sender, distance(v) = t.
For each edge that is incident on vertex v (say, connecting v with vertex x and having weight w), if x has not yet received a signal then send a signal from v to x.
You send a signal simply by inserting an event representing the signal's arrival into the event queue. The signal from v to x arrives at time t + w.
Repeat. Keep doing (get an event; process the event) until a signal has reached the end vertex.
Development plan |
---|
7. EventsCreate and document a type Event. An event stores a sender, a receiver and a time at which the event occurs. You will want a header file that defines type Event. Call it event.h. It should look as follows. #ifndef EVENT_H #define EVENT_H // documentation for type Event struct Event { … }; #endif |
8. The Event QueueYou should notice that the operations needed for events are exactly the ones supported by a priority queue. The priority of an event is its time. We refer to a priority queue holding events as the event queue. Create a copy of pqueue.h and pqueue.cpp for use with this assignment. Modify the definition of PQItemType in your priority queue module to be typedef Event* PQItemType;Make pqueue.h include "event.h" so that it can use type Event. Make sure that you allocate events in the heap. When you remove an event from the event queue, delete it when you are finished looking at it. Note. Your shortest-distance module should only use the things in the priority queue module that the priority queue module exports. You are not allowed to make use of the fact that a priority queue is represented as a linked list. You are not allowed to make direct use of a value of type PQCell or PQCell*. Stick to the interface. You will be shocked by the number of points that you lose if you violate the priority queue interface. Don't do it. |
9. Sending a single signalDocument and define a function that takes two vertex numbers u and v, a time t and an event queue q. It should send a signal from u to v, arriving at time t, by inserting an event into q. That is all it should do. Don't add other duties. |
10. Sending SignalsDocument and define a function that takes a graph g, a vertex v and an event queue q. It should send a signal from v to every vertex that is adjacent to v in g, excluding those that have already received a signal. This function must use the preceding one to send each signal. That is all it should do. Don't add other duties. |
11. Processing an EventDocument and define a function that takes a graph, an event queue and an event, and that processes the event. Note that this function processes a single given event. That is all it does. Don't add any other duties. Suppose the event represents a signal from vertex sender to vertex receiver that arrives at time t. If vertex receiver has previously received a signal, do nothing. Throw this event away. But if no signal has yet reached receiver, then
Then send a signal to each vertex that is adjacent to v (and that has not already received a signal). |
12. Running Dijkstra's AlgorithmDocument and define a function that performs Dikjstra's algorithm. It starts by sending a signal to the start vertex that comes from ficticious vertex 0 and that arrives at time 0. Then it goes into the event loop. It keeps getting and processing events until a signal has reached the end vertex. |
13. Showing the PathWhen the simulation is finished, the shortest distance from the
start vertex s to the end vertex t is simply the distance stored with vertex t.
You can follow a path from t back to s easily.
|
Tracing |
---|
14. TracingYou are required to put trace (or debug) prints in your program that can be turned on and off. If tracing is turned on, trace the following.
Make your traces clear and easy to understand. It should not require an expert to read them. Do not show raw data. To trace the arrival of a signal, your program might show something like the following. Time 22.1: A signal arrives at vertex 5 from vertex 2. |
15. Turning Tracing On or OffThe program should look at the command line. If the command line contains -t, then tracing should be turned on. If not, tracing should be turned off. When tracing is turned off, there must be no tracing. Use a global variable that holds 0 if there is no tracing and 1 if there is tracing. This is one of the few places where you are allowed to use a global variable. Just define the variable near the beginning of your module, outside of any functions. Write a separate function that sets the tracing variable by looking at the command line. The command line is passed to main. Use the following heading for main. int main(int argc, char** argv)Parameter argc tells how many parts the command line has, and argv[i] is the i-th part (a null-terminated string). For example, if the command is ./dijkstra -tthen argc is 2, argv[0] is "./dijkstra" and argv[1] is "-t". If some other option is provided, then the program must
write a line
|
A Makefile is provided for you. You can use the following commands with it.
This assignment is larger than prior assignments. In the past, students have become overwhelmed and have stopped paying attention to basics. But the basics are even more important as the size of a program increases.
Do not relapse into novice software design methods!
Start early. If you start late, you will end up with a junk program.
Write clear, concise and precise contracts. Pay attention to that. Write a contract before you start to work on a function. Then make the function do exactly what the contract says it does.
Avoid complicated algorithms. Keep it simple.
Keep your program organized and easy to read while you write it.
Use successive refinement. Write a little bit and test that. Do not try to write the entire program before testing any of it.
If you follow this advice, you should find this program much easier than you originally thought it would be. If you ignore this advice, then you will find this program to be even harder than you orignally thought.
Do not ignore compiler warnings. If you do not understand what a warning means, ask about it.
Each function can have at most one loop in its body. Do not use one loop to simulate two nested loops by manipulating the loop parameters.
Keep function definitions short and simple. A function body must have no more than 15 noncomment lines.
A function body must not change the value of a call-by-value parameter.
Delete events after handling them.
To turn in your work, log into the Linux system, change your
directory for the one for assignment 6,
use the following command.
~abrahamsonk/2530/bin/submit 6 pqueue.cpp pqueue.h event.h dijkstra.cpp
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
Command
~abrahamsonk/2530/bin/submit 6
will show you what you have submitted for
assignment 6.
You can do repeated submissions. New submissions will replace old ones.
Late submissions will be accepted for 24 hours after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.
To ask a question about your program, first submit it,
but use assignment name q6. For example, use command
~abrahamsonk/2530/bin/submit q6 pqueue.cpp pqueue.h event.h dijkstra.cpp
Include a data file if appropriate.
Then send me an email with your question. Do not expect
me to read your mind. Tell me what your questions are.
I will look at the files that you have submitted as q6.
If you have another question later, resubmit your new file
as assignment q6.