Class WeightedQuickUnionRangeDBIDs
- java.lang.Object
-
- elki.utilities.datastructures.unionfind.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 forDBIDRange
only, with optimizations.To instantiate, use
UnionFindUtil.make(elki.database.ids.StaticDBIDs)
. This version is optimized forDBIDRange
s.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
-
-
Constructor Summary
Constructors Constructor Description WeightedQuickUnionRangeDBIDs(DBIDRange ids)
Constructor (package private, useUnionFindUtil.make(elki.database.ids.StaticDBIDs)
).
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
find(DBIDRef element)
Find the component ID of an element.DBIDs
getRoots()
Collect all component root elements.boolean
isConnected(DBIDRef first, DBIDRef second)
Test if two components are connected.int
union(DBIDRef first, DBIDRef second)
Join the components of elements p and q.
-
-
-
Field Detail
-
ids
private DBIDRange ids
Object ID range.
-
parent
private int[] parent
Parent element
-
weight
private int[] weight
Weight, for optimization.
-
-
Constructor Detail
-
WeightedQuickUnionRangeDBIDs
WeightedQuickUnionRangeDBIDs(DBIDRange ids)
Constructor (package private, useUnionFindUtil.make(elki.database.ids.StaticDBIDs)
).- Parameters:
ids
- Range to use
-
-
Method Detail
-
find
public int find(DBIDRef element)
Description copied from interface:UnionFind
Find the component ID of an element.
-
union
public int union(DBIDRef first, DBIDRef second)
Description copied from interface:UnionFind
Join the components of elements p and q.
-
isConnected
public boolean isConnected(DBIDRef first, DBIDRef second)
Description copied from interface:UnionFind
Test if two components are connected.- Specified by:
isConnected
in interfaceUnionFind
- Parameters:
first
- First elementsecond
- Second element- Returns:
true
if they are in the same component.
-
-