Package com.google.javascript.jscomp.graph

Interface UnionFind<E>

Type Parameters:
E - element type
All Known Implementing Classes:
StandardUnionFind
public interface UnionFind<E>
Union-Find is a classical algorithm used to find connected components in graph theory.

Each equivalence class has a representative element that is chosen arbitrarily and is used to determine if two elements are members of the same class.

See algorithmist for more detail.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(E e)
    Adds the given element to a new set if it is not already in a set.
    Collection<Set<E>>
    allEquivalenceClasses()
    Returns an immutable collection containing all equivalence classes.
    boolean
    areEquivalent(E a, E b)
    Returns true if a and b belong to the same equivalence class.
    Set<E>
    elements()
    Returns an unmodifiable set of all elements added to the UnionFind.
    E
    find(E e)
    Returns the representative of the equivalence class of e.
    Set<E>
    findAll(E value)
    Returns the elements in the same equivalence class as value.
    E
    union(E a, E b)
    Unions the equivalence classes of a and b and returns the representative of the resulting equivalence class.

  • Method Details

    • add

      void add(E e)
      Adds the given element to a new set if it is not already in a set.
      Throws:
      UnsupportedOperationException - if the add operation is not supported by this union-find.

    • union

      E union(E a, E b)
      Unions the equivalence classes of a and b and returns the representative of the resulting equivalence class. The elements will be added if they are not already present.
      Throws:
      UnsupportedOperationException - if the add operation is not supported by this union-find.

    • find

      E find(E e)
      Returns the representative of the equivalence class of e.

    • areEquivalent

      boolean areEquivalent(E a, E b)
      Returns true if a and b belong to the same equivalence class.
      Throws:
      IllegalArgumentException - if any argument is not an element of this structure.

    • elements

      Set<E> elements()
      Returns an unmodifiable set of all elements added to the UnionFind.

    • allEquivalenceClasses

      Collection<Set<E>> allEquivalenceClasses()
      Returns an immutable collection containing all equivalence classes. The returned collection represents a snapshot of the current state and will not reflect changes made to the data structure.

    • findAll

      Set<E> findAll(E value)
      Returns the elements in the same equivalence class as value.
      Returns:
      an unmodifiable view. As equivalence classes are merged, this set will reflect those changes.
      Throws:
      IllegalArgumentException - if a requested element does not belong to the structure.