Computer Science 2530
Spring 2017
Programming Assignment 6

Assigned:	Monday, March 13
Due:	Tuesday, March 28, 11:59pm

Purpose of this assignment
Graphs and terminology
Assignment requirements
Representing Graphs: Types Vertex, Edge and Graph
Input and echoing
Dijkstra's algorithm and discrete event simulation
Design and development plan
Tracing
Compiling, linking and running
Things to watch out for
Submitting your work
Asking questions

Purpose of This Assignment

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.

Graphs and Terminology

This assignment uses weighted graphs, as described in assignment 4. 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.

Assignment Requirements

Functional Requirements

Write a program that reads information about a weighted graph from the standard input. The input format is described in detail below. After the edges, 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.

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 0 indicates the end of the edges. 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

Nonfunctional Requirements

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. Follow the design.

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. Remember that a function cannot have more than 15 noncomment lines in its body.

As always, you must follow the coding standards for this course.

Representing Graphs: Types Vertex, Edge and Graph

This assignment uses a different graph representation from assignment 4. Here, we use the adjacency list representation.

Types and information representation
1. Type Vertex Create and document type Vertex. Each vertex v has the following pieces of information. A pointer to a linked list of edges listing all edges that are incident on v. This list is called an adjacency list. A real number indicating v's shortest distance from the start vertex. This number is −1 if the distance is not yet known. A boolean value, signaled, that tells whether a signal has reached vertex v. Signals are discussed below. *A vertex number prev. After a signal has reached vertex v, the shortest path from v to the start vertex begins by going from v to prev.* Create a constructor for type Vertex that takes no parameters and sets signaled to false and sets the linked list to NULL.

2. Type Edge Create and document type Edge. Type Edge is used for a cell in an adjacency list. The Edge structure stores: Two vertex numbers u and v. A weight w. 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. 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.

3. Type Graph Create and document type Graph. A graph 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 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.

Input and Echoing

Input and echoing
4. Reading the Graph Document and define a function to read a graph. You can use your function from assignment 4 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. Only store the graph once. The contract for this function should describe the input format and show an example input.

5. Printing a Graph Document 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. Testing Test reading and echoing the graph. Do not move on until you are satisfied that this much works.

