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.Object
Union-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 void
deleteSet(V root)
Delete the set whose root is the given node.V
find(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.boolean
isSameUnion(java.util.Set<V> elements)
Returns if all given elements are in the same partition.V
makeSet(java.util.Collection<V> nodes)
Creates a new union set from a collection of elements.V
makeSet(V node)
This method creates a single set containing the given node.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.void
unite(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()
-
-