bundles / scipy 1.18.0 / scipy / _lib / _disjoint_set / DisjointSet

class

`scipy._lib._disjoint_set:DisjointSet`

source: /scipy/_lib/_disjoint_set.py:6

Signature

class DisjointSet(elements = None)

Members

Summary

Disjoint set data structure for incremental connectivity queries.

Extended Summary

Parameters

elements : sequence of hashable objects: Elements of the disjoint set.

Attributes

n_subsets : int: The number of subsets.

Methods

add
merge
connected
subset
subset_size
subsets
__getitem__

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.

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)
disjoint_set.merge(3, 'a')
disjoint_set.merge('a', 'b')
disjoint_set.merge('b', 'b')

✓

False

Find root elements:

disjoint_set[2]
disjoint_set['b']

✓

Test connectivity:

disjoint_set.connected(1, 2)
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')

✗

{3, 'a', 'b'}

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

disjoint_set.subset_size('a')

✓

Get all subsets in the disjoint set:

disjoint_set.subsets()

✗

[{1, 2}, {3, 'a', 'b'}]