scipy.cluster.hierarchy.

DisjointSet#

class scipy.cluster.hierarchy.DisjointSet(elements=None)[source]#

Disjoint set data structure for incremental connectivity queries.

Added in version 1.6.0.

Attributes:

n_subsetsint: The number of subsets.

Methods

`add`(x)	Add element x to disjoint set
`merge`(x, y)	Merge the subsets of x and y.
`connected`(x, y)	Test whether x and y are in the same subset.
`subset`(x)	Get the subset containing x.
`subset_size`(x)	Get the size of the subset containing x.
`subsets`()	Get all the subsets in the disjoint set.
`__getitem__`(x)	Find the root element of x.

Notes

This class implements the disjoint set [1], also known as the union-find or merge-find data structure. The find operation (implemented in __getitem__) implements the path halving variant. The merge method implements the merge by size variant.

References

[1]

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Examples

>>> from scipy.cluster.hierarchy import DisjointSet

Initialize a disjoint set:

>>> disjoint_set = DisjointSet([1, 2, 3, 'a', 'b'])

Merge some subsets:

>>> disjoint_set.merge(1, 2)
True
>>> disjoint_set.merge(3, 'a')
True
>>> disjoint_set.merge('a', 'b')
True
>>> disjoint_set.merge('b', 'b')
False

Find root elements:

>>> disjoint_set[2]
1
>>> disjoint_set['b']
3

Test connectivity:

>>> disjoint_set.connected(1, 2)
True
>>> disjoint_set.connected(1, 'b')
False

List elements in disjoint set:

>>> list(disjoint_set)
[1, 2, 3, 'a', 'b']

Get the subset containing ‘a’:

>>> disjoint_set.subset('a')
{'a', 3, 'b'}

Get the size of the subset containing ‘a’ (without actually instantiating the subset):

>>> disjoint_set.subset_size('a')
3

Get all subsets in the disjoint set:

>>> disjoint_set.subsets()
[{1, 2}, {'a', 3, 'b'}]