aima.core.util

Class DisjointSets<E>

java.lang.Object

aima.core.util.DisjointSets<E>

Type Parameters:

E - the type of elements to be contained by the disjoint sets.

public class DisjointSets<E>
extends java.lang.Object

A basic implementation of a disjoint-set data structure for maintaining a collection of disjoint dynamic sets. This is based on the algorithm description in Chapter 21 of 'Introduction to Algorithm 2nd Edition' (by Cormen, Leriserson, Rivest, and Stein) for Disjoint-sets taking into account some of the heuristic ideas described. However, this implementation relies on the constant time performance of the HashMap's get and put operations, and HashSet's add, remove, contains and size operations as an alternative implementation approach. This provides a cleaner separation between the elements and the implementation (i.e. the idea of a representative for a particular disjoint set is not used) and an easier to use API (i.e. direct access to the disjoint set that an element belongs to and no need to understand how the internals work with respect to a representative) but will not perform as fast (proper analysis required but likely O(m + n lg n) as detailed in Theorem 21.1 on page 504 of 'Introduction to Algorithm 2nd Edition'). Note: the internal implementation of this class can likely be improved to use all the techniques outlined in section 21.3 in order to get optimal performance.

Author:

Ciaran O'Reilly

Constructor Summary

Constructors

Constructor and Description
DisjointSets() Default Constructor.
DisjointSets(java.util.Collection<E> initialElements) Constructor.
DisjointSets(E... elements) Constructor.

Method Summary

Modifier and Type	Method and Description
void	clear() Remove all the disjoint sets.
java.util.Set<E>	find(E element) Find the disjoint set that an element belongs to.
java.util.Set<java.util.Set<E>>	getDisjointSets()
java.util.Map<E,java.util.Set<E>>	getElementToDisjointSet()
void	makeSet(E element) Create a disjoint set for the element passed in.
int	numberDisjointSets()
void	union(E element1, E element2) Union two disjoint sets together if the arguments currently belong to two different sets.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjointSets

public DisjointSets()

Default Constructor.

DisjointSets

public DisjointSets(java.util.Collection<E> initialElements)

Constructor.

Parameters:

initialElements - a collection of elements, each of which will be assigned to their own disjoint set via makeSet().

DisjointSets

public DisjointSets(E... elements)

Constructor.

Parameters:

initialElements - a collection of elements, each of which will be assigned to their own disjoint set via makeSet().

Method Detail

makeSet

public void makeSet(E element)

Create a disjoint set for the element passed in. This method should be called for all elements before any of the other API methods are called (i.e. construct a disjoint set for each element first and then union them together as appropriate).

Parameters:

element - the element for which a new disjoint set should be constructed.

union

public void union(E element1,
                  E element2)

Union two disjoint sets together if the arguments currently belong to two different sets.

Parameters:

element1 -

element2 -

Throws:

java.lang.IllegalArgumentException - if element1 or element 2 is not already associated with a disjoint set (i.e. makeSet() was not called for the argument beforehand).

find

public java.util.Set<E> find(E element)

Find the disjoint set that an element belongs to.

Parameters:

element - the element whose disjoint set is being sought.

Returns:

the disjoint set for the element or null if makeSet(element) was not previously called.

getElementToDisjointSet

public java.util.Map<E,java.util.Set<E>> getElementToDisjointSet()

Returns:

a map for each element and the corresponding disjoint set that it belongs to.

getDisjointSets

public java.util.Set<java.util.Set<E>> getDisjointSets()

Returns:

the set of disjoint sets being maintained.

numberDisjointSets

public int numberDisjointSets()

Returns:

the number of disjoint sets.

clear

public void clear()

Remove all the disjoint sets.