| Assigned: | Wednesday, March 4 |
| Intermediate version due: | Friday, March 20, 11:59pm |
| Version (a) due: | Wednesday, March 25, 11:59pm |
| Version (b) due: | Saturday, April 11, 11:59pm |
A graph is a collection of vertices connected by a collection of edges. An edge connects exactly two vertices to one another. You can draw a picture of a graph by showing the vertices and the edges connecting them. Here is an example. The vertices are shown as circles with numbers in them and the edges are lines connecting the vertices.
Two vertices are said to be adjacent if there is an edge that connects them directly to one another. In the graph above, vertices 1 and 2 are adjacent, but 1 and 4 are not adjacent. A given edge is incident on each of the vertices that it connects.
A path is a sequence of vertices where every consecutive pair of vertices are adjacent to one another. For example, in the above graph, [3, 1, 2, 4] is a path that connects vertices 3 and 4.
A graph is connected if there is a path from every vertex to every other vertex. We will only be concerned with connected graphs here.
A weighted graph is a graph in which each edge has a number attached to it, called the weight of the edge. Here is a picture of a weighted graph.
Think of the vertices of a 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 weighted graph above, 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.
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.
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
This page describes an algorithm, based on Dijkstra's algorithm, for solving this problem, and provides additional details on how to implement it. You are required to use this algorithm, and to follow the guidelines for its implementation. It is not acceptable to rely on a different approach to the problem.
Use sensible terminology in your program. If something is a graph, do not call it an edge. If something is an edge, do not call it a vertex. Make variable and type names sensible. Keep functions short and simple.
As always, you must follow the coding standards for this course.
The input starts with a line that tells how many vertices the graph has. If there are five vertices, then those vertices have numbers 1, 2, 3, 4 and 5. In general, if there are n vertices, then they are numbered 1, …, n.
Following the first line are
the edges, one per line. Each edge line has two integers and one
real number on it.
Line
2 4 5.4
indicates that there is an edge between vertices 2 and 4,
and that its weight is 5.4. The end of the list of edges is signaled
by a line that contains just a 0. After that are the numbers
for vertices s and t. An input describing graph
with start vertex 2 and end vertex 4 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
2 4
Important note. The first number in the input is the number of vertices, not the number of edges. Do not use that number to determine how many remaining lines need to be read. Just keep reading edges until you read a 0.
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 which vertex the signal arrived from. Then you send a signal out on all of the edges that are incident on vertex v and whose other vertex has not yet received a signal.
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 is the distance from the start vertex to the end vertex.
Suppose that signaler(u) is the number of the vertex from which the first signal reached vertex u. Then path [u, signaler(u), signaler(signaler(u)), ...] is the shortest path from u back to the start vertex.
This program must simulate sending and receiving signals. It keeps a list of events, where an event holds three pieces of information, (u, v, t), and indicates the arrival of a signal at vertex v at time t, where the signal was sent from vertex u.
The idea is to store the events in increasing order by the times at which they occur. The program repetitively performs the following steps.
Get the next event (u, v, t). The next event is the one that occurs next in chronological order. So it is the one with the smallest time.
If no signal has yet arrived at vertex v, then do the following.
Record signaler(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), 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. That simulates sending a signal from v to x.
To get going, set the signaler of each vertex to −1 to indicate that no signal has yet arrived at that vertex. Then create an initial event (0, s, 0.0) that indicates a signal arriving at the start vertex s at time 0.0, coming from a fictitious vertex 0. Then do the simulation of events.
When the simulation is finished, you will be able to follow a path
from t back to s by following the chain of signalers.
t -----> signaler(t) -------> signaler(signaler(t)) ----> ... -----> s
Print that chain out backwards, so that it goes from s
to t instead of from t to s.
The easiest way to do that is
to use recursion. To print a path backwards, starting at vertex u,
print the path starting at signaler(u) backwards, then print u.
Of course, in the special case where u is the start vertex
s, just print s. Remember to put -> between
vertex numbers.
You will need to store some information for each vertex in the graph. Create a structure type that holds information about a vertex.
Each vertex has a distance from the start vertex.
Each vertex v has a signaler.
Each vertex has a linked list of edge descriptions, telling the vertices that are adjacent to this vertex and the weight of the edge that connects them. So each cell in the linked list holds (1) another vertex number and (2) a weight. (This list is called the adjacency list of this vertex.)
Create a type that holds information about a graph. It should hold (1) the number of vertices, (2) the start vertex (an integer), (3) the end vertex and (4) an array holding a structure for each vertex. Provide a constructor that takes an integer parameter n and sets up the information for a graph with n vertices and no edges. Be sure that the information about each vertex is initialized.
It is convenient to find the information about vertex v in graph g to be g.info[v], assuming the array is called info. But remember that the vertices are numbered starting at 1, so you want to use g.info[1], ..., g.info[n]. That means there are n+1 slots in the array. You do not use g.info[0].
Once the readGraph and printGraph functions are working, submit them as assignment 5i. Include a main function that tests them.
Create a type Event that describes an event. As explained above, it holds two vertex numbers and a time. Put the definition of type Event in file event.h. You will want to have it in more than one place. To avoid the compiler reading the definition of type Event twice, write the body of file event.h as follows.
#ifndef EVENT_H
#define EVENT_H
struct Event
{
…
};
#endif
This says that if
preprocessor symbol
EVENT_H has not yet been defined, then define it and put the
definition of type Event in the program. But if EVENT_H has
already been defined, then omit the (redundant) definition
of type Event.
You will need a data structure to hold the events that have been scheduled. If you think about the requirements of such a data structure, you will see that you require the following.
A way to create an initialized event queue with no events in it.
A way to insert a new event into the event queue, with a given time.
A way to remove the event that has the smallest time.
A way to ask whether there are any events in the event queue.
Those features are just what you have already implemented as a priority queue. Just use that module. You will need to change the definition of PQItemType to be Event. You will need to make pqueue.h include a header file that defines type Event.
Ensure that your algorithm only uses features of the priority queue module that are part of its interface. Do not use features that should remain hidden inside the priority queue module! You will lose a lot of points if you use non-exported features of the priority queue module.
Create a module, graph.cpp, that is responsible for reading and writing graphs and performing the shortest path algorithm. Put the vertex and graph type definitions in it. Include a main function that reads and echoes the information in the standard input, performs the simulation and writes the path and its distance to the standard output.
Provide functions to do the following tasks.
You 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 action of Dijkstra's algorithm by doing the following. Any time the program shows a signal it must show signaler, the receiver and the arrival time.
The program should look at the command line. If it contains -t, then tracing should be turned on. If not, tracing should be turned off.
To turn in this program, log into one of the Linux computers in the lab. (You can log in remotely.) Ensure that your files are there. Change to the directory that contains those files. Then issue one of the following commands.
~abrahamsonk/3300/bin/submit 5i graph.cpp
~abrahamsonk/3300/bin/submit 5a graph.cpp event.h pqueue.cpp pqueue.h
~abrahamsonk/3300/bin/submit 5b graph.cpp event.h pqueue.cpp pqueue.h
Late submissions on version (a) will be accepted for one day after the due date. Late submissions for version (b) will be accepted for three days after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.