### 6 releases

Uses old Rust 2015

0.2.4 | Oct 31, 2018 |
---|---|

0.2.3 | Oct 31, 2018 |

0.1.0 | Oct 22, 2018 |

#**1161** in Algorithms

**16,092** downloads per month

Used in **9** crates
(4 directly)

**Apache-2.0**

69KB

807 lines

# Partitions

A disjoint-sets/union-find implementation of a vector partitioned in sets that allows for efficient iteration over the elements of a set.

The main struct of this crate is

which has the functionality
of a `PartitionVec <T>`

`Vec``<`T`>`

and in addition divides the elements of this vector in sets.
The elements each start in their own set and sets can be joined with the
`union`

method.
You can check if elements share a set with the `same_set`

method and iterate
on the elements in a set with the `set`

method.
The `union`

and `same_set`

methods are extremely fast and have an amortized
complexity of `O``(``α``(`n`)``)`

where `α`

is the inverse Ackermann function and `n`

is
the length.
This complexity is proven to be optimal and `α``(`n`)`

has value below 5 for any `n`

that can be written in the observable universe.
The next element of the iterator returned by `set`

is found in `O``(``1``)`

time.The Disjoint-Sets algorithm is used in high-performance implementations of unification. It is also a key component in implementing Kruskal's algorithm to find the minimum spanning tree of a graph.

## Using Partitions

The recommended way to use this crate is to add a line into your

such as:`Cargo .toml`

`[``dependencies``]`
`partitions ``=` `"`0.2`"`

and then add the following to to your

or `lib .rs`

`main``.`rs

:`extern` `crate` partitions`;`

## License

Partitions is distributed under the terms of the Apache License (Version 2.0).

#### Dependencies

~1MB

~24K SLoC