Class WeightedQuickUnionStaticDBIDs
- java.lang.Object
-
- elki.utilities.datastructures.unionfind.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 forStaticDBIDs
, 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 (althoughArrayDBIDs
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 Summary
Fields Modifier and Type Field Description private ArrayDBIDs
ids
Object ID range.private WritableIntegerDataStore
index
Index, to map DBID to offset.private int[]
parent
Parent elementprivate int[]
weight
Weight, for optimization.
-
Constructor Summary
Constructors Constructor Description WeightedQuickUnionStaticDBIDs(StaticDBIDs 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 ArrayDBIDs ids
Object ID range.
-
index
private WritableIntegerDataStore index
Index, to map DBID to offset.
-
parent
private int[] parent
Parent element
-
weight
private int[] weight
Weight, for optimization.
-
-
Constructor Detail
-
WeightedQuickUnionStaticDBIDs
WeightedQuickUnionStaticDBIDs(StaticDBIDs 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.
-
-