CSCI 220: Project 4

NOTICE: Since we will have only 4 projects instead of the five originally stated in the syllabus, I will give you the choice of having each project count for 12.5 percent of your grade, or of having projects 1-3 count for 10 percent and this project count for 20 percent. I will count all projects equally unless you tell me otherwise.

Part I: Implementing a graph data structure

G=(V,E) is the graph

• Degree(G,v) returns an integer which is the degree of vertex v in graph G. If v is not a valid vertex for the graph you have the choice of crashing the code or returning -1. Document the choice.

• Edge(G,v,u) returns true if the graph contains an edge between vertex v and vertex u. If the vertices are not valid for the graph, can either return false or crash the code.

• Neighbors(G,v) returns a list of the neighbors of vertex v. You can write neighbors to take the list into which the neighbors are stored as an argument if you wish. If v is not a valid vertex in G, either return an empty list or crash the code.

• SubGraph(G, subV) takes a graph and a list of vertices in the graph and returns the subgraph induced by the list of vertices. You can make the subgraph an argument passed if you wish.

• WriteGraph(G) writes out a graph. The graph should be output in DIMACS format. (See a description below.)

• ReadGraph(G, filename) reads a graph in from the given filename. Assume the graph is in DIMACS format. (See a description below.)

DIMACS Graph Format

1. The file begins with 0 or more comment lines. Each comment line begins with the letter 'c'.

2. After any comment lines there will be a line with the number of vertices and edges in the graph. These lines are always of the format
   p edge #vertices #edges
   (This is to distinguish between other types of graphs used at DIMACS.)

3. Following the line detailing the size of the graph there will be lines indicating edges in the graph. The lines are of the format
   e v u
   where e is the letter 'e' but v and u are integers representing the edge.

Here is an example graph in DIMACS format.

Part II: Breadth First Search

Write a program that reads in a graph and then constructs a Breadth First forest by repeatedly calling BFS (as we discussed in class). Output each of the trees level by level. For example:

source:  5
level 1: 2 4 8
level 2: 1 7 3
level 3: 6

The graph yielding the above tree is:

p edge 8 12
e 1 2
e 1 4
e 1 6
e 1 7
e 2 4
e 2 5
e 2 7
e 3 7
e 3 4
e 3 8
e 4 5
e 5 8

One way to store the resulting tree is to create a directed subgraph. This is a slight modification to your undirected graph data structure; if you use an adjacency list, only store out-edges in an adjacency list; if you use an adjacency matrix, only make M[v,u] = 1 instead of both M[v,u] and M[u,v].

Part III: Minimum Spanning Tree

You will need to modify your graph data structure to handle weighted graphs. The graph format is exactly the same except a third integer is added on each edge description line indicating the weight (cost) of the edge.

Write a program that reads in a weighted graph and outputs the minimum spanning tree of the graph.

IV: What to hand in

1. Commented code detailing the data structures and algorithms.
2. The main programs you used to test the data structures.
3. Sample runs of the programs for parts II and III.

V: Test Data

Update: The directory /usr/local/www/data/csci220 contains 8 files of interest to you:

• bfsgraph1.dat and bfsgraph2.dat are the test files for the BFS algorithm.

• bfsgraph1.out and bfsgraph2.out are my output on these graphs (you don't need to output the entire graph again, that's the remainder of my debugging scaffolding).

• mstgraph1.dat and mstgraph2.dat are the test files for the MST algorithm.

• mstgraph1.out and mstgraph2.out are my output on these graphs (you don't need to output the entire original graph again, that's the remainder of my debugging scaffolding).