Classe « DisjointSet »

Informations générales

Héritage

builtins.object
    DisjointSet

Définition

class DisjointSet(builtins.object):

help(DisjointSet)

Disjoint set data structure for incremental connectivity queries.

.. versionadded:: 1.6.0

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.

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

Constructeur(s)

Signature du constructeur	Description
__init__(self, elements=None)

Liste des opérateurs

Signature de l'opérateur	Description
__contains__(self, x)
__getitem__(self, x)	Find the root element of `x`. _{[extrait de __getitem__.__doc__]}

Opérateurs hérités de la classe object

__eq__, __ge__, __gt__, __le__, __lt__, __ne__

Liste des méthodes

Toutes les méthodes Méthodes d'instance Méthodes statiques

Signature de la méthode	Description
__iter__(self)	Returns an iterator of the elements in the disjoint set. _{[extrait de __iter__.__doc__]}
__len__(self)
add(self, x)	Add element `x` to disjoint set _{[extrait de add.__doc__]}
connected(self, x, y)	Test whether `x` and `y` are in the same subset. _{[extrait de connected.__doc__]}
merge(self, x, y)	Merge the subsets of `x` and `y`. _{[extrait de merge.__doc__]}
subset(self, x)	Get the subset containing `x`. _{[extrait de subset.__doc__]}
subset_size(self, x)	Get the size of the subset containing `x`. _{[extrait de subset_size.__doc__]}
subsets(self)	Get all the subsets in the disjoint set. _{[extrait de subsets.__doc__]}