Module net.automatalib.common.util
Package net.automatalib.common.util

Interface IntDisjointSets

  • All Known Implementing Classes:
    UnionFind, UnionFindRemSP
    public interface IntDisjointSets
    Interface for disjoint-set forest implementations that operate on a universe of contiguous integers.

    • Method Summary

      All Methods Instance Methods Abstract Methods Default Methods 
      Modifier and Type Method Description
      default boolean equivalent​(int x, int y)
      Checks if two elements are in the same set.
      int find​(int x)
      Determines the representative element of the set containing x.
      int link​(int rx, int ry)
      Links (unites) two sets, identified by their representatives.
      int size()
      Returns the size of the universe.
      default boolean union​(int x, int y)
      Unites the sets containing the respective elements.

    • Method Detail

      • size

        int size()
        Returns the size of the universe. The elements of the universe are the integers between 0 (inclusive) and size() (exclusive).
        Returns:
        the size of the universe

      • equivalent

        default boolean equivalent​(int x,
                           int y)
        Checks if two elements are in the same set.
        Parameters:
        x - the first element
        y - the second element
        Returns:
        true if x and y are in the same set, false otherwise

      • find

        int find​(int x)
        Determines the representative element of the set containing x.
        Parameters:
        x - the element to find
        Returns:
        the representative element of the set containing x.

      • union

        default boolean union​(int x,
                      int y)
        Unites the sets containing the respective elements. If two disjoint sets were united, the return value is true. Otherwise, if x and y were already in the same set, false is returned.

        Attention: this method returns true if and only if equivalent(x, y) would have returned false.

        Parameters:
        x - the first element
        y - the second element
        Returns:
        true if two disjoint sets have been united as a result, false otherwise

      • link

        int link​(int rx,
         int ry)
        Links (unites) two sets, identified by their representatives.
        Parameters:
        rx - the representative of the first set
        ry - the representative of the second set
        Returns:
        the representative of the resulting set (typically either rx or ry).