scipy.cluster.hierarchy.

DisjointSet#

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

Datenstruktur für disjunkte Mengen für inkrementelle Konnektivitätsabfragen.

Hinzugefügt in Version 1.6.0.

Attribute:

n_subsetsint: Die Anzahl der Teilmengen.

Methoden

`add`(x)	Fügt das Element x zur disjunkten Menge hinzu.
`merge`(x, y)	Führt die Teilmengen von x und y zusammen.
`connected`(x, y)	Prüft, ob x und y in derselben Teilmenge sind.
`subset`(x)	Gibt die Teilmenge zurück, die x enthält.
`subset_size`(x)	Gibt die Größe der Teilmenge zurück, die x enthält.
`subsets`()	Gibt alle Teilmengen in der disjunkten Menge zurück.
`__getitem__`(x)	Findet das Wurzelelement von x.

Hinweise

Diese Klasse implementiert die disjunkte Menge [1], auch bekannt als Union-Find oder Merge-Find Datenstruktur. Die find Operation (implementiert in __getitem__) implementiert die Path Halving Variante. Die merge Methode implementiert die Merge by Size Variante.

Referenzen

[1]

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

Beispiele

>>> from scipy.cluster.hierarchy import DisjointSet

Initialisiert eine disjunkte Menge.

>>> disjoint_set = DisjointSet([1, 2, 3, 'a', 'b'])

Führt einige Teilmengen zusammen.

>>> disjoint_set.merge(1, 2)
True
>>> disjoint_set.merge(3, 'a')
True
>>> disjoint_set.merge('a', 'b')
True
>>> disjoint_set.merge('b', 'b')
False

Findet Wurzelelemente.

>>> disjoint_set[2]
1
>>> disjoint_set['b']
3

Testet die Konnektivität.

>>> disjoint_set.connected(1, 2)
True
>>> disjoint_set.connected(1, 'b')
False

Listet Elemente in der disjunkten Menge auf.

>>> list(disjoint_set)
[1, 2, 3, 'a', 'b']

Gibt die Teilmenge zurück, die 'a' enthält.

>>> disjoint_set.subset('a')
{'a', 3, 'b'}

Gibt die Größe der Teilmenge zurück, die 'a' enthält (ohne die Teilmenge tatsächlich zu instanziieren).

>>> disjoint_set.subset_size('a')
3

Gibt alle Teilmengen in der disjunkten Menge zurück.

>>> disjoint_set.subsets()
[{1, 2}, {'a', 3, 'b'}]