| Assigned: | Wednesday, November 1 |
| Due: | Tuesday, November 14, 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 5. 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 starts with a description of a graph in the same format as for Assignment 5. After that are two vertex numbers: a start vertex s and an end vertex e.
Your program should print, on the standard output, a description of the graph followed by the shortest path from s to e and the distance from s to e via that path.
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 line containing only 0 indicates the end of the edges.
The start vertex s
is 1, and the end vertex e 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
The order of the edges is not important, but each edge should
be shown once.
A
As each event is encountered, it is processed. A key characteristic of discrete event simulations is that processing one event can cause more events to be created.
An example is a simulation of a bank with tellers and customers. There are five kinds of events.
A teller is ready to serve a customer. This event is processed by placing the teller into the teller queue. If the customer queue is not empty, it also schedules a "teller begins to serve customer" event at the current time.
A customer arrives. Processing a customer arrival adds the customer to the customer queue and also schedules another customer arrival at some randomly chosen future time. That way, customers keep arriving. The distribution of random times determines how rapidly customers arrive.
If there is a teller in the teller queue, then a "teller begins to serve customer" event is scheduled at the current time.
A teller begins to serve the next customer. Processing this event removes the first customer from the customer queue and removes the first teller from the teller queue. It also schedules a "teller finishes serving customer" event at some randomly chosen future time. The distribution of this random number controls how much time it takes to process a transaction.
A teller finishes serving a customer. Processing this event schedules a "teller is ready to serve customer" event at the current time.
Stop the simulation. Processing this event stops the simulation.
Additionally, when each event is processed, it writes out the current simulation time and the event that is being performed. It also keeps track of some statistics, such as how long a customer waited for service on the average.
It is easy to get the simulation started. If there are t tellers, then schedule t "teller is ready" events at time 0, the beginning of the simulation. Also schedule a "stop" event at some future time so that the simulation will not continue forever.
The simulation is performed by an event loop, that is roughly as follows.
loop
Get the chronologically next event. Call it E.
Process event E.
until the simulation has stopped
Discrete event simulations are useful for games. Each event is something that happens in the game, such as a character taking a step forward. Processing an event can cause new events to be sheduled, such as taking another step forward. It is easy to schedule the arrival of new characters at specific times.
Dijkstra's algorithm finds shortest paths in weighted graphs, and it can be expressed as a discrete event simulation.
Instead of thinking of each edge as having a distance, think of the weight of an edge as a time, in seconds. The simulation imagines sending signals between adjacent vertices. A signal from vertex u to vertex v along an edge of weight w takes w seconds to reach v.
During the simulation, the algorithm keeps two pieces of information about each vertex v.
The arrival time (v.time) of the first signal to reach v. If no signal has reached v, then v.time is −1.
The vertex (v.from) that sent the signal to v that was the first signal to reach v. If no signal has reached v, then v.from is −1.
There is just one kind of event: A signal from vertex u arrives at vertex v at time t. Let's write that event in a more compact form as (u, v, t).
Processing event (u, v, t) goes as follows.
If v.time ≥ 0, then do nothing, since this is not the first signal to reach v. For the remaining cases, assume that v.time < 0.
Set v.time = t and v.from = u.
For each vertex r that is adjacent to v, where no signal has yet reached r, send a signal from v to r by scheduling an event (v, r, t + w) where w is the weight of the edge from v to r. That is, this signal arrives at r just w seconds after the signal reaches v.
To get started, create an event that represents a signal arriving at the start vertex from a fictitious vertex 0 at time 0. After that, go into the event loop. Keep going until a signal reaches the end vertex.
| Getting started |
|---|
|
1. Create a directory for assignment 7 and create file dijkstra.cpp. Copy the template into it. Add a comment to dijkstra.cpp telling its purpose. Include a description of the input format as well as an example input and output. |
This assignment uses a different graph representation from assignment 5. Here, we use the adjacency list representation.
| Types and information representation |
|---|
|
2. Type Vertex Create and document type Vertex. Each vertex v has the following pieces of information.
Create a constructor for type Vertex that takes no parameters, sets the time and from fields to −1. and sets the adjacency list to NULL. |
|
3. Type Edge Create 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. Think of a bidirectional road being split into two one-way roads. Important note. Since the roads are actually one-way, the order of the vertices matters. Choose an order. For example, an edge from a to b might be stored with u = a and v = b, not the other way around. |
|
4. Type Graph Create and document type Graph. A graph stores the following.
Create a contructor for type 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. The vertices are numbered starting at 1. The sensible thing is not to use index 0 in the array. Pay attention to that. You will need to allocate an extra slot in the array to account for the unused slot. |
|
5. Draw an accurate picture of the representation of a small
sample graph. Skipping this step is a big mistake.
In the description of Dijkstra's algorithm, I have used v.time for the time stored with vertex number v. But that is not how it is referred to in the program. If you have Graph g, how can you get the time stored for vertex number 1 in g? For vertex number v? |
| Input and echoing |
|---|
|
6. Reading the Graph Document and define a function to read a graph. You can use your function from assignment 5 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. Do not use duplicate representations. Only store the graph once, using the adjacency list representation. |
|
7. Printing a Graph Document and define a function to print a graph. Again, you can use your function from assignment 5 as a starting point, but make sure to convert it to the new graph representation. Below, you will use a global variable to control tracing. If tracing is turned on then show each edge twice, once for each adjacency list that it occurs in. If tracing is turned off, then show each edge once. That is easy to arrange. When looking at an edge from u to v, only show it if u < v. |
|
8. Testing Test reading and echoing the graph, both with tracing turned on and turned off. Do not move on until you are satisfied that this much works. |
| Events |
|---|
|
9. Type Event Create and document a type Event. An event represents the arrival of a signal at a vertex. An event stores a sender, a receiver and a time at which the signal arrives. The time is an absolute time since the beginning of the simulation. 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
|
|
10. The Event Queue You 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 ItemType in your priority queue module to be typedef Event* ItemType;Make pqueue.h include "event.h" so that it can use type Event. Make sure that you allocate events in the heap. After removing an event from the event queue, delete it when you are finished looking at it. Note. File dijkstra.cpp must 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. |
|
11. Sending a single signal Document 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. |
|
12. Propagating Signals Document and define a function that takes a graph g, a vertex number 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 function from step 11 to send each signal. That is all it should do. Don't add other duties. This function should not look at every vertex. How can it find every vertex that is adjacent to v without looking at every vertex? |
|
13. Processing an Event Document 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. |
| Finding Shortest Paths |
|---|
|
14. Running Dijkstra's Algorithm Document 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. Make sure that the event loop is clear and short. It should look like the event loop outlined above. There should be one line to get the next event and one line to process that event. |
|
15. Showing the Path When the simulation is finished, the shortest distance from the
start vertex s to the end vertex e is e.time.
You can follow a path from e back to s easily.
|
| Tracing |
|---|
|
16. Tracing 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 following.
Make your traces clear and easy to understand. It should not require an expert to read them. Do not show raw data. Make it easy to distinguish sending a signal from receiving a signal (processing an event). 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. |
|
17. Turning Tracing On or Off Use a global variable that holds 0 if tracing is not requested and holds 1 if tracing is requested. 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. The 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. Write a separate function that sets the tracing variable by looking at the command line. The command line is passed to main when the program is started. 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
Watch out when comparing strings. If A and B are null-terminated strings, then expression A == B is true if A and B are the same memory address, since a null-terminated string is a pointer. Use strcmp. |
A Makefile is provided for you. You can use the following commands with it.
As always, you are required to follow the design discussed here. Do not try to invent your own algorithm. Follow the coding standards.
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.
Follow the refinement plan. 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.
Remember to delete events after processing them.
To turn in your work, log into the Linux system, change your
directory for the one for assignment 7,
use the following command.
~abrahamsonk/2530/bin/submit 7 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 7
will show you what you have submitted for
assignment 7.
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 q7. For example, use command
~abrahamsonk/2530/bin/submit q7 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 q7.
If you have another question later, resubmit your new file
as assignment q7.