scipy.cluster.hierarchy.DisjointSet#
- class scipy.cluster.hierarchy.DisjointSet(elements=None)[source]#
Disjoint set data structure for incremental connectivity queries.
New in version 1.6.0.
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
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'}]
- 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.