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 - 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'}]