Skip to main content
`Ctrl`+`K`
scipy.cluster.hierarchy.

# DisjointSet

class scipy.cluster.hierarchy.DisjointSet(elements=None)

  Disjoint set data structure for incremental connectivity queries.

  Added in version 1.6.0.

  Attributes:
    n_subsets int

      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

  [1]

  https://en.wikipedia.org/wiki/Disjoint-set_data_structure

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