scipy.cluster.hierarchy.

# DisjointSet#

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

Disjoint set data structure for incremental connectivity queries.

Attributes:
n_subsetsint

The number of subsets.

Methods

 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. Get the subset containing x. Get the size of the subset containing x. Get all the subsets in the disjoint set. 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'}]
```