| Assigned: | Thursday, April 9 |
| Due: | Sunday, April 26, 11:59pm |
| Points: | 700 |
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.
You will need to define 3 structure types and roughly 15 functions, including main, depending on how you write this assignment. (Having more functions is not necessarily worse!)
Read the entire assignment before you start working on it.
You will need to submit three files, dijkstra.cpp, pqueue.cpp and pqueue.h. Submit pqueue.h and pqueue.cpp even if you think that I already have them.
When faced with a large assignment near the end of a term, many students turn to plagiarism, especially if they have waited too long to start on the assignment.
Do not fall into that trap and submit a plagiarized assignment. Keep in mind that you must get an overall weighted score of 50% or better on the programming assignments in order to pass this course, and that a plagiarized assignment gets a negative score.
Submitting plagiarized or partially plagiarized work can cause you to fail this course.
Start early. 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.
After reading this assignment, you might think it is impossibly difficult. It is not. If you just move ahead, creating one piece after another, and give yourself time, you will find this simpler than you thought.
Write this program in stages. Do not try to do it all in two or three days. Start by reading the assignment all the way through. Then, the next day, read it again.
You are required to use successive refinement. The following refinement barriers will be enforced.
If your Edge, Vertex Graph types are unusable, then you will receive no credit except for partial credit for those type and possibly a function that sets tracing, regardless of how much you have written.
If readGraph is so bad that it cannot possibly provide a graph to be processed by the remaining functions, then you will only receive credit for types Edge, Vertex and Graph, readGraph and functions that support it, writeGraph and functions that support it, and a function to set tracing, regardless of how much else you have written.
If your code to perform Dijkstra's algorithm is so bad that your program cannot even get to the step of printing the shortest path, you will not receive credit for a function that prints the shortest path, even if you have written one that is correct.
This assignment uses weighted graphs, as described in assignment 5.
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, or the amount of time it takes to drive 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. The total distance (or time) is the sum of the weights of the edges in the path. 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.
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 vstart and an end vertex vend.
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 5That 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. All edges are undirected. The line containing only 0 indicates the end of the edges. The start vertex vstart is 1, and the end vertex vend 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 -> 5The order of the edges in the graph description is not important, but each edge should be shown once unless tracing is requested.
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, provided that the roles of those parameters are clearly documented. Choose sensible names for functions and parameters.
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.
Here is a typical trace of a simulation. Notice that each trace line begins with the current time.
0.0 teller 1 is ready.
0.0 teller 2 is ready.
0.0 customer 1 arrives.
0.0 teller 1 begins to serve customer 1.
3.5 customer 2 arrives.
3.5 teller 2 begins to serve customer 2.
4.0 teller 1 finishes serving customer 1.
4.0 teller 1 is ready.
5.0 customer 3 arrives.
5.0 teller 1 begins to serve customer 3.
6.1 customer 4 arrives.
10.0 teller 2 finishes serving customer 2.
10.0 teller 2 is ready.
10.0 teller 2 begins to serve customer 4.
11.0 customer 5 arrives.
15.0 customer 6 arrives.
18.5 teller 2 finishes serving customer 4.
18.5 teller 2 is ready.
18.5 teller 2 begins to server customer 5.
end of simulation
Discrete event simulations are useful for implementing games. Each event is something that happens in the game, such as a character entering the game or 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 (DYKE-stra'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. 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 and reflect. 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 equivalent 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 that was sent by vertex s to vertex r, arriving at time t. So there are three pieces of information in an event: s, r and t. Let's write that event in a more compact form as event(s, r, t), where s is the sender, r is the receiver and t is the arrival time.
Processing event(s, r, t) goes as follows.
If time(r) ≥ 0, then do nothing, since this is not the first signal to reach r. For the remaining cases, assume that time(r) < 0 when the signal arrives.
Set time(r) = t and sender(r) = s.
For each vertex v that is adjacent to r, where no signal has yet reached v, send a signal from r to v by scheduling event(r, v, t + w) where w is the weight of the edge from r to v. That is, this signal arrives at v just w seconds after the signal reaches r.
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 vend, that is, until time(vend) ≥ 0.
Create a directory for assignment 7. Download files
into that directory.Create file dijkstra.cpp and copy the template into dijkstra.cpp. Edit the template with your information.
Add a comment to dijkstra.cpp telling its purpose. Say what this program reads and what it writes. Include a description of the input format as well as an example input and output. Assume that the reader understands graph terminology. Do not describe Dijkstra's algorithm.
This assignment uses a different graph representation from assignment 5. Here, we use the adjacency list representation.
Edge
Important note. Although each edge in the graph has no direction associated with it, the adjacency list representation involves splitting each edge into two directed edges, one going each direction. Think of splitting a bidirectional road into two lanes, one for each direction. We will talk about an edge directed from u to v.
Because an edge is broken into two one-way parts, an undirected 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.
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:
Two vertex numbers from and to, indicating that the edge is directed from vertex from to to vertex to. Document the direction of the edge.
A weight w of the edge, of type double.
A pointer next that points to the next Edge in the linked list.
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.
Vertex
An object of type Vertex represents information about one vertex v in a graph. It must contain
A pointer to a linked list of all edges edges from v to another vertex. This list is called an adjacency list, since it shows the vertices that are adjacent to v. The list cells have type Edge.
A real number indicating v's shortest distance (or time) from the start vertex. This number is −1 if the distance (or time) is not yet known. (This is the number called time(v) above. Descriptions of algorithms use convenient notation, not necessarily the notation that you find in a C++ program.)
A vertex number sender. (This is the number called sender(v) above.) After a signal has reached vertex v, the shortest path from v back to the start vertex begins by going from v to sender(v). The senders allow you to reconstruct the entire shortest path.
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.
Graph
An object of type Graph represents a weighted graph and stores the following.
The number of vertices.
The number of edges.
An array, vertices, where vertices[v] is a Vertex structure giving information about vertex v.
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.
Draw an accurate diagram of the representation of a small sample graph. Not doing that 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 a pointer g of type Graph*, 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.
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. If the variable is called tracing, write
int tracing = 0;before any function definition in dijkstra.cpp. This is the only place where you are allowed to use a global variable in this course.
If a function performs a trace, it must say
if(tracing > 0)
{
…
}
so that the trace is only shown if tracing is positive. There must be no traces that are always done, regardless of whether tracing is turned on.
Note. If f is a function that has some purpose other than just tracing, but f performs some tracing, do not state that f does tracing in f 's contract. That is not part of f 's official behavior, but is only added for debugging purposes.
The template that you installed in dijkstra.cpp contains a heading for main with two parameters, argc and argv, where argv is an array that holds the components of the command line and argc is the size of argv. For example, if the command that invokes your program is
./dijkstra -tthen argc is 2, argv[0] is "./dijkstra" and argv[1] is "-t".
Command line argument -t requests tracing. If it is not present, there should be no tracing.
Write a function to set tracing if requested. It must not look at any index of argc that does not exist. By default, tracing is 0. If argc is 2 and argv[1] is -t, your function should make tracing = 1.
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.
In dijkstra.cpp, document and define a function to read a graph. You can use your function from assignment 5 as a rough 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. /p>
Make this function only read the graph. Do not give it any additional responsibilities. In particular, it should not write anything, except possibly traces.
You will want two helper functions to avoid code duplication and to avoid making readGraph too long. Write one helper function that inserts one edge into one adjacency list. Write another that inserts an edge into a graph by inserting it (in opposite directions) into two adjacency lists.
In dijkstra.cpp, document and define a function to print a graph. Make this function only write the graph. Do not give it any additional responsibilities.
Do not write a label for the graph. 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 directed edge so that you can see the structure of the adjacency lists. If tracing is turned off, then show each undirected 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.
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.
Create file event.h. In event.h, create and document type Event, where 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 total time since the beginning of the simulation.
Include a sensible constructor for Event to make creating events easier.
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.
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 by making the priority of an event be 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 EventQueue
Use 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 ItemT in pqueue.h to say
typedef Event* ItemT;
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 ItemT.
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 are part of the interface. 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 lose a lot of points if you violate the interface.
Note 2. The priority queue module does not export types ItemT or PriorityT. Do not use those types in dijkstra.cpp. Use type Event*, not ItemT, and use type double, not PriorityT.
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.
In dijkstra.cpp, document and define a function that takes two vertex numbers s and r, a time t and an event queue q. It should send a signal from s to r, arriving at time t, by inserting an event into q. That is all it should do. Don't add other duties (other than tracing).
You might find additional parameters useful.
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. Make the trace only one line long and make that line begin with the current time, as shown in the sample trace above. Also show the sender, the receiver and the signals' arrival time. Make the trace succinct, but make it clear that it is telling about a signal being sent. Do not confuse the current time with the signal's arrival time.
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 the preceding step to send each signal.
That is all it should do. Don't add other duties (except tracing).
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?
In dijkstra.cpp, document and define a function that takes a graph g, a vertex number v, a vertex number s and a time t, and stores sender s and time (or distance) t into the Vertex structure that represents vertex number v in g.
Add tracing to the function that you just wrote that shows the information that is being stored for a vertex. The trace must be one line long, and it must start with the current time. Make it clear and readable.
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 (except tracing). This function does not get an event out of q. But it might need to add new events to q.
Remember that, if vertex f has already received a signal, then the arrival of another signal at f should be ignored. Make your event processor do nothing at all (except tracing) when a second or subsequent signal arrives at r.
Suppose that event E represents the arrival of a signal at vertex r, and that r has not yet received a signal. Processing E involves
Use your functions for propagating signals and installing information into a vertex.
Add tracing to the your event-processing function. Suppose that the event represents a signal from u to v, arriving at time t. If the signal is being ignored, the event processor should say something like "t signal from u to v ignored." If the signal is not being ignored, it should say something like "t signal arrival from u to v."
Important note. Do not put off writing signals. A line showing that a signal has arrived should occur before any lines showing things that occur as a consequence of that arrival.
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(vend) ≥ 0.
Make sure that the event loop is clear and short. It should look like the event loop outlined above. It should get an event then process the event, in that order.
Make main call your function that performs the simulation. Test it with tracing turned on. Look at the trace. Does the simulation look right? Are the correct distances installed in vertices? A few traces in a row can happen at the same time, but time should never get smaller as the trace continues.
In dijkstra.cpp, document and define a function that takes a graph g and two vertex numbers vstart and vend. It should be called when the simulation is finished, and should show the path from vstart to vend. It must not do anything but that.
Using the information in g, it is easy to follow a path from end vertex vend back to start vertex vstart.
| vend → sender(vend) → sender(sender(vend) → … → vstart |
But print that chain out backwards, so that it goes from vstart to vend instead of from vend to vstart. 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 vstart, just print vstart. For arrows, write -> between vertex numbers.
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 the output is easy to read.
Do not try to compute the shortest distance (or time) using a loop of something like that. You already have it. The shortest distance from vstart to vend is time(vend).
Test dijkstra.cpp with tracing on and with tracing off.
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 nothing but junk.
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 hands you a contract. Just edit it to make sense in a program. For example, a contract should not begin "Write a function that …". It should not describe the function heading, since that is visible.
Avoid complicated algorithms. Keep it simple. Function bodies should be easy to read and understand. Avoid writing a long expression more than once by storing its value in a variable.
Keep your program organized, well-indented, documented and easy to read while you write it, not as an afterthought.
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.
Look at the test results. Has a value that should not be an integer been forced to be an integer?
Keep function definitions short. 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. You will lose a lot of points for using a global variable, and more for using two global variables.
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.cppAfter 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 7will 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.cppInclude 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.