Allocation-free UnionFind library for bare metal environments

Budi Syahiddin

Last update: Dec 10, 2022

Related tags

Overview

Allocation-free UnionFind 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

[dependencies]
pulau-rs = "0.1.0"

Asymptotic Complexity

Algorithm	Struct	Init	Union	Find	Connected
QuickFind	`QuickFind`	`O(N)`	`O(N)`	`O(1)`	`O(1)`
QuickUnion	`QuickUnion`	`O(N)`	`O(N)`	`O(N)`	`O(N)`
Weighted (Rank) QuickUnion With Path Compression	`QuickUnion`	`O(N)`	`Amortized O(α(N))`	`Amortized O(α(N))`	`Amortized O(α(N))`
Weighted (Size) QuickUnion With Path Compression	`QuickUnion`	`O(N)`	`Amortized O(α(N))`	`Amortized O(α(N))`	`Amortized O(α(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

use pulau_rs::{UnionFind, QuickFind, QuickUnion, BySize};
fn make_uf_quickfind() {
    // construct with quickfind algorithm with fixed size 10
    let mut uf = UnionFind::<QuickFind, u32, 10, 0>::new();
}

fn make_uf_quickunion() {
    // construct weighted quickunion with path compression algorithm with fixed size 10
    let mut uf = UnionFind::<QuickUnion, u32, 10>::new();
    // construct weighted quickunion with path compression using size heuristics and fixed size 10
    let mut uf_with_sz = UnionFind::<QuickUnion<BySize>, u8, 10>::new();
    uf.union_sets(1,2);
    uf.union_sets(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)

A Rust library for parsing the SOME/IP network protocol (without payload interpretation).

someip_parse A Rust library for parsing the SOME/IP network protocol (without payload interpretation). Usage Add the following to your Cargo.toml: [de

18 Oct 31, 2022

Bevy plugin for the GGRS P2P rollback networking library.

Bevy_GGRS Bevy plugin for the 👉 GGRS P2P rollback networking library. The plugin creates a custom stage with a separate schedule, which handles corre

120 Jan 6, 2023

A library for easily creating WebRTC data channel connections in Rust

Cyberdeck A library for easily creating WebRTC data channel connections in Rust.

34 Nov 10, 2022

Modrinth API is a simple library for using Modrinth's API in Rust projects

Ferinth is a simple library for using the Modrinth API in Rust projects. It uses reqwest as its HTTP(S) client and deserialises responses to typed structs using serde.

20 Dec 8, 2022

An LV2 host library for Rust.

Livi A library for hosting LV2 plugins. Note: This is a work in progress and has not yet been full tested. Supported LV2 Features LV2 has a simple cor

11 Nov 8, 2022

A Rust compiler plugin and support library to annotate overflow behavior

overflower This project contains a compiler plugin and supporting library to allow the programmer to annotate their code to declare how integer overfl

104 Nov 28, 2022

Dav-server-rs - Rust WebDAV server library. A fork of the webdav-handler crate.

dav-server-rs A fork of the webdav-handler-rs project. Generic async HTTP/Webdav handler Webdav (RFC4918) is defined as HTTP (GET/HEAD/PUT/DELETE) plu

30 Dec 29, 2022

Peer-to-peer communications library for Rust based on QUIC protocol

qp2p Crate Documentation MaidSafe website SAFE Dev Forum SAFE Network Forum Overview This library provides an API to simplify common tasks when creati

337 Dec 14, 2022

Lightweight p2p library. Support build robust stable connection on p2p/distributed network.

Chamomile Build a robust stable connection on p2p network features Support build a robust stable connection between two peers on the p2p network. Supp