Dijkstra's Algorithm and Discrete Event Simulation

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 as v's distance the vertex that the signal came from at v's previous vertex. (We are computing distances, so the time is really a distance. 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 to all vertices that are adjacent to 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 (It was sent after 5.1 seconds into the simulation, and it arrives at vertex 3 two seconds later.).

A vertex can receive more than one signal. Only the first signal that it receives is meaningful. The second and subsequent signals are 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.

Let's write prev(u) for u's previous vertex: the number of the vertex from which the first signal reached vertex u. Then path [u, prev(u), prev(prev(u)), …, s] is the shortest path from u back to the start vertex s. The path from s to u is the reversal of that.

Discrete Event Simulation

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, (sender, receiver, time), and indicates the arrival of a signal from vertex sender at vertex receiver at time time. The time of an event is always the total time since the beginning of the simulation.

The idea is to store the events in increasing order by time into an event queue. The program repetitively performs the following steps. This loop is called the event loop. For brevity, I write prev(v) for g.vertices[v].prev, dist(v) for g.vertices[v].distance and signaled(v) for g.vertices[v].signaled.

Get the next event E = (sender, receiver, t) representing the arrival of a signal from sender to receiver 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 from the event queue.
If no signal has yet arrived at vertex receiver, then process event E, as follows. I will refer to receiver as v.
1. Record signaled(v) = true, prev(v) = sender, distance(v) = t.
2. 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 send a signal from v to x.
  
  You send a signal simply by inserting an event representing the signal's arrival into the event queue. The signal from v to x arrives at time t + w.
Repeat. Keep doing (get an event; process the event) until a signal has reached the end vertex.

Design and Development Plan

Development plan

Development plan
7. Events Create 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 // documentation for type Event struct Event { … }; #endif

8. 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 PQItemType in your priority queue module to be typedef Event* PQItemType; Make pqueue.h include "event.h" so that it can use type 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 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.*

9. 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.
10. Sending Signals Document and define a function that takes a graph g, a vertex 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 preceding one to send each signal. That is all it should do. Don't add other duties.

11. 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. Suppose the event represents a signal from vertex sender to vertex receiver that arrives at time t. If vertex receiver has previously received a signal, do nothing. Throw this event away. But if no signal has yet reached receiver, then set receiver's signaled variable to true, store sender as receivers's previous vertex and store t as receiver's distance. Then send a signal to each vertex that is adjacent to v (and that has not already received a signal).

12. 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.

13. Showing the Path When the simulation is finished, the shortest distance from the start vertex s to the end vertex t is simply the distance stored with vertex t. You can follow a path from t back to s easily. t -----> prev(t) -------> prev(prev(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 previous(u) backwards, then print u. Of course, in the special case where u is the start vertex s, just print s. Put `->` between vertex numbers.

7. Events

Create 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

// documentation for type Event

struct Event
{
  …
};

#endif

8. 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 PQItemType in your priority queue module to be

  typedef Event* PQItemType;

Make pqueue.h include "event.h" so that it can use type 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 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.

9. 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.

10. Sending Signals

Document and define a function that takes a graph g, a vertex 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 preceding one to send each signal.

That is all it should do. Don't add other duties.

11. 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.

Suppose the event represents a signal from vertex sender to vertex receiver that arrives at time t. If vertex receiver has previously received a signal, do nothing. Throw this event away.

But if no signal has yet reached receiver, then

set receiver's signaled variable to true,
store sender as receivers's previous vertex and
store t as receiver's distance.

Then send a signal to each vertex that is adjacent to v (and that has not already received a signal).

12. 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.

13. Showing the Path

When the simulation is finished, the shortest distance from the start vertex s to the end vertex t is simply the distance stored with vertex t. You can follow a path from t back to s easily.

     t -----> prev(t) -------> prev(prev(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 previous(u) backwards, then print u. Of course, in the special case where u is the start vertex s, just print s. Put -> between vertex numbers.

Tracing

Tracing
14. 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. When a signal is sent, the program should say that it is sending a signal. Show the signal's sender, receiver and arrival time. When an event is processed, show the event, and indicate that a signal is arriving. Show the event's sender, receiver time. Show updates of the prev and distance fields when the first signal arrives at a vertex. Provide information about the vertex whose information is being modified and what the new information is. 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.

15. Turning Tracing On or Off 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. 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 -t then 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 usage: dijkstra [-t]** and stop.

14. 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.

When a signal is sent, the program should say that it is sending a signal. Show the signal's sender, receiver and arrival time.
When an event is processed, show the event, and indicate that a signal is arriving. Show the event's sender, receiver time.
Show updates of the prev and distance fields when the first signal arrives at a vertex. Provide information about the vertex whose information is being modified and what the new information is.

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.

15. Turning Tracing On or Off

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.

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 -t
then 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

  usage: dijkstra [-t]

and stop.

Compiling, Linking and Running

A Makefile is provided for you. You can use the following commands with it.

make dijkstra: Just compile pqueue.cpp and dijkstra.cpp, if necessary, and link them to create executable file dijkstra.
make pqueue.o: Just compile pqueue.cpp, if necessary.
make dijkstra.o: Just compile dijkstra.cpp, if necessary.
make test: Do make dijkstra then run it.
make debug: Do make dijkstra then run it via the gdb debugger.
make clean: Remove all machine-generated files.

Things to watch out for

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.

Use successive refinement. 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.
Delete events after handling them.

Submitting Your Work

To turn in your work, log into the Linux system, change your directory for the one for assignment 6, use the following command.

  ~abrahamsonk/2530/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/2530/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

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.

Asking questions

To ask a question about your program, first submit it, but use assignment name q6. For example, use command

  ~abrahamsonk/2530/bin/submit q6 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 q6. If you have another question later, resubmit your new file as assignment q6.

Computer Science 2530 Spring 2017 Programming Assignment 6

Table of Contents