Computer Science 3200
Fall 2015
Section 001
Programming Assignment 5

Table of contents

1. Background: weighted graphs
2. The assignment
3. Representing graphs
4. An algorithm
5. The event queue
6. A design and plan
7. Nonfunctional requirements
8. Extra credit
9. Submitting your work

Background: weighted graphs

---

graph is a collection of vertices connected by a collection of edges. An edge connects exactly two different vertices to one another. You can draw a picture of a graph by showing the vertices as circles and the edges as lines connecting them. Here is an example.

A path from vertex v₁ to vertex v_k is a sequence of vertices (v₁, v₂, …, v_k) such that there is an edge between v_i and v_i+1, for i = 1, …, n − 1.

We will only be concerned with connected graphs. A graph is connected if there is a path from every vertex to every other vertex. For example, in the above graph, there is a path from 3 to 4 that goes (3, 1, 2, 4). There are other paths from 3 to 4 as well. For any two vertices u and v, there is a path from u to v.

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.

A weighted graph is a graph in which each edge has a number attached to it, called the weight of the edge. Here is a picture of a weighted graph.

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 above 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. You add the weights of the edges that you use.

For this assignment, the weights are real numbers (type double). All of the weights are positive.

The assignment

---

The input starts with a line that tells how many vertices the graph has. If there are five vertices, then those vertices have numbers 1, 2, 3, 4 and 5. In general, if there are n vertices, then they are numbered 1, …, n.

Following the first line are the edges, one per line. Each edge line has three integers on it. Line

2 4 50.0

with start vertex 1 and end vertex 5 might look like this.

5
1 2  9
1 3 12
2 4 18
2 3  6
2 5 20
3 5 15
0
1 5

Your program must show the graph and compute the shortest from the start vertex to the end vertex. For the sample input, the output would be

There are 5 vertices.  The adjacency lists are as follows.

Vertex 1
  to 3, weight 12.00
  to 2, weight 9.00
Vertex 2
  to 4, weight 18.00
  to 3, weight 6.00
  to 5, weight 20.00
  to 1, weight 9.00
Vertex 3
  to 5, weight 15.00
  to 2, weight 6.00
  to 1, weight 12.0
Vertex 4
  to 2, weight 18.00
Vertex 5
  to 3, weight 15.00
  to 1, weight 12.00

The shortest distance from 1 to 5 is 27.

Representing graphs

---

Use the linked list class provided. Read the class to see what is provided.

Represent a graph as an array of PairLists. If the array is called adj, then adj[i] is a list of pairs (j,w) so that there is an edge from i to j of weight w. (If x is a List2 object, then x.vertex is the value j and x.weight is the weight.) Consider the following graph.

Notice that an edge between vertices u and v can be thought of as going from u to v or from v to u. So it shows up in two lists. Here is a representation. For brevity, I show a list in square brackets; each item in a list is a pair (j,w) of a vertex number j and a weight w, in that order.

   index   list
     0      -
     1     [(3,12), (2,9)]
     2     [(1,9),  (3,6), (5,20), (4,18)]
     3     [(1,12), (2,6), (5,15)]
     4     [(2,18)]
     5     [(3,15), (2,20)]

For example, pair (3,6) occurs in the list at index 2, indicating that there is an edge from vertex 2 to vertex 3 of weight 6. The order of the lists does not matter. Index 0 is not used.

For this assignment, you will also need another array, distance, so that distance[i] = −1 if the distance from the start vertex to vertex i is currently unknown, and distance[i] = x if the distance from the start vertex to vertex i is known to be x.

An algorithm

