ddotten / partitions

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

Partitions

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

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;

This crate is fully documented on docs.rs.

License

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

partitions's Issues

Warnings that will become errors

It looks like the latest commit for this crate was over four years ago, so I'm not sure whether it's still being maintained.

It looks like it contains some compiler warnings (which may not have been warnings at the time) that are soon going to become compiler errors. These looks like very simple fixes, so if you like I'm happy to submit a PR to fix these if you'd accept it.

EDIT: To clarify, I am building on nightly so I don't know whether these are flagged currently in stable.

Exposed "find" method? (Or a way of storing info about each set)

Hey,

First of all, great crate! I've been playing with using it and so far I find the API far more convenient and intuitive than the other Rust Union-Find implementations out there.

However, for my use case I need to be able to store information about the core set of "root" vertices in the union-find (i.e. the indices in the vector that are representatives of their corresponding sets). This seems to not be possible because find is -- while part of the implementation -- not public. Is it possible to expose find as public?

In the source code it states

This method is private to keep the representative of the set an implementation detail, this gives greater freedom to change the representative of the set.

But I think, unless I am missing something, that there is no way to store information separately about each set in the PartitionVec unless you have access to a canonical representative.

In particular, the workflow of my use case is that I have a graph where edges are stored as linked lists at each vertex, and then vertices are sometimes "merged" using union-find. Whenever two vertices are merged, I need to call find on each vertex to get the new canonical vertex name, then merge the two edge lists to get a single edge list at the new canonical vertex name. Is there a way to do this with the current exposed API?

(I believe this is a pretty standard algorithms use case, though I have not implemented such things before so I may be missing an alternative way to do it.)

If you do think it's possible to make find public, or have another fix in mind, I'd be happy to contribute a pull request.

New release in crates.io

Hi, is it possible to update the version of partitions in crates.io with the changes from #3 ? Thanks in advance!