allocation-free union-find library for bare metal environments

The library provides the following algorithms that is used with UnionFind. - QuickFind - QuickUnion - Weighted QuickUnion - Weighted QuickUnion With Path Compression (Default)

Setup

Cargo.toml setup

toml [dependencies] pulau-rs = "0.2.0"

Asymptotic Complexity

| Algorithm | Struct | Init | Union | Find | Connected | | :----------------------------------------------- | :-------------------------: | :----: | --------: | --------: | --------: | | QuickFind | QuickFind | O(N) | O(N) | O(1) | O(1) | | QuickUnion | QuickUnion<false, false> | O(N) | O(N) | O(N) | O(N) | | Weighted QuickUnion | QuickUnion<ByRank, false> | O(N) | O(lg N) | O(lg N) | O(lg N) | | Weighted (Rank) QuickUnion With Path Compression | QuickUnion<ByRank, true> | O(N) | Θ(α(N)) | Θ(α(N)) | Θ(α(N)) | | Weighted (Size) QuickUnion With Path Compression | QuickUnion<BySize, true> | O(N) | Θ(α(N)) | Θ(α(N)) | Θ(α(N)) |

*Where α is the inverse Ackermann function

Applications of UnionFind

• Checking for connected components in a graph
• Checking for cycles in a graph
• Searching for connected components in an image
• Finding minimum spanning tree using Kruskal

Example Usage

```rust use pulaurs::{UnionFind, QuickFind, QuickUnion, BySize}; fn makeuf_quickfind() { // construct with quickfind algorithm with fixed size 10 let mut uf = UnionFind::::new(); }

fn makeufquickunion() { // construct weighted quickunion with path compression algorithm with fixed size 10 let mut uf = UnionFind::::new(); // construct weighted quickunion with path compression using size heuristics and fixed size 10 let mut ufwithsz = UnionFind::, u8, 10>::new(); uf.unionsets(1,2); uf.unionsets(2,3); uf.union_sets(2,3); assert!(uf.connected(1, 3)); } ```

License

pulau-rs is licensed under MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)