Class WeightedQuickUnionStaticDBIDs

  • All Implemented Interfaces:
    UnionFind

    @Reference(authors="R. Sedgewick",
               title="Algorithms in C, Parts 1-4",
               booktitle="",
               bibkey="DBLP:books/daglib/0004943")
    public class WeightedQuickUnionStaticDBIDs
    extends java.lang.Object
    implements UnionFind
    Union-find algorithm for StaticDBIDs, with optimizations.

    To instantiate, use UnionFindUtil.make(elki.database.ids.StaticDBIDs), which will automatically choose the best implementation available.

    This is the weighted quick union approach, weighted by count and using path-halving for optimization.

    This version needs more memory than WeightedQuickUnionRangeDBIDs but can work with any unmodifiable DBID set (although ArrayDBIDs are recommended).

    Reference:

    R. Sedgewick
    1.3 Union-Find Algorithms
    Algorithms in C, Parts 1-4

    Since:
    0.7.0
    Author:
    Evgeniy Faerman, Erich Schubert
    • Field Detail

      • parent

        private int[] parent
        Parent element
      • weight

        private int[] weight
        Weight, for optimization.
    • Method Detail

      • find

        public int find​(DBIDRef element)
        Description copied from interface: UnionFind
        Find the component ID of an element.
        Specified by:
        find in interface UnionFind
        Parameters:
        element - Element
        Returns:
        Component id
      • union

        public int union​(DBIDRef first,
                         DBIDRef second)
        Description copied from interface: UnionFind
        Join the components of elements p and q.
        Specified by:
        union in interface UnionFind
        Parameters:
        first - First element
        second - Second element
        Returns:
        Component id.
      • isConnected

        public boolean isConnected​(DBIDRef first,
                                   DBIDRef second)
        Description copied from interface: UnionFind
        Test if two components are connected.
        Specified by:
        isConnected in interface UnionFind
        Parameters:
        first - First element
        second - Second element
        Returns:
        true if they are in the same component.
      • getRoots

        public DBIDs getRoots()
        Description copied from interface: UnionFind
        Collect all component root elements.
        Specified by:
        getRoots in interface UnionFind
        Returns:
        Root elements