# Union-Find

A JS implementation of disjoint-set data structure for node and browsers.

## Installation

The library is available as a npm package:

```
npm install @manubb/union-find
```

## Examples

Examples directory contains implementations of:

- an algorithm to compute connected components of a graph
- Kruskal algorithm
- Hoshen-Kopelman algorithm

Examples can be run with:

```
npm run example:components
npm run example:hk
npm run example:kruskal
```

## API

The library uses trees to encode sets. It exposes three functions.

### makeSet

`makeSet();`

returns an object representing a set containing one element. It has two properties: `parent`

and `rank`

. You can then safely add other properties that suit to your needs.

Note that you can also use your own custom function that should return an object `obj`

with:

```
obj.rank === 0
obj.parent === obj
```

At any time, you can check if `obj`

is the root of a tree with:

`obj.parent === obj`

### find

`find(obj)`

returns the root of the tree that contains `obj`

. Checking if two objects belong to the same set can be done with:

`find(obj1) === find(obj2)`

### union

`union(obj1, obj2)`

merges the sets containing `obj1`

and `obj2`

and returns `undefined`

.

## Complexity

`makeSet`

run in constant time. If `n`

is the total number of elements, `find`

and `union`

run in amortized time `O(α(n))`

where α is the inverse Ackermann function. It is a very slowly increasing function: `α(10^35164)=5`

. For all practical purposes, one can consider that `find`

and `union`

run in constant amortized time.

## Usage

`import { makeSet, find, union } from '@manubb/union-find';`

or

`const { makeSet, find, union } = require('@manubb/union-find');`