| Assigned: | Monday, November 5 |
| Due: | Thursday, November 15, 11:59pm |
The purpose of this assignment is to develop your ability to write a larger application involving arrays, structures and linked lists. It also introduces switchable tracing.
Read the entire assignment before you start working on it.
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. They got very low grades.
Remember that you must get an overall grade of at least 50% on the programming assignments to pass this course, and this assignment counts more than most.
After reading the assignment, you might think this assignment is impossibly difficult. It is not. If you just move ahead, creating one piece after another, you will find this simpler than you thought.
The refinement plan has 19 steps. Some are easier than others. You cannot read this assignment and do all 19 steps in 2 days. Set up a schedule. For example, set aside a day for each of the following tasks. (These tasks should not occupy an entire day. You have other things to do too. But don't try to pack them into two or three days. You will end up working inefficiently if you do that.)
That is just an example schedule. Make your schedule appropriate for you. But Start early. Resolve to finish early.
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,
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.
As always, you are required to follow the design that is explained below.
In this assignment, you are allowed to add additional functions. You can also add parameters to required functions that are not mentioned in the design, provided that the roles of those parameters are clearly documented.
A discrete event simulation performs a simulation of a collection of events, where each event occurs at a specified time. The simulation jumps from one event to the next. If one event occurs at 1:00 and the next occurs at 2:00, the simulation does not sit and wait for an hour. It just updates its internal clock to 2:00 and moves on.
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 is a teller queue to hold tellers who are ready to serve customers and a customer queue that holds customers waiting to be served. 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 the next customer" event at the current time.
Notice that processing one event can cause another event to be created.
A customer arrives. Processing a customer arrival adds the customer to the customer queue and also schedules another customer arrival event 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 the next 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 a 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 a customer" event at the current time.
Stop the simulation. Processing this event stops the simulation. At the beginning of the simulation, one of these events is scheduled at a chosen time when the simulation should end.
Typically, when each event is processed, the simulation writes out the current simulation time and the event that is being performed, so that you can see what happened. The simulation also keeps track of some statistics, such as how long a customer waited for service on the average and how long the customer queue got.
It is easy to get the simulation started. If there are t tellers, then schedule t "teller is ready to serve a customer" 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.
Discrete event simulations are useful for implementing 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 or objects at specific times.
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
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. Imagine 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. So, if such a signal is sent at time t, it arrives at time t + w.
In effect, the start vertex broadcasts a radio wave that travels along the edges. When the radio wave hits a vertex v, it bounces off v in all directions, traveling along all edges that are incident on v, in a way that is similar to the way real, physical waves propagate. The edge weights determine how fast the radio wave travels along each edge. It is easy to see that the time when the radio wave first reaches vertex v is proportional to v's distance from the start vertex.
During the simulation, the algorithm keeps two pieces of information about each vertex v: time(v) and sender(v).
Time(v) is the arrival time of the first signal to reach v. If no signal has reached v yet, then time(v) is −1.
Sender(v) is the vertex that sent the signal to v that was the first signal to reach v. If no signal has reached v, then sender(v) is −1.
There is just one kind of event, representing the arrival of a signal at vertex v at time t, where the signal was sent by vertex u. So there are three pieces of information in an event: u, v and t. Let's write that event in a more compact form as event(u, v, t). Notice that, in this convention, u is the sender, v is the receiver and t is the arrival time.
Processing event(u, v, t) goes as follows.
If time(v) ≥ 0, then do nothing, since this is not the first signal to reach v. For the remaining cases, assume that time(v) < 0 when the signal arrives.
Set time(v) = t and sender(v) = u, recording information about the first signal to reach v.
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 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, which should keep going until a signal has reached the end vertex e, that is, until time(e) ≥ 0.
| Getting started |
|---|
|
1. Create a directory for assignment 7 and create
file dijkstra.cpp.
Copy the template into it. Edit the template with your information. 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
In dijkstra.cpp, create and document type Vertex. An object of type Vertex represents information about a vertex in a graph. In the program, each Vertex object will represent one vertex number. For example, there will be a Vertex object for vertex 1, another for vertex 2, etc. A Vertex object that represents information about vertex number v has the following pieces of information.
Create a constructor for type Vertex that takes no parameters, sets the 'time' and 'sender' fields to −1, and sets the adjacency list pointer to NULL. |
|
3. Type Edge
In dijkstra.cpp, create and document type Edge. An object of type Edge is a cell in an adjacency list. It represents an edge of the graph. In the documentation for type Edge, make sure that you say that an object of type Edge is used as 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 of an Edge. Important note. Because an edge is broken into two one-way parts, an edge between u and v must occur in two adjacency lists. The adjacency list for vertex u contains an edge directed from u to v. The adjacency list for vertex v contains an edge directed from v to u. |
|
4. Type Graph
In dijkstra.cpp, create and document type Graph. An object of type Graph represents a weighted graph and 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 time(v) for the time stored with vertex number v. But that is not how it is referred to in the C++ program. If you have Graph g, how can you get the time stored for vertex number 1 in g? How can you get the time stored for vertex number v? Look at your diagram. |
| Tracing |
|---|
|
6. Setting up tracing
You are required to put switchable tracing in your program. For now, just get ready for tracing. In dijkstra.cpp, create 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 in this course. Just create 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. 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". In dijkstra.cpp, write a function that takes parameters argc and argv that are passed to main and that sets your global trace variable either to 0 or to 1. If some option other than -t is provided,
then your function must write a line
exit(1);Include <cstdlib> to use exit. 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 to compare strings. |
| Input and echoing |
|---|
|
7. Reading the Graph
In dijkstra.cpp, 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. Make this function only read the graph. Do not give it any additional responsibilities. In particular, it should not write anything. |
|
8. Writing a Graph
In dijkstra.cpp, 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. Make this function only write the graph. Do not give it any additional responsibilities. Do not say what this graph is. For example, do not say that it is the "input graph". Just show the information in the graph. It is the caller's responsibility to say what this graph is. 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 only once. That is easy to arrange. When looking at an edge that is directed from u to v, only show it if u < v. |
|
9. 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. An automated trace is available. You can use it for all tests. |
| Events |
|---|
|
10. Type Event
Create file event.h. In event.h, create and document type Event. An object of type Event represents the arrival of a signal at a vertex. An event stores: a sender (a vertex number), a receiver (a vertex number) and a time at which the signal arrives. The time is an absolute time since the beginning of the simulation. File event.h should look as follows, with the line calling for documentation of type Event replaced by actual documentation and the body of type Event added.
#ifndef EVENT_H
#define EVENT_H
(documentation for type Event)
struct Event
{
…
};
#endif
The #ifndef, #define and #endif ensure that file event.h will only be read once by the compiler, even if it is included more than once. |
|
11. The Event Queue
Notice that the operations needed for events are exactly the ones supported by a priority queue. You need to get the next event in chronological order. That is easy to arrange. The priority of an event is its time. Let's refer to a priority queue holding events as the event queue. Add the following type definition to dijkstra.cpp. typedef PriorityQueue EventQueueUse type EventQueue for the type of the event queue. Copy files pqueue.h and pqueue.cpp from assignment 6 into your directory for assignment 7. Modify the definition of ItemType in pqueue.h to say typedef Event* ItemType; File pqueue.h must include "event.h" so that it can use type Event. That is, add directive #include "event.h"to pqueue.h before the definition of type ItemType. Allocate all events in the heap. After removing an event from the event queue, delete it when you are finished looking at it. Note 1. 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. See the priority queue interface. Note 2. The priority queue module does not export types ItemType or PriorityType. Do not use those types in dijkstra.cpp. Note 3. When passing the event queue to a function, always pass it by reference or by pointer. There must only be one copy of the event queue. |
|
12. Sending a single signal
In dijkstra.cpp, 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. |
|
13. Tracing
In dijkstra.cpp, add tracing to your function that sends a signal. When a signal is sent, the program should say that it is sending a signal. Show the time when the signal is sent, the arrival time, the signal's sender and the signal's receiver. In all traces, start each line with the current time in the simulation. That greatly enhances the readability of the trace. |
|
14. Propagating Signals
In dijkstra.cpp, 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 12 to send each signal. That is all it should do. Don't add other duties. This function should not look at every vertex in graph g. How can it find every vertex that is adjacent to v without looking at every vertex in g? |
|
15. Processing an Event
In dijkstra.cpp, document and define a function that takes a graph g, an event queue q and an event e, and that processes event e. Note that this function processes a single given event. That is all it does. Don't add any other duties. This function does not get an event out of q. But it might need to add new events to q. |
|
16. Tracing
Add tracing to the function that processes an event. The trace should start with the arrival time stored in the event. It should also show the sender and the receiver. If the 'sender' and 'time' fields are updated for the receiver, show the new values of those fields. But continue to follow the rule that every trace line begins with the current time in the simulation.
Make it easy to distinguish between a trace of an signal being sent and a signal arriving. The trace should only be shown if tracing is turned on. |
| Finding Shortest Paths | ||
|---|---|---|
|
17. Running Dijkstra's Algorithm
In dijkstra.cpp, 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. (Do not add vertex 0 to the graph! There is no such vertex.) Then it goes into the event loop. It keeps getting and processing events until a time(e) ≥ 0 for the end vertex e. 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. Be sure to get the event before processing the event. Make your event loop look like the one above. | ||
|
18. Showing the Path
In dijkstra.cpp, document and define a function that takes a graph g and two vertex numbers start and end. It should be called when the simulation is finished, and should show the path from start to end. It must not do anything but that. Using the information in g, it is easy to follow a path from end vertex e back to start vertex s.
But print that chain out backwards, so that it goes from s to e instead of from e 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 sender(u) backwards, then print u. Of course, in the special case where u is the start vertex s, just print s. For arrows, write -> between vertex numbers. | ||
|
19. Show the shortest distance and path
In dijkstra.cpp, modify main so that it shows the shortest distance from the start vertex to the end vertex and also shows the path from the start vertex to the end vertex. Be sure that it is clear, in the output, what is being shown. Don't write out raw information and force the reader to guess what it is. The shortest distance from start vertex s to the end vertex e is time(e). |
Get files Makefile and dotest and put them into the directory that holds assignment 7. Then uou can use the following commands.
As always, you are required to follow the design discussed here. Do not try to invent your own algorithm. Follow the coding standards.
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 yourself stuck in the swamp and this program will be even harder than you originally thought.
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.
It is easy to write contracts. The assignment tells you what each function is supposed to do. It is hands you a contract. Just edit it to make sense in a program. For example, a contract should not begin "Arite a function that …"
Avoid complicated algorithms. Keep it simple.
Keep your program organized, well-indented, documented 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.
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.
Be sure to initialize variables before you use them. In the past, this has been a source of mistakes for students.
Be sure to distinguish between vertices and edges. Do not use numEdges where you should have used numVertices. In the past, this has been a common source of mistakes.
In the past, some students have, at some places in dijkstra.cpp, used type int for an edge weight or for a time/distance value. That causes all distances to be forced to integers, which means that the results are incorrect when the correct distance is not an integer. Make sure that all time/distance values have type double.
Keep function definitions short and simple. A function body must have no more than 16 noncomment lines.
Do not use global variables other than one to control tracing, regardless of how appealing you find them.
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.