de.lmu.ifi.dbs.elki.utilities.datastructures.unionfind

Class WeightedQuickUnionInteger

java.lang.Object

de.lmu.ifi.dbs.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 and Description
private static int	INITIAL_SIZE Initial size.
private int[]	parent Parent element
private int	used Number of used indexes.
private int[]	weight Weight, for optimization.

Constructor Summary

Constructors

Constructor and Description
WeightedQuickUnionInteger() Constructor.

Method Summary

Modifier and Type	Method and 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

Constructor Detail

WeightedQuickUnionInteger

public WeightedQuickUnionInteger()

Constructor.

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 element

second - Second element

Returns:

Component id.

isConnected

public boolean isConnected(int first,
                           int second)

Test if two components are connected.

Parameters:

first - First element

second - 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.