org.graphstream.algorithm.util

Class DisjointSets<E>

java.lang.Object

org.graphstream.algorithm.util.DisjointSets<E>

Type Parameters:

E - the type of the elements

public class DisjointSets<E>
extends Object

This data structure is used to maintain disjoint sets. It supports limited number of operations, but they are all executed in constant amortized time. The supported operations are:

• Adding a new set containing a single element
• Determining if two elements belong to the same set
• Union of the sets containing two elements

The space taken by this structure is O(n), where n is the number of elements.

Constructor Summary

Constructors

Constructor and Description
DisjointSets() Creates a new instance containing no sets and no elements
DisjointSets(int initialCapacity) Creates a new instance containing no sets and no elements.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(E e) Adds a new set containing only e to the structure.
void	clear() Reinitializes the structure.
boolean	contains(Object e) Checks if an element belongs to some of the disjoint sets.
boolean	inSameSet(Object e1, Object e2) Checks if two elements belong to the same set.
boolean	union(Object e1, Object e2) Union of the set containing e1 and the set containing e2.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjointSets

public DisjointSets()

Creates a new instance containing no sets and no elements

DisjointSets

public DisjointSets(int initialCapacity)

Creates a new instance containing no sets and no elements. If the total number of elements to add is known in advance, this constructor is more efficient than the default.

Parameters:

initialCapacity - Initial capacity (in number of elements) of the structure. The structure grows dynamically and new elements can be added even if this capacity is exceeded.

Method Detail

add

public boolean add(E e)

Adds a new set containing only e to the structure. If e already belongs to some of the disjoint sets, nothing happens.

Parameters:

e - The element to add as a singleton

Returns:

True if the new set is added and false if e already belongs to some set.

inSameSet

public boolean inSameSet(Object e1,
                Object e2)

Checks if two elements belong to the same set.

Parameters:

e1 - An element

e2 - An element

Returns:

True if and only if belong to the same set. Note that if e1 or e2 do not belong to any set, false is returned.

union

public boolean union(Object e1,
            Object e2)

Union of the set containing e1 and the set containing e2. After this operation inSameSet(e1, e2) will return true. If e1 or e2 do not belong to any set or if they already belong to the same set, nothing happens.

Parameters:

e1 - An element

e2 - An element

Returns:

true if and only if e1 and e2 belong to different sets at the beginning

contains

public boolean contains(Object e)

Checks if an element belongs to some of the disjoint sets.

Parameters:

e - An element

Returns:

True if e belongs to some set.

clear

public void clear()

Reinitializes the structure. After this operation the structure contains no sets.