| Assigned: | Friday, March 4 |
| Due: | Monday, 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.
This assignment uses weighted graphs, as described in assignment 4. Please 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. You add the weights of the edges that you use.
For this assignment, the weights are real numbers (type double). All of the weights are 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 description of the graph, 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 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.
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.
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 the vertex number and distance to −1 and 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 three things.
Create a constructor that takes three parameters (a vertex number, a weight and a next pointer) and installs them into the three fields. If a cell with vertex u and weight w occurs in the adjacency list for vertex v, then the graph has an edge from v to u of weight w. Important note. An edge between u and v must occur in two adjacency lists, the list for u and the list for 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. |
| Input and echoing |
|---|
4. Reading the GraphDocument and define a function to read a graph. You can use your function from assignment 4, 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. |
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 and from which vertex the signal was sent. (The time is really the distance. We are computing distances, but 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 out along the edges that are incident on 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 (2 seconds after it was sent from vertex 2).
A vertex can receive more than one signal. Only the first signal that it receives is meaningful. The second and subsequent times a signal arrives at a vertex, the signal is 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.
Suppose that previous(u) is the number of the vertex from which the first signal reached vertex u. Then path [u, previous(u), previous(previous(u)), ...] is the shortest path from u back to the start vertex.
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, (u, v, t), and indicates the arrival of a signal from vertex u at vertex v at time t.
The idea is to store the events in increasing order by the times at which they occur. The program repetitively performs the following steps. This loop is called the event loop. For brevity, I write previous(v) for g.vertices[v].previous and distance(v) for g.vertices[v].distance.
Get the next event (u, v, t) representing the arrival of a signal from u to v 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.
If no signal has yet arrived at vertex v, then do the following.
Record previous(v) = u and 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 we need to send a signal from v to x. Schedule a new event (v, x, t+w) indicating that a signal will arrive at vertex x, coming from vertex v, at a time that is w seconds after time t.
| 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
struct Event
{
…
};
#endif
|
8. The Event QueueYou should notice that the operations needed for events are exactly the ones supported by a priority queue. So you should create a priority queue, called the event queue. The items in the event queue are events and their priorities are their times. 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;So that an item is a pointer to an 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. Stick to the interface. You will be shocked by the number of points that you lose if you violate the priority queue interface. |
9. Sending SignalsDocument and define a function that takes a graph g, a vertex v and a priority 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. To send a signal, just schedule its arrival by adding an event to the priority queue. |
10. Processing an EventDocument and define a function that takes a graph, a priority queue and an event, and that processes the event. Suppose the event represents a signal from vertex u to vertex v that arrives at time t. If vertex v has previously received a signal, do nothing. Throw this event away. But if no signal has yet reached v, then store u as v's previous vertex and t as its distance. Then send a signal to each vertex that is adjacent to v (and that has not already received a signal). |
11. 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. |
12. Showing the PathWhen the simulation is finished, the shortest distance from the
start vertex to the end vertex is simply the distance stored with the
end vertex. You can follow a path
from t back to s easily.
|
| Tracing |
|---|
13. 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. |
14. 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 not 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[2] is "-t". |
A Makefile is provided for you. You can use the following commands with it.
This assignment is larger than what you have done before. 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.
Write clear, concise and precise contracts. Pay attention to that. Write a contract before you start to work on a function.
Keep your program organized and easy to read while you write 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 reasonably short. If a function definition is more than 30 lines long, it should be broken up into smaller functions.
A function body must not change the value of a call-by-value parameter.
To turn in your work, log into the Linux system, change your
directory for the one for assignment 6,
use the following command.
~abrahamsonk/3300/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/3300/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 one day after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.