Class 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.
    • Constructor Summary

      Constructors 
      Constructor 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

      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.
      • 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()