org.eclipse.viatra.query.runtime.matchers.algorithms

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

Direct Known Subclasses:

UnionFind

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.

Constructor Summary

Constructors

Constructor and Description
UnionFind() Instantiate a new union-find data structure.
UnionFind(java.lang.Iterable<V> elements) Instantiate a new union-find data structure with the given elements as separate sets.

Method Summary

Modifier and Type	Method and 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.

Methods inherited from class java.lang.Object

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

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 universe

y - 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()