#union-find #disjoint-set #client #graph-node #graph-theory #algorithm #connect-nodes

bin+lib cozad-union-find

An implementation of the union-find disjoint set graph algorithm

2 stable releases

1.1.0 Mar 20, 2022
1.0.0 Mar 19, 2022
0.1.0 Mar 19, 2022

#1455 in Algorithms

MIT license

21KB
338 lines

cozad-union-find

An implementation of the union-find disjoint set graph algorithm

MIT License

Quick Start

Using the named node interfaces

For relatively small networks you can simply interact with nodes by name.

extern crate cozad_union_find;
use cozad_union_find::union_find::client as ufclient;

fn main() {
    let mut client = ufclient::Client::new();

    client.add_node("A");
    client.add_node("B");
    client.add_node("C");
    client.add_node("D");
    client.add_node("E");
    client.add_node("F");
    client.add_node("G");
    client.add_node("H");
    client.add_node("I");
    client.add_node("J");


    client.connect_nodes("E", "D");
    client.connect_nodes("D", "I");
    client.connect_nodes("G", "F");
    client.connect_nodes("J", "E");
    client.connect_nodes("C", "B");
    client.connect_nodes("I", "J");
    client.connect_nodes("F", "A");
    client.connect_nodes("H", "B");
    client.connect_nodes("G", "B");
    client.connect_nodes("B", "A");
    client.connect_nodes("G", "H");

    println!("\nDisjoint sets found: {}", client.disjoint_set_count());
}

Output

Disjoint sets found: 2

Using the bulk interfaces

When you have a large volume of connections to process you can skip the lookups that occur with named nodes and use the bulk interfaces. The process involves giving a vector of node names and then specifying connections between nodes by index.

extern crate cozad_union_find;
use cozad_union_find::union_find::client as ufclient;
use cozad_union_find::union_find::client::BulkConnection as ufconnection;

fn main() {

    let mut bulk_client = ufclient::Client::new();
    let nodes = vec![
        String::from("A"), 
        String::from("B"), 
        String::from("C"),
        String::from("D"),
        String::from("E"),
        String::from("F"), 
        String::from("G"), 
        String::from("H"), 
        String::from("I"), 
        String::from("J")
    ];
    bulk_client.add_nodes_bulk(nodes);

    let connections = vec![
        ufconnection { a: 4, b: 3 },
        ufconnection { a: 3, b: 8 },
        ufconnection { a: 6, b: 5 },
        ufconnection { a: 9, b: 4 },
        ufconnection { a: 2, b: 1 },
        ufconnection { a: 8, b: 9 },
        ufconnection { a: 5, b: 0 },
        ufconnection { a: 7, b: 2 },
        ufconnection { a: 6, b: 1 },
        ufconnection { a: 1, b: 0 },
        ufconnection{ a: 6, b: 7 }
    ];
    bulk_client.connect_nodes_bulk(connections);

    println!("\nDisjoint sets found: {}", bulk_client.disjoint_set_count());
}

Output

Disjoint sets found: 2

Concepts

  • What is a disjoint set?
  • Why would I use this?
    • You have a large un-directed graph and you want to find non overlapping sets, such as for
    • 2D and 3D Percolation
    • Disease exposure
    • Contact tracing
    • Labeling clusters
  • How can I learn more?

Support

  • How do I request a change?
    • Please submit an issue or a pull request
  • How fast will my request be added?
    • Probably not very fast for requests outside of a support package because this repo is maintained by a working professional
    • If you require fast, predictable responses, please purchase a support package
  • Can support package be purchased?
    • Yes, various support packages can be purchased and customized for your needs. Support areas available include:
    • On demand support videos
    • 1:1 and team coaching
    • New features and other modifications

Dependencies

~3MB
~57K SLoC