com.codemelon.graph.algorithm.spanningtree

Class Kruskal<E extends SpanningTreeEdgeData,V extends UndirectedKruskalVertex<E>>

java.lang.Object

com.codemelon.graph.algorithm.spanningtree.Kruskal<E,V>

public class Kruskal<E extends SpanningTreeEdgeData,V extends UndirectedKruskalVertex<E>>
extends java.lang.Object

Implementation of Kruskal's algorithm for growing a minimum spanning tree. Follows CLRS, pp. 631ff. This implementation allows clients to retrieve a minimum spanning tree in either of 2 ways:

1. Mark all edges belonging to the minimum spanning tree black and all other edges white, or
2. Produce a new graph which is a minimum spanning tree for the input graph.

Constructor Summary

Constructors

Constructor and Description
Kruskal(UndirectedWeightedEdgeGraph<E,V> graph, VertexFactory<V> vertexFactory) Create a new object for generating a minimum spanning tree using Kruskal's algorithm.

Method Summary

Methods

Modifier and Type	Method and Description
UndirectedWeightedEdgeGraph<E,V>	generateTree() Creates and returns a minimum spanning tree.
java.util.Map<V,V>	getVertexMap() Returns a map showing which vertex in the spanning tree corresponds to a given vertex in the original graph.
void	markEdges() Set edges in minimum spanning tree to BLACK, all other edges are set to WHITE

Methods inherited from class java.lang.Object

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

Constructor Detail

Kruskal

public Kruskal(UndirectedWeightedEdgeGraph<E,V> graph,
       VertexFactory<V> vertexFactory)

Create a new object for generating a minimum spanning tree using Kruskal's algorithm. If a separate spanning tree will not be needed (i.e., the relevant edges only need to be marked in the original graph), null may be passed as vertex factory. If null is passed, a NullPointerException will result if generateTree() is called.

Parameters:

graph - graph for which a minimum spanning tree is to be determined

vertexFactory - factory method for creating new vertices for the spanning tree graph that can be generated by calling generateTree()

Method Detail

markEdges

public void markEdges()

Set edges in minimum spanning tree to BLACK, all other edges are set to WHITE

generateTree

public UndirectedWeightedEdgeGraph<E,V> generateTree()

Creates and returns a minimum spanning tree. Running this method does not modify the original graph. Corresponding vertices can be determined by running getVertexMap(). The 2 graphs will have the same weight epsilon for determining the accuracy used for weight equality, and the weights of edges between corresponding vertices will be the same. With the exception of edge weights and weight epsilon, however, all vertex and edge data in the spanning tree will be set to the default value, regardless of the corresponding value in the original graph.

Returns:

a spanning tree of the original graph.

getVertexMap

public java.util.Map<V,V> getVertexMap()

Returns a map showing which vertex in the spanning tree corresponds to a given vertex in the original graph. Edges between corresponding vertices in the 2 graphs will have the same weight. The keys of this map are the vertices in the original graph, and the values are vertices in the spanning tree generated when generateTree() is called.

Returns:

map from vertices in the original graph to vertices in the spanning tree

Throws:

java.lang.IllegalStateException - if this method is called before generateTree(). In this case, the map has not been created yet.