CMPS 101

CMPS 101
Abstract Data Types
Winter 2000

Programming Assignment #3 : Finding Shortest Paths
Due Friday February 18, 12:00 midnight

The purpose of this assignment is to understand and implement a graph ADT and associated algorithms. The adjacency list representation of a graph consists of a sequence of lists, one for each vertex in the graph, where each list gives the neighbors of the corresponding vertex. For instance, the graph

(See the graph on six vertices pictured in the pa3 handout)

has adjacency list representation

1: 2, 3
2: 1, 4, 5, 6
3: 1, 4
4: 2, 3, 5
5: 2, 4, 6
6: 2, 5

In this assignment you will create a Graph ADT which represents an undirected simple graph as an array of neighbor-lists, as above. Each vertex will be identified by an integer from 1 to the number of vertices. Your program will use this Graph ADT to find shortest paths (i.e. paths with the fewest number of edges) between pairs of vertices.

The input to your program (as always from stdin) will come in two parts. The first part will begin with a line consisting a single integer n giving the number of vertices in the graph. The following lines will each represent an edge in the graph by a pair of distinct numbers in the range 1 to n, separated by a space. This first part of the input defines a graph, and will be terminated by a dummy line containing "0 0". After these lines are read your program will print out the adjacency list representation of the graph. For instance, the input lines

6
4 2
1 3
5 4
2 5
6 2
5 6
3 4
1 2
0 0

will define the graph pictured above, and will result in its adjacency list representation to be printed out.

The second part of the input will consist of a number of lines, each consisting of a pair of integers in the range 1 to n, separated by a space. Each line specifies a pair of vertices in the graph; a starting point and a destination. For each such pair your program will do the following:

Perform a Breadth First Search (BFS) to assign each vertex in the graph a "parent" vertex. The BFS algorithm will be discussed in class and is described in general terms below. The pseudo code for BFS can be found on p. 470 of the text.

Use these "parent" vertices to print out a shortest path from the starting point to the destination, along with its length.

This second part of the input will also be terminated by the dummy line "0 0". Continuing the previous example, the input lines

1 5
3 6
2 3
4 4
0 0

will result in something like the following being printed.

A shortest path from 1 to 5 of length 2 is: 1 -> 2 -> 5
A shortest path from 3 to 6 of length 3 is: 3 -> 1 -> 2 -> 6
A shortest path from 2 to 3 of length 2 is: 2 -> 1 -> 3
A shortest path from 4 to 4 of length 0 is: 4

You may assume that the graph is connected so that some path will always exist between any two vertices. Note however that there may be more than one shortest path. The particular path discovered by BFS depends on the order in which it steps through the vertices in your adjacency lists. This order is not specified in the pseudocode for BFS. Thus your output may differ from the above on the very same input, but see the note on extra credit below.

Your program’s operation can be broken down into two basic steps, corresponding to the two groups of input data.

Read and store the graph and print out its adjacency list representation.
Enter a loop which processes the second part of the input. Each iteration of the loop should read in one pair of vertices (starting point, destination), run BFS on one of the vertices given, then find and print the resulting shortest path from starting point to destination, together with the length of the path.

What is Breadth First Search? Given a graph G and a distinguished vertex s, called the source vertex, BFS systematically explores the edges of G to discover every vertex that is reachable from s. It computes the distance from s to all such reachable vertices. It also produces a "breadth-first tree" with root s that contains all reachable vertices. For any vertex v reachable from s, the unique path in the breadth-first tree from s to v corresponds to a shortest path in G from s to v. Breadth First Search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier; i.e. the algorithm discovers all vertices at distance k from s before discovering any vertices at distance k+1.

To keep track of its progress and to construct the breadth-first tree, BFS requires that each vertex v in G possess the following attributes: a color which may be white, grey, or black; a distance d[v] which is the distance from v to the source s; and a parent (or predecessor) p[v] which points to the parent of v in the breadth-first tree. At any point in the algorithm's execution, the white vertices are as yet undiscovered, black vertices are discovered, and the grey vertices form the frontier between discovered and undiscovered vertices. BFS uses a first-in first-out queue to manage the set of grey vertices.

Without going any further into the details of BFS, we can see a need for the following modules in your program design. Some of these are required in your project, while others are optional, and are so noted.

A Vertex ADT with the fields mentioned above. (Optional but highly recommended.)
A FIFO Queue ADT used by BFS as mentioned above. (Optional since you can use a list for this.)
A List ADT to manage the adjacency lists. (Required.)
A Graph ADT that uses all the other ADTs. (Required.)
A main program that reads the input , prints the output and uses the Graph module. (Required. )

Your Graph module is required to export a GraphHndl type and the following operations:

GraphHndl NewGraph(int n);
void FreeGraph(GraphHndl * pGraph);
void AddEdge(GraphHndl G, VertexHndl u, VertexHndl v);
VertexHndl Parent(GraphHndl G, VertexHndl u);
void BreadthFirstSearch(GraphHndl G, VertexHndl s);
void PrintGraph(GraphHndl G);

The above prototypes assume that you are implementing the Vertex ADT. If you choose not to do this, you may alter the prototypes to suit your particular situation. Bear in mind however that you must adhere to the principle of modularity. Never let one module "look inside the black box" of another module. NewGraph creates a Graph object with n vertices and no edges, and of course FreeGraph de-allocates all memory associated with a Graph object. AddEdge adds vertex v to the adjacency list of u, and u to the adjacency list of v. Parent returns a pointer to its parent vertex in the breadth-first tree. Note that this pointer is only set after BFS has been run on the graph. BreadthFirstSearch implements the BFS algorithm on p. 470 of the text, and PrintGraph prints out the adjacency list representation of G, as in the previous examples.

You may of course implement additional Graph operations such as the following:

Boolean IsNull(GraphHndl G);
void MakeNull(GraphHndl G);
void GraphCopy(GraphHndl G, GraphHndl H);

IsNull returns true if its argument is a null graph, i.e. if G has no edges. MakeNull deletes all edges from G. GraphCopy is the assignment operator for this ADT.

As usual you should submit a driver for each of your ADT modules, as well as the .c and .h files. Extra credit of 10 points will be awarded for implementing the following feature, provided the project is submitted on time, and is claimed in the README file.

For each start-destination pair, print out not only a shortest path together with its length, but the total number of shortest paths from starting point to destination. Believe it or not, this can be done by modifying your matrix multiplication function from the previous project. Those interested should see me for details.