net.automatalib.commons.util

Class UnionFind

java.lang.Object

net.automatalib.commons.util.UnionFind

All Implemented Interfaces:

IntDisjointSets

public final class UnionFind
extends Object
implements IntDisjointSets

The well-known disjoint-set forest data structure for dealing with partitions on a fixed-range integer domain.

Author:

fhowar, Malte Isberner

Constructor Summary

Constructors

Constructor and Description
UnionFind(int n) Initializes the disjoint-set data structure.

Method Summary

Modifier and Type	Method and Description
int	find(int x) Finds the set of a given element, and compresses the path to the root node.
int	link(int x, int y) Unites two given sets.
int	size() Returns the size of the universe.

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.automatalib.commons.util.IntDisjointSets

equivalent, union

Constructor Detail

UnionFind

public UnionFind(int n)

Initializes the disjoint-set data structure.

Parameters:

n - the overall size of the domain

Method Detail

size

public int size()

Description copied from interface: IntDisjointSets

Returns the size of the universe. The elements of the universe are the integers between 0 (inclusive) and size() (exclusive).

Specified by:

size in interface IntDisjointSets

Returns:

the size of the universe

find

public int find(int x)

Finds the set of a given element, and compresses the path to the root node.

Specified by:

find in interface IntDisjointSets

Parameters:

x - the element

Returns:

the identifier of the set which contains the given element

link

public int link(int x,
                int y)

Unites two given sets. Note that the behavior of this method is not specified if the given parameters are normal elements and no set identifiers.

Specified by:

link in interface IntDisjointSets

Parameters:

x - the first set

y - the second set

Returns:

the identifier of the resulting set (either x or y)