graph
Class MyKruskal

java.lang.Object
  graph.MyKruskal

All Implemented Interfaces:

MinSpanForest

public class MyKruskal
extends Object
implements MinSpanForest

Field Summary

Fields inherited from interface support.graph.MinSpanForest

CLOUD, DISCOVERY_EDGE, DISTANCE, LOCATOR, MST_EDGE, MST_VERTEX, TRUE

Constructor Summary

MyKruskal()

Method Summary

void	cleanup(AdjacencyMatrixGraph g) This will clean up any decorations that were added to the graph as a result of running the genMinSpanForest(.)
void	genMinSpanForest(AdjacencyMatrixGraph g) This method implements Kruskal's algorithm and extends it slightly to account for disconnected graphs.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MyKruskal

public MyKruskal()

Method Detail

genMinSpanForest

public void genMinSpanForest(AdjacencyMatrixGraph g)

This method implements Kruskal's algorithm and extends it slightly to account for disconnected graphs. Kruskal's algorithm has three phases. In the first phase, we have to put each Vertex of the graph in its own 'cluster'. In Java, we represent a cluster by a NodeSequence. Thus, there will be n NodeSequences initially, where n is the number of vertices in the graph. In the second phase, we insert all the edges into a priority queue using the weight of each edge as its key. In terms of this algorithm, you may assume that the 'element' of the edge is an Integer storing the weight. Thus, to get the weight of an edge, all I would have to do is: int weight = ((Integer)theEdge.element()).intValue(); Now, we have a choice of priority queues that we could use. However, in order to get the best running times, the most efficient one to use is HeapPriorityQueue. In the third stage, we keep obtaining the edge with minimum weight. If the connecting Vertex's of the edge belong to different clouds, we merge the clouds. In order to get this method to run in the correct running time, each Vertex has to know which cloud it is in. Again, we can use the decorable pattern to accomplish this. Specifically, you can use the predefined CLOUD object as your decoration key. *This is important!* You will *not* be returning a tree. This is partly because there may be multiple MST's (hence a Minimum Spanning Forest (MSF)). Instead, you will mark (by decorations) all the edges that belong in an MST. You *must* use the MST_EDGE decoration (which is predefined for you) to decorate edges in order for the visualizer to correctly recognize an Edge as belonging to an MST.

Specified by:

genMinSpanForest in interface MinSpanForest

Parameters:

g - The graph to perform the algorithm on.

See Also:

NodeSequence, HeapPriorityQueue, CS16Vertex, This algorithm must run in O((n + m) log n) time. Where n is the number of vertices, and m is the number of edges.

cleanup

public void cleanup(AdjacencyMatrixGraph g)

This will clean up any decorations that were added to the graph as a result of running the genMinSpanForest(.) algorithm. Specifically, this means removing all CLOUD decorations from Vertex's and all MST_EDGE decorations from all Edges. This must run in O(n + m) time. Where n is the number of vertices and m is the number of edges.

Specified by:

cleanup in interface MinSpanForest

Parameters:

g - The graph to cleanup.