JGraphUnionFind (JGraph v5.13.0.0 API Specification)

Class JGraphUnionFind

public class JGraphUnionFind extends Object

Implements a union find structure that uses union by rank and path compression. The union by rank guarantees worst case find time of O(log N), while Tarjan shows that in combination with path compression (halving) the average time for an arbitrary sequence of m >= n operations is O(m*alpha(m,n)), where alpha is the inverse of the Ackermann function, defined as follows: alpha(m,n) = min{i >= 1 | A(i, floor(m/n)) > log n} for m >= n >= 1 Which yields almost constant time for each individual operation.

Nested Class Summary
class	JGraphUnionFind.Node A class that defines the identity of a set.

Nested Class Summary

class

JGraphUnionFind.Node

A class that defines the identity of a set.

Field Summary
protected Map	nodes Maps from elements to nodes

Field Summary

protected Map

nodes

Maps from elements to nodes

Constructor Summary
	JGraphUnionFind(Object[] elements) Constructs a union find structure and initializes it with the specified elements.

Constructor Summary

JGraphUnionFind(Object[] elements)

Constructs a union find structure and initializes it with the specified elements.

Method Summary
boolean	differ(Object a, Object b) Returns true if element a and element b are not in the same set.
JGraphUnionFind.Node	find(JGraphUnionFind.Node node) Returns the set that contains `node`.
JGraphUnionFind.Node	getNode(Object element) Returns the node that represents element.
void	union(JGraphUnionFind.Node a, JGraphUnionFind.Node b) Unifies the sets `a` and `b` in constant time using a union by rank on the tree size.

Method Summary

boolean

differ(Object a, Object b)

Returns true if element a and element b are not in the same set.

JGraphUnionFind.Node

find(JGraphUnionFind.Node node)

Returns the set that contains node.

JGraphUnionFind.Node

getNode(Object element)

Returns the node that represents element.

void

union(JGraphUnionFind.Node a, JGraphUnionFind.Node b)