# union-find

> A union-find data structure for maintaining disjoint sets.

Latest version **1.0.2** (published 2015-03-12) · MIT license · 0 weekly downloads

## Install

```sh
npm install union-find
pnpm add union-find
yarn add union-find
bun add union-find
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.0.2 |
| Published | 2015-03-12 |
| First published | 2013-01-12 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 0 |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 27 |
| Author | Mikola Lysenko |
| Maintainers | mikolalysenko |
| Keywords | union, find, link, disjoint, set, connected, component, graph |

## Links

- npm: https://www.npmjs.com/package/union-find
- Repository: https://github.com/mikolalysenko/union-find
- Issues: https://github.com/mikolalysenko/union-find/issues
- npm.io page: https://npm.io/package/union-find

## Alternatives

- [apollo-link-http-common](https://npm.io/package/apollo-link-http-common.md) — 879.0K weekly downloads
- [react-relay](https://npm.io/package/react-relay.md) — 336.8K weekly downloads
- [relay-test-utils](https://npm.io/package/relay-test-utils.md) — 181.6K weekly downloads
- [@vendure/core](https://npm.io/package/@vendure/core.md) — 14.8K weekly downloads
- [@pnpm/deps.graph-sequencer](https://npm.io/package/@pnpm/deps.graph-sequencer.md) — 13.4K weekly downloads

## Recent versions

- 1.0.2 (latest) — 2015-03-12
- 1.0.1 — 2014-04-29
- 1.0.0 — 2014-04-29
- 0.0.4 — 2013-04-01
- 0.0.3 — 2013-01-21
- 0.0.2 — 2013-01-21
- 0.0.1 — 2013-01-18
- 0.0.0 — 2013-01-12

## README

union-find
==========

A basic union-find data structure for node.js.  For more information, see wikipdia:

[Disjoint Set Datastructures](http://en.wikipedia.org/wiki/Disjoint-set_data_structure)

Union find data structures solve the incremental connectivity problem. (That is maintaining a spanning forest under incremental insertions of edges.)  To handle fully dynamic connectivity, you can use a [dynamic forest](https://www.npmjs.org/package/dynamic-forest) data structure.

Usage
=====
Here is an example showing how to do connected component labelling.  Assume we are given a graph with `VERTEX_COUNT` vertices and a list of edges stored in array represented by pairs of vertex indices:

```javascript
//Import data structure
var UnionFind = require('union-find')

var VERTEX_COUNT = 8
var edges = [
    [0,1],
    [1,2],
    [2,3],
    [5,6],
    [7,1]
]

//Link all the nodes together
var forest = new UnionFind(VERTEX_COUNT)
for(var i=0; i<edges.length; ++i) {
  forest.link(edges[i][0], edges[i][1])
}

//Label components
var labels = new Array(VERTEX_COUNT)
for(var i=0; i<VERTEX_COUNT; ++i) {
  labels[i] = forest.find(i)
}
```

Installation
============

```
npm install union-find
```

# API

```javascript
var UnionFind = require('union-find')
```

## Constructor

### `var forest = new UnionFind(numVertices)`
Creates a new union-find data structure.

* `numVertices` is the number of vertices in the graph

**Returns** A new union-find data structure

## Methods

### `forest.length`
Returns the number of vertices in the forest

### `forest.makeSet()`
Creates a new vertex

**Returns** An integer id for the new vertex

### `forest.find(v)`
Returns an identifier representing the connected component of any given vertex

**Returns** An integer id representing the connected component of `v`

### `forest.link(s, t)`
Links a pair of connected components together

* `s` and `t` are both vertices
    
Credits
=======
(c) 2013-2014 Mikola Lysenko.  MIT License

---
_Source: https://npm.io/package/union-find · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._