DisjointSet — SciPy v1.15.2 Manual (original) (raw)

scipy.cluster.hierarchy.

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

Disjoint set data structure for incremental connectivity queries.

Added 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