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.

In dijkstra.cpp, create and document type Vertex. An object of type Vertex represents information about a vertex in a graph. 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. (This is the number called v.time above.)

• A vertex number from. (This is the number called v.from above.) After a signal has reached vertex v, the shortest path from v back to the start vertex begins by going from v to v.from.

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.

Note. Type Vertex will be used as part of the representation of a graph. In the rest of the program, use vertex numbers, not objects of type Vertex. Add the following type definition to dijkstra.cpp.

  typedef int vertexNumber;

In dijkstra.cpp, create and document type Edge. An object of type Edge represents an edge of the graph and is used for a cell in an adjacency list. 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 u and v. Even though the graph is undirected, it is important to think of this edge as directed from u to v. It will be used in that direction in a path from the start vertex to the end vertex. Document that important fact. Pay attention to this! Ignore it at your peril.

• 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. Think of a bidirectional road being split into two one-way roads. See the remark above about u and v.

In dijkstra.cpp, create and document type 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.

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? How can you get the time stored for vertex number v?

You are required to implement tracing for this assignment. 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. 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.

The command line is passed to main when the program is started. Use the following heading for main.

 int main(int argc, char* argv[])

  ./dijkstra -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

  usage: dijkstra [-t]

  exit(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.

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

Do not print the graph while reading it. Use a separate function.

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 once. That is easy to arrange. When looking at an edge 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. 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.

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. Add the following type definition to dijkstra.cpp.

  typedef PriorityQueue EventQueue

Create a copy of files 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. That is, add directive

  #include "event.h"

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. See the priority queue interface.

Note. The priority queue module does not export types ItemType or PriorityType. Do not use those types in dijkstra.cpp.

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.

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.

Show the time at which the signal is sent first. Make all traces, including those added later, always show the current time first, with all times aligned for easy reading.

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?

In dijkstra.cpp, 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.

Add tracing to the function that processes an event. Show that a signal is arriving at a given vertex. Show the time at which the signal arrives, which vertex receives the signal and which vertex sent the signal. If the from and time fields are updated for the receiver, show the new values of those fields.

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.

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!) 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. Be sure to get the event before processing the event.

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.

     e -------> e.from -------> e.from.from ----> ... -----> s

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 what is being shown. Don't write out raw information.

The shortest distance from start vertex s to the end vertex e is e.time.