Package net.automatalib.common.util
Class UnionFindRemSP
- java.lang.Object
-
- net.automatalib.common.util.UnionFindRemSP
-
- All Implemented Interfaces:
IntDisjointSets
public class UnionFindRemSP extends Object implements IntDisjointSets
Implementation of a disjoint set (union-find) data structure for integers, based on Rem's algorithm, as described in the paper Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure (M. Patwary, J. Blair, F. Manne; Proc. SEA 2010).
-
-
Constructor Summary
Constructors Constructor Description UnionFindRemSP(int n)
Initializes the disjoint-set data structure.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
equivalent(int x, int y)
Checks if two elements are in the same set.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.boolean
union(int x, int y)
Unites the sets containing the two given elements.
-
-
-
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 between0
(inclusive) andsize()
(exclusive).- Specified by:
size
in interfaceIntDisjointSets
- Returns:
- the size of the universe
-
equivalent
public boolean equivalent(int x, int y)
Description copied from interface:IntDisjointSets
Checks if two elements are in the same set.- Specified by:
equivalent
in interfaceIntDisjointSets
- Parameters:
x
- the first elementy
- the second element- Returns:
true
ifx
andy
are in the same set,false
otherwise
-
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 interfaceIntDisjointSets
- Parameters:
x
- the element- Returns:
- the identifier of the set which contains the given element
-
union
public boolean union(int x, int y)
Unites the sets containing the two given elements.- Specified by:
union
in interfaceIntDisjointSets
- Parameters:
x
- the first elementy
- the second element- Returns:
true
if two disjoint sets have been united as a result,false
otherwise
-
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 interfaceIntDisjointSets
- Parameters:
x
- the first sety
- the second set- Returns:
- the identifier of the resulting set (either
x
ory
)
-
-