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

Class WeightedQuickUnionRangeDBIDs

java.lang.Object

de.lmu.ifi.dbs.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 for DBIDRange only, with optimizations.

To instantiate, use UnionFindUtil.make(de.lmu.ifi.dbs.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 Summary

Fields

Modifier and Type	Field and Description
private DBIDRange	ids Object ID range.
private int[]	parent Parent element
private int[]	weight Weight, for optimization.

Constructor Summary

Constructors

Constructor and Description
WeightedQuickUnionRangeDBIDs(DBIDRange ids) Constructor (package private, use UnionFindUtil.make(de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs)).

Method Summary

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

Methods inherited from class java.lang.Object

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

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, use UnionFindUtil.make(de.lmu.ifi.dbs.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.

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