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)
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
PartitionVec<T> which has the functionality
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
You can check if elements share a set with the
same_set method and iterate
on the elements in a set with the
same_set methods are extremely fast and have an amortized
α is the inverse Ackermann function and
This complexity is proven to be optimal and
α(n) has value below 5 for any
that can be written in the observable universe.
The next element of the iterator returned by
set is found in
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.
The recommended way to use this crate is to add a line into your
[dependencies] partitions = "0.2"
and then add the following to to your
extern crate partitions;
Partitions is distributed under the terms of the Apache License (Version 2.0).