Union-Find

`UnionFind(elements=None)`

Bases: object

Union-find disjoint sets datastructure.

Original repository: https://github.com/deehzee/unionfind/blob/master/unionfind.py

Union-find is a data structure that maintains disjoint set (called connected components or components in short) membership, and makes it easier to merge (union) two components, and to find if two elements are connected (i.e., belong to the same component).

This implements the "weighted-quick-union-with-path-compression" union-find algorithm. Only works if elements are immutable objects.

Worst case for union and find: (N + M log* N), with N elements and M unions. The function log* is the number of times needed to take log of a number until reaching 1. In practice, the amortized cost of each operation is nearly linear [1]_.

Terms

Component: Elements belonging to the same disjoint set

Connected: Two elements are connected if they belong to the same component.

Union: The operation where two components are merged into one.

Root: An internal representative of a disjoint set.

Find: The operation to find the root of a disjoint set.

Parameters:

Name	Type	Description	Default
`elements`	`None or container`	The initial list of elements.	`None`

Attributes:

Name	Type	Description
`n_elts`	`int`	Number of elements.
`n_comps`	`int`	Number of distjoint sets or components.
`__len__`		Calling `len(uf)` (where `uf` is an instance of `UnionFind`) returns the number of elements.
`__contains__`		For `uf` an instance of `UnionFind` and `x` an immutable object, `x in uf` returns `True` if `x` is an element in `uf`.
`__getitem__`		For `uf` an instance of `UnionFind` and `i` an integer, `res = uf[i]` returns the element stored in the `i`-th index. If `i` is not a valid index an `IndexError` is raised.
`__setitem__`		For `uf` and instance of `UnionFind`, `i` an integer and `x` an immutable object, `uf[i] = x` changes the element stored at the `i`-th index. If `i` is not a valid index an `IndexError` is raised.

References

[1][http://algs4.cs.princeton.edu/lectures/](http://algs4.cs.princeton.edu/lectures/)

`add(x)`

Add a single disjoint element.

Parameters:

Name	Type	Description	Default
`x`	`Any`	immutable object	required

`component(x)`

Find the connected component containing the given element.

Parameters:

Name	Type	Description	Default
`x`	`Any`	immutable object	required

Raises:

Type	Description
`ValueError`	If the given element is not found.

Returns:

Name	Type	Description
`set`	`set`	The component of x

`component_mapping()`

Return a dict mapping elements to their components.

The returned dict has the following semantics

`elt -> component containing elt`

If x, y belong to the same component, the comp(x) and comp(y) are the same objects (i.e., share the same reference). Changing comp(x) will reflect in comp(y). This is done to reduce memory.

But this behaviour should not be relied on. There may be inconsistency arising from such assumptions or lack thereof.

If you want to do any operation on these sets, use caution. For example, instead of

s = uf.component_mapping()[item]
s.add(stuff)
# This will have side effect in other sets

do

s = set(uf.component_mapping()[item]) # or
s = uf.component_mapping()[item].copy()
s.add(stuff)

or

s = uf.component_mapping()[item]
s = s | {stuff}  # Now s is different

Returns:

Name	Type	Description
`dict`	`dict`	A dict with the semantics: `elt -> component contianing elt`.

`components()`

Return the list of connected components.

Returns:

Name	Type	Description
`list`	`list`	A list of sets representing components

`connected(x, y)`

Return whether the two given elements belong to the same component.

Parameters:

Name	Type	Description	Default
`x`	`Any`	immutable object	required
`y`	`Any`	immutable object	required

Returns:

Name	Type	Description
`bool`	`bool`	True if x and y are connected, false otherwise.

`find(x)`

Find the root of the disjoint set containing the given element.

Parameters:

Name	Type	Description	Default
`x`	`Any`	immutable object	required

Returns:

Name	Type	Description
`int`	`int`	The (index of the) root.

Raises:

Type	Description
`ValueError`	If the given element is not found.

`roots()`

Return the set of roots of components

Returns:

Name	Type	Description
`set`	`set`	A set of elements

`union(x, y)`

Merge the components of the two given elements into one.

Parameters:

Name	Type	Description	Default
`x`	`Any`	immutable object	required
`y`	`Any`	immutable object	required