CS 112 A1 - Fall 2004: Homework 5

Due Monday, November 29, 11:59 P.M.

Reading: Chapters 12, pages 569 - 596.

PROBLEM 1 (90 points):

Introduction

In this assignment you will implement a two graph classes and use them in two graph algorithms, a depth first search algorithm and a shortest path algorithm.

The Two Graph Classes

The two classes will differ in how they store the graph. The first will store a weighted graph as a weighted adjacency matrix. The second graph class will store the graph as an array of pointers of length n, where n is the number of vertices in the graph. The ith pointer points to a linked list of those vertices adjacent to vertex i, and the nodes in the list store the adjacent vertices as well as the weights of the corresponding edges.

The choice of methods for the graph classes is up to you. However you should have both private and public methods. To the extent you can, the private functions in each class should do the same tasks, only on different input formats. And to the extent you can the public functions should have the same definitions in the two cases, but use the private functions from their respective classes.

The Two Graph Algorithms

You need to write two functions in your program, one to carry out a depth first search and one to carry out a shortest path algorithm. You can include the calls to these two functions into one main.cpp program. This program should work with each of the two graph classes. You will only have to change the include statement in your program to include the particular graph class the program should use. So you will need to choose and design your class methods carefully so that they carry out the same operations, just using the different data structures. You can find algorithms for DFS or finding the shortest path in a graph in our textbook.

The graph algorithms should both be written once in your main program and not written twice in the in your two classes. These application functions should be called from main and should work (without changing them) for either the sequential or linked class. To do this they will have to access the (private) graph representations stored by the classes. And to do this they will need public class methods (auxiliary functions) which, for instance, takes a vertex as input and which outputs the next vertex adjacent to it that has not been visited. You may implement whatever auxiliary functions you like in your classes.

The output of the shortest path algorithm is only the LENGTH of the shortest path from vertex 1 to vertex n. It need not output the path itself.

The Input

Here is an input file containing a single graph. You should save it to your own directory. The format of the file is an integer n = no. of vertices in the first graph The a list of edges in the first graph with their weights (one per line).

A graph with n vertices will be a assumed to have vertices 1,2,3,4..., n. All weights are positive integers. You may assume that the graph has at most 40 nodes.

For example, a graph with three nodes and 2 edges, (1,3) of weight 11 and (2,3) of weight 33, might be given as

3 
1 3 11 
2 3 33

Your main.cpp program will need to first call a function which input the graph from the datafile and which then prints out the graph. It should this by either printing out the adjacency array or by printing out the list of linked lists which store the graph.

The Action and Output of the Algorithms

The depth first search algorithm will output a depth first traversal of the graph in the datafile. The traversal should begin at vertex 1.

The shortest path algorithm should find the length of the shortest path from vertex 1 to vertex n in the graph. (Vertex n is the highest numbered vertex.)

So you will need to run your program twice, once with the first graph class and once with the second graph class.

So a sample output might look like:

i. (The adjacency matrix of the graph here. )

ii. The Depth first search of the graph is: 1 5 3 6 7 2 4

iii. The shortest path from vertex 1 to vertex 7 has length 7.

You should input the data file using the UNIX command line and the redirection ("<") operator. When the program is tested it will be tested on other graphs, including unconnected graphs, graphs will only one node, and graphs with many cycles in them. SO make sure your program runs using the redirection operator.

What to Submit

Turn in files graph_mat.cpp and graph_mat.h and graph_link.cpp and graph_link.h with the 2 graph classes.

Turn in your program file main.cpp.

Turn in your output in two output files, out_mat with the adjacency matrix output, and out_link, with the linked graph output. These files should contain the representation of the graph after it is stored and the output of the two algorithms on the graph.

You should also submit a text file called hw5.txt which documents the uses and capabilities of your program and how a user would run it. Finally you should write, use and submit a make file for this program.