Class WeightedQuickUnionRangeDBIDs

  • All Implemented Interfaces:
    UnionFind

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

    To instantiate, use UnionFindUtil.make(elki.database.ids.StaticDBIDs). This version is optimized for DBIDRanges.

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

    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

      • ids

        private DBIDRange ids
        Object ID range.
      • 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