Assignment #6

Due December 17.

The goal of this assignment is to implement Kruskal's and Prim's algorithms for computing the minimum spanning tree (T) of a graph G = (V,E). The description of the assignment in this file is complemented by a more detailed discussion of the two algorithms in a file called MST Discussion. It is necessary to study both files in order to understand the assignment

You will need to write two methods, Kruskal and Prim, together with their supporting data structures, and a main driver method.

(1) The main method (like the sorting assignment) should consist of a test section and a timing section.

The test section should do the following:

read the input for a graph G (format is described in MST Discussion);
build EdgeList, the edge list representation of G;
build ADJ, the adjacency list representation of G;
print out the edge list representation in a neat format;
print out the adjacency list representation in a neat format;
call Kruskal;
call Prim;
(note that in test mode Kruskal and Prim will print out the edges of T)
print the weight of T;
print whether the graph G is connected or not.

The timing section should do the following:

read a series of input files containing both dense and sparse graphs of a range of sizes (methods to generate dense and sparse graphs are provided in MakeGraph.java and MakeGraph2.java, which are in the examples directory) and for each input graph:
- build EdgeList and ADJ;
- call Kruskal;
- call Prim;
- for each algorithm, print out:
  - the name of the algorithm
  - the input size
  - whether sparse or dense
  - the elapsed time
  - the weight returned

(2) The function Kruskal should do the following:

take EdgeList, n, and m as input parameters;
perform Kruskal's algorithm to construct a minimum spanning tree, T, of G;
if in test mode, print out the edges in T, in the order they are added into T;
return the weight of T, and also indicate to the calling method whether the graph G is connected or not;

(3) The function Prim should do the following:

take ADJ, n, and m as input parameters;
perform Prim's algorithm to construct a minimum spanning tree, T, of G;
if in test mode, print out the edges in T, in the order they are added into T;
return the weight of T, and also indicate to the calling method whether the graph G is connected or not;

Note that the minimum spanning trees constructed by Kruskal's and Prim's algorithms could be different. However, the weight of the two MSTs must be the same.

The following will also be needed by your program.

An edge class, defined as follows:

    
public class Edge implements Comparable {

    public int weight;
    public int firstNode;
    public int secondNode;
  
    public Edge(int W) {
        weight = W;
        firstNode = 0;
        secondNode = 0;
    }
    
    public Edge(int W, int F, int S) {
        weight = W;
        firstNode = F;
        secondNode = S;
    }

    public Edge() {
        weight = 0;
        firstNode = 0;
        secondNode = 0;
    }

    public int compareTo(Object rhs) {
        Edge edge = (Edge)rhs;
        return this.weight - edge.weight;
    }
}

So it should be possible to compare two variables e1 and e2 of type Edge by the test: e1.compareTo(e2).

A queue structure is needed for each component item ADJ[i] in the adjacency list (see MST Discussion), and also for the tree T in both Kruskal's and Prim's algorithms. The main operations that will be needed are to put an Edge into this queue and to remove an Edge from it. Since the components of the queue would be Edges, and class Edge implements Comparable, any Queue class that can work with Comparables should be OK.
An edge list structure which is simply an array of Edges:
```
Edge[] EdgeList = new Edge[m];
```
where m is the number of edges in a graph.
An adjacency list representation, defined as follows:
```
Queue[] ADJ = new Queue[n+1];
```
ADJ is an array whose elements are of type Queue (queues of edges). Since the vertices (nodes) of a graph will need to be numbered 1,2, . . .,n, the ADJ array needs to be indexed from 1 to n. So its size must be n+1, where n is the number of vertices.
A queue containing the edges in a MST, which is needed by both Kruskal's and Prim's algorithms. Its definition would simply be:
```
Queue T;
```
A class UnionFindSet, described in MST Discussion, which is needed for Kruskal's algorithm.
A class BitSet, also described in MST Discussion, which is needed by Prim's algorithm.
In Kruskal's algorithm, a sorting method is needed to sort the array EdgeList according to Weight. You can modify the QuickSort from last assignment to do this. Since the elements in EdgeList are of type Edge, any QuickSort which sorts Comparables should work fine.
Note that the edges in the input graph are allowed to have the same weight. So the elements in an EdgeList may have the same key value. Weiss's code should handle this correctly.
A priority queue is needed to implement CrossEdges in Prim's algorithm. Use Weiss's binary heap:
```
BinaryHeap CrossEdges = new BinaryHeap();
```
Note, again, that the binary heap should handle duplicate key values.

Submission:

Each group should submit the following:

Hard copy of the source code.
Hard copy of testing for correctness (sparse and dense graphs, connected and disconnected graphs).
Hard copy of some timing runs.
An brief analysis of the order of growth of the two algorithms, and discussion of whether your timing runs confirm this analysis.
In addition, each group should email me a soft copy program.

Extra Credits

1) Find an improvement in one of the algorithms described, and show that your improvement actually yields better times for a class of input. 2) Implement Dijkstra's Shortest Path Algorithm and test with a range of input graphs.

Hints

First get your input routine working and make sure you can read graph data and print out the correct adjacency list and edge list representations of this data.
Then choose one of the algorithms to implement, gather the supporting data structures, and test for the input set in Fig. 1.
Etc. --one confirmable step at a time.

Updated November 26, 2007

Computer Science

at Simon's Rock College

Assignment #6