---

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 (and from which vertex the signal was sent). (The time is really the distance. We are computing distances, but 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 out along the edges that are incident on 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 (2 seconds after it was sent from vertex 2).

A vertex can receive more than one signal. Only the first signal that it receives is meaningful. The second and subsequent times a signal arrives at a vertex, the signal is ignored.

The algorithm is finished when a signal reaches the end vertex. The time at which the signal arrived at the end vertex is the distance from the start vertex to the end vertex.

Events

An event is the arrival of a signal at a given vertex, at a given time. The algorithm handles events in chronological order.

The algorithm maintains an event queue that holds events in chronological order. The main structure of the algorithm is as follows.

1. Add the first event to the event queue. It arrives at the start vertex at time 0, to get the algorithm going.

2. While the end vertex has an unknown distance

   1. Get the next event in chronological order. Suppose that it indicates a signal arriving at vertex v at time t.

   2. If vertex v has an unknown distance then

      1. Set distance[v] = t.

      2. For each vertex u that is adjacent to v

         1. Let w be the weight of the edge from v to u.

         2. If u has an unknown distance then

            • Create a new event e indicating a signal arriving at vertex u at time t+w (w seconds in the future from t).
            • Add event e to the event queue.

The event queue

---

The Java API provides a class java.util.PriorityQueue. Use a PriorityQueue for the event queue. Read about class PriorityQueue in the Java documentation. You will use type PriorityQueue<Event>. You will want to use the following. (I assume that you import java.util.PriorityQueue.)

• new PriorityQueue( ) returns a new empty priority queue.

• q.add(e) adds event e to priority queue q.

• q.poll( ) removes and returns the smallest event in queue q, or returns null if the queue is empty.

• q.size( ) is the number of events in queue q.

A design and plan

---

There will be three classes. Put them all in the same file, ShortestPath.java.

1. Create a class called Graph. It should contain the following.

   1. A private variable adj that is an array of PairLists.

   2. A public constructor so that new Graph(n) yields a new graph with its adj variable set to an array of n+1 cells.

   3. A public accessor getAdjacencyList( ) so that g.getAdjacencyList(v) returns the adjacency list for vertex v. (A vertex is an integer from 1 to n.)

   4. A public instance method insert(u, v, w) that adds an edge between u and v, of weight w. It must add (v, w) to the adjacency list of u and add (u, w) to the adjacency list of v.

   5. A public instance method show( ) so that g.show() shows all of the adjacency lists, in the format shown in the example above.

2. Create the main class, ShortestPath. Make it a public class. Create a static method readGraph( ) that reads the description of a graph, starting with the first line containing the number of vertices and ending after it has read the 0 at the end of the edges. readGraph() should return the graph.

3. Add private static variables to class ShortestPath holding:

   1. the graph,
   2. the array of distances,
   3. the event queue,
   4. the start vertex,
   5. the end vertex.
   All of the methods in class ShortestPath share these variables.

4. Create a main method that initializes all of the static variables. It should initialize the graph by reading it. After initialization, main should show the graph.

   Test your program. Do not continue until it what you have written is working.

5. Create a class Event. Its heading should be

     class Event implements Comparable<Event>
   

   Phrase implements Comparable<Event> indicates that two events can be compared to determine which is larger, or whether they are equal.

   Class Event should contain the following.

   1. Private variables vertex and time, telling the vertex where this signal arrives and the time of its arrival.

   2. A public constructor so that new Event(v, t) yields a new Event object with vertex v and time t.

   3. A public accessor getVertex( ) so that e.getVertex() returns the vertex stored in event e.

   4. A public accessor getTime( ) so that e.getTime() returns the time stored in event e.

   5. A public instance method compareTo(Event d) so that e.compareTo(d) returns s − t, where s is e's time and t is d 's time. This method defines the natural ordering of events, indicating that events are ordered according to their times.

6. Add a static method to your ShortestPath class that takes a vertex v and a time t. It should simulate sending signals from vertex v at time t to v's adjacent vertices by creating an event for each vertex adjacent vertex u whose distance is unknown.

7. Add a static method to your ShortestPath class that performs a single event. It should take the event as a parameter. If the vertex v that receives the signal has an unknown distance, then it should set v's distance to the time at which the event occurs and simulate sending signals to vertices that are adjacent to v. Do not do anything if v already has a known distance.

8. Add a static method to your ShortestPath class that performs the simulation by successively getting events out of the event queue and processing the events until the end vertex has a known distance.

9. Modify main so that, after reading and showing the graph, it inserts an initial event and then runs the simulation. After the simulation is done, it should show the distance from the start vertex to the end vertex. (Where is it stored?)

Tip. You will probably find it useful to add a trace print to your method that handles an event that shows the event that it is processing, in a clear and readable form. That way, you can look at the sequence of events to see that they are being done correctly. It might also be useful to trace events being added to the event queue.

Nonfunctional requirements

---

Use sensible terminology in your program. If something is a graph, do not call it an edge. If something is an edge, do not call it a vertex. Make variable and type names sensible. Keep methods short, simple and readable. Indent correctly.

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

Extra credit

---

For extra credit, show not only the distance from the start vertex to the end vertex but also the path that has that distance. That involves the following.

1. Modify the event class so that it also remembers which vertex sent the signal.

2. Add another private static variable prev that is an array of integers, where

   1. If the distance of vertex v is known, then prev[v] is the number of the vertex that sent the first signal to arrive at vertex v.

   2. If the distance of vertex v is unknown, then prev[v] is −1.

   Keep the prev array up to date while processing events.

3. When the simulation is finished, the path from the end vertex t back to the start vertex s is t, prev[t], prev[prev[t]], … Print that path backwards. An easy way to do that is by recursion. Suppose that the correct forward path (from start vertex 3 to end vertex 4) is (3, 7, 2, 5, 4). Start by showing the path from 3 to 5. (5 = prev[4].) Then show 4. To show the path from the start vertex to itself, just show the start vertex.

   Show the path as in the following example.

     The path from 3 to 4 is 3 -> 7 -> 2 -> 5 -> 4
   

   So add -> before each vertex except the start vertex.

Submitting Your Work

---

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

  ~abrahamsonk/3200/bin/submit 5 ShortestPath.java

Command

  ~abrahamsonk/3200/bin/submit 5

You can do repeated submissions. New submissions will replace old ones.

Late submissions

Late submissions will be accepted for one day after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.