Class WeightedQuickUnionInteger
- java.lang.Object
-
- elki.utilities.datastructures.unionfind.WeightedQuickUnionInteger
-
@Reference(authors="R. Sedgewick", title="Algorithms in C, Parts 1-4", booktitle="", bibkey="DBLP:books/daglib/0004943") public class WeightedQuickUnionInteger extends java.lang.Object
Union-find algorithm for primitive integers, with optimizations.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.1
- Author:
- Erich Schubert
-
-
Field Summary
Fields Modifier and Type Field Description private static int
INITIAL_SIZE
Initial size.private int[]
parent
Parent elementprivate int
used
Number of used indexes.private int[]
weight
Weight, for optimization.
-
Constructor Summary
Constructors Constructor Description WeightedQuickUnionInteger()
Constructor.WeightedQuickUnionInteger(int size)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
find(int cur)
Find the parent of an object.it.unimi.dsi.fastutil.ints.IntList
getRoots()
Collect all component root elements.boolean
isConnected(int first, int second)
Test if two components are connected.int
nextIndex(int weight)
Occupy the next unused index.int
size()
Number of allocated indexes.int
union(int first, int second)
Join the components of elements p and q.
-
-
-
Field Detail
-
used
private int used
Number of used indexes.
-
parent
private int[] parent
Parent element
-
weight
private int[] weight
Weight, for optimization.
-
INITIAL_SIZE
private static final int INITIAL_SIZE
Initial size.- See Also:
- Constant Field Values
-
-
Method Detail
-
nextIndex
public int nextIndex(int weight)
Occupy the next unused index.- Parameters:
weight
- Initial weight.- Returns:
- Next unused index.
-
find
public int find(int cur)
Find the parent of an object.- Parameters:
cur
- Current entry- Returns:
- Parent entry
-
union
public int union(int first, int second)
Join the components of elements p and q.- Parameters:
first
- First elementsecond
- Second element- Returns:
- Component id.
-
isConnected
public boolean isConnected(int first, int second)
Test if two components are connected.- Parameters:
first
- First elementsecond
- Second element- Returns:
true
if they are in the same component.
-
getRoots
public it.unimi.dsi.fastutil.ints.IntList getRoots()
Collect all component root elements.- Returns:
- Root elements
-
size
public int size()
Number of allocated indexes.- Returns:
- Index number.
-
-