com.codemelon.graph.common

Class DisjointSet<T>

java.lang.Object

com.codemelon.graph.common.DisjointSet<T>

public class DisjointSet<T>
extends java.lang.Object

Implementation of disjoint set following CLRS, pp. 561ff. Disjoint sets are needed for Kruskal's minimum spanning tree algorithm.

Constructor Summary

Constructors

Constructor and Description
DisjointSet(java.util.Collection<T> items) This performs the make-set operation described in CLRS on all items in the collection

Method Summary

Methods

Modifier and Type	Method and Description
T	findSet(T item) Returns the canonical representative of the set to which the given item belongs
boolean	union(T x, T y) Perform a union on the sets to which x and y belong.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjointSet

public DisjointSet(java.util.Collection<T> items)

This performs the make-set operation described in CLRS on all items in the collection

Parameters:

items -

Method Detail

findSet

public T findSet(T item)

Returns the canonical representative of the set to which the given item belongs

Parameters:

item - item whose set is to be determined

Returns:

the canonical representative of the set to which the given item belongs

union

public boolean union(T x,
            T y)

Perform a union on the sets to which x and y belong. After this method is called, x and y will belong to the same disjoint set. CLRS, p. 562

Parameters:

x - member of a disjoint set (unknown whether or not the same set as y)

y - member of a disjoint set (unknown whether or not the same set as x)

Returns:

true iff the sets to which x and y belong were distinct prior to the call