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

Class WeightedQuickUnionStaticDBIDs

java.lang.Object

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

To instantiate, use UnionFindUtil.make(de.lmu.ifi.dbs.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 (although ArrayDBIDs 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 and Description
private ArrayDBIDs	ids Object ID range.
private WritableIntegerDataStore	index Index, to map DBID to offset.
private int[]	parent Parent element
private int[]	weight Weight, for optimization.

Constructor Summary

Constructors

Constructor and Description
WeightedQuickUnionStaticDBIDs(StaticDBIDs 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 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, 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