papyri
{ } Raw JSON

bundles / scipy 1.17.1 / 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

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')
✓
Find root elements: 
disjoint_set[2]
disjoint_set['b']
✓
Test connectivity: 
disjoint_set.connected(1, 2)
disjoint_set.connected(1, 'b')
✓
List elements in disjoint set: 
list(disjoint_set)
✓
Get the subset containing 'a': 
disjoint_set.subset('a')
✗
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()
✗

Aliases

  • scipy.cluster.hierarchy.DisjointSet

Referenced by

This package