disjoint-set

DisjointSet (a.k.a. union–find data structure or merge–find set) implementation for Python.

Prerequisites

The only requirement is using Python 3.8+. You can verify this by running:

$ python --version
Python 3.8.18

Installation

pip install disjoint-set

You can verify you're running the latest package version by running:

>>> import disjoint_set
>>> disjoint_set.__version__
'0.8.0'

Usage

Import & instantiate

>>> from disjoint_set import DisjointSet
>>> DisjointSet()
DisjointSet({})

>>> DisjointSet({1: 1})
DisjointSet({1: 1})

>>> DisjointSet.from_iterable([1,2,3])
DisjointSet({1: 1, 2: 2, 3: 3})

Perform find & union operations

>>> ds = DisjointSet()
>>> ds.find(1)
1

>>> ds.union(1,2)
>>> ds.find(1)
2

>>> ds.find(2)
2

Check if values belong to the same set

>>> ds = DisjointSet({1: 2, 2: 2, 3: 3})
>>> ds.connected(1,2)
True

>>> ds.connected(1,3)
False

Check if values are present within the data structure

>>> ds = DisjointSet()
>>> "a" in ds
False

>>> ds.find("a")
'a'

>>> "a" in ds
True

List elements and sets within the disjoint set

>>> ds = DisjointSet({1: 2, 2: 2, 3: 3})
>>> list(ds)
[(1, 2), (2, 2), (3, 3)]

>>> ds = DisjointSet({1: 2, 2: 2, 3: 3})
>>> list(ds.itersets())
[{1, 2}, {3}]

Contributing

Feel free to open any issues on github.

Authors

• Maciej Rapacz

License

This project is licensed under the MIT License - see the LICENSE.md file for details