Class UnionFind<V>
- java.lang.Object
-
- org.eclipse.viatra.query.runtime.matchers.algorithms.UnionFind<V>
-
- Type Parameters:
V- the type parameter of the element's stored in the union-find data structure
public class UnionFind<V> extends java.lang.ObjectUnion-find data structure implementation. Note that the implementation relies on the correct implementation of the equals method of the type parameter's class.
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description voiddeleteSet(V root)Delete the set whose root is the given node.Vfind(V node)Find method with path compression.java.util.Set<V>getPartition(V element)Returns the partition in which the given element can be found, or null otherwise.java.util.Set<V>getPartitionHeads()java.util.Collection<java.util.Set<V>>getPartitions()Returns all partitions.booleanisSameUnion(java.util.Set<V> elements)Returns if all given elements are in the same partition.VmakeSet(java.util.Collection<V> nodes)Creates a new union set from a collection of elements.VmakeSet(V node)This method creates a single set containing the given node.Vunion(V x, V y)Union by rank implementation of the two sets which contain x and y; x and/or y can be a single element from the universe.voidunite(java.util.Set<V> elements)Places the given elements in to the same partition.
-
-
-
Constructor Detail
-
UnionFind
public UnionFind()
Instantiate a new union-find data structure.
-
UnionFind
public UnionFind(java.lang.Iterable<V> elements)
Instantiate a new union-find data structure with the given elements as separate sets.
-
-
Method Detail
-
makeSet
public V makeSet(java.util.Collection<V> nodes)
Creates a new union set from a collection of elements.- Parameters:
nodes- the collection of elements- Returns:
- the root element
-
makeSet
public V makeSet(V node)
This method creates a single set containing the given node.- Parameters:
node- the root node of the set- Returns:
- the root element
-
find
public V find(V node)
Find method with path compression.- Parameters:
node- the node to find- Returns:
- the root node of the set in which the given node can be found
-
union
public V union(V x, V y)
Union by rank implementation of the two sets which contain x and y; x and/or y can be a single element from the universe.- Parameters:
x- set or single element of the universey- set or single element of the universe- Returns:
- the new root of the two sets
-
unite
public void unite(java.util.Set<V> elements)
Places the given elements in to the same partition.
-
deleteSet
public void deleteSet(V root)
Delete the set whose root is the given node.- Parameters:
root- the root node
-
isSameUnion
public boolean isSameUnion(java.util.Set<V> elements)
Returns if all given elements are in the same partition.
-
getPartition
public java.util.Set<V> getPartition(V element)
Returns the partition in which the given element can be found, or null otherwise.
-
getPartitions
public java.util.Collection<java.util.Set<V>> getPartitions()
Returns all partitions.
-
getPartitionHeads
public java.util.Set<V> getPartitionHeads()
-
-