# `union_find`

[![build status](https://gitlab.com/rustychoi/union_find/badges/main/pipeline.svg)](https://gitlab.com/rustychoi/union_find/-/pipelines/latest)
[![crate](https://img.shields.io/crates/v/union-find-rs.svg)](https://crates.io/crates/union-find-rs)
[![docs](https://docs.rs/union-find-rs/badge.svg)](https://docs.rs/union-find-rs)

Implementations of [the disjoint-set forest data structure that supports the union-find
algorithm](https://en.wikipedia.org/wiki/Disjoint-set_data_structure).

This crate focuses on ease of use and simplicity.

## Background / Context

1. [Wikipedia article: disjoint-set data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)

## Getting Started

Specify `union-find-rs` as a dependency in your `Cargo.toml`.

```toml
[dependencies]
union-find-rs = "^0.2"
```

1. add the following to the top of your `.rs` file
    1. ```rust
       use union_find_rs::prelude::*;
       ```
1. see the trait [`UnionFind`](https://docs.rs/union-find-rs/latest/union_find_rs/traits/trait.UnionFind.html) 
for the core operations of union-find
1. see the struct [`DisjointSets`](https://docs.rs/union-find-rs/latest/union_find_rs/disjoint_sets/struct.DisjointSets.html) 
for an implementation of [`UnionFind`](https://docs.rs/union-find-rs/latest/union_find_rs/traits/trait.UnionFind.html) 

## Example

```rust
use std::collections::HashSet;
use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.make_set(1).unwrap();
sets.make_set(4).unwrap();
sets.make_set(9).unwrap();

sets.union(&1, &4).unwrap();

// the disjoint sets as a vector of vectors
let as_vec: Vec<HashSet<usize>> = sets.into_iter().collect();

// there should be 2 disjoint sets, where one of them only contains `9` and the other one
// only contains `1` and `4`
assert_eq!(as_vec.len(), 2);
assert!(
    as_vec
        .iter()
        .any(|set| set == &vec![9].into_iter().collect::<HashSet<usize>>())
);
assert!(
    as_vec
        .iter()
        .any(|set| set == &vec![1, 4].into_iter().collect::<HashSet<usize>>())
);
```