#union-find #disjoint-sets

partitions

A disjoint-sets/union-find implementation that allows for efficient iteration over elements of a set

6 releases

Uses old Rust 2015

0.2.4 Oct 31, 2018
0.2.3 Oct 31, 2018
0.1.0 Oct 22, 2018

#1200 in Algorithms

Download history 3720/week @ 2023-10-18 3972/week @ 2023-10-25 2990/week @ 2023-11-01 2633/week @ 2023-11-08 2277/week @ 2023-11-15 2270/week @ 2023-11-22 3215/week @ 2023-11-29 3880/week @ 2023-12-06 2441/week @ 2023-12-13 1463/week @ 2023-12-20 776/week @ 2023-12-27 3030/week @ 2024-01-03 3208/week @ 2024-01-10 3457/week @ 2024-01-17 2963/week @ 2024-01-24 2237/week @ 2024-01-31

12,543 downloads per month
Used in 6 crates (3 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.

Latest version Documentation Average time to resolve an issue Percentage of issues still open Maintenance Build Status

The main struct of this crate is PartitionVec<T> which has the functionality of a 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 Cargo.toml such as:

[dependencies]
partitions = "0.2"

and then add the following to to your lib.rs or main.rs:

extern crate partitions;

License

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

Dependencies

~1.5MB
~26K SLoC