# disjoint-set

1.1.9 • Public • Published

## Disjoint-set

Disjoint-set is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non overlapping) subsets. A union–find algorithm is an algorithm that performs two useful operations on such a data structure:

• Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset;
• Union: Join two subsets into a single subset.

Use to solve network connectivity problem.

## API

### Creation

Factory Description
`disjointSet()` Instantiates disjoint-set data structure.

### Methods

Method Returns Order of growth (worst case) Description
union(<Object> val1, <Object> val2) Boolean Logarithmic Сonnects val1 with val2.
find(<Object> val) String Logarithmic Returns identifier of the subset by given value.
connected(<Object> val1, <Object> val2) Boolean Logarithmic Returns true when val1 and val2 are connected.
extract() Array Linear Returns all items grouped by subsets.
destroy() Constant Clears data structure.

## Usage example

``````var set = disjointSet(); // instantiate disjoint-set data structure

var person1 = {
name: 'Volodymyr',
surname: 'Velykyj'
}
var person2 = {
name: 'Yaroslav',
surname: 'Mydryi'
}
var person3 = {
name: 'Bohdan',
surname: 'Khmelnytskyi'
}
var person4 = {
name: 'Ivan',
surname: 'Mazepa'
}
var person5 = {
name: 'Jim',
surname: 'Morrison'
}
var person6 = {
name: 'Ray',
surname: 'Manzarek'
}

// add objects to the set

// connect some objects to each other
set.union(person1, person2);
set.union(person2, person3);
set.union(person3, person4);
set.union(person5, person6);

// check connections
console.log(set.connected(person1, person2)); // returns true. Direct connection
console.log(set.connected(person1, person4)); // returns true. Indirect connection
console.log(set.connected(person5, person6)); // returns true. Another direct connection
console.log(set.connected(person4, person5)); // returns false. No connection

/**
* returns two arrays grouped by connection:
* [
*     [person1, person2, person3, person4],
*     [person5, person6]
* ]
*/
console.log(set.extract());
``````

## Development

``````npm install # install dependencies
npm test    # check the code with JSHint and run tests
``````

## Papers

• Robert Sedgewick and Kevin Wayne, Algorithms, 4th edition, page 216

## Changelog

### 1.1.5 — 01.05.2014

• critical bug (wrong subtree connections) fixed

### 1.1.4 — 25.04.2014

• performance optimization: stringify key generator changed to Numerical ids

### 1.1.3 — 10.04.2014

• quick-union algorithm changed to weighted quick-union

### 1.1.2 — 08.04.2014

• quick-find algorithm changed to quick-union

### 1.1.1 — 08.04.2014

• unit tests done

### 1.1.0 — 07.04.2014

• find() method changed

### 1.0.0 — 06.04.2014

• First Disjoint-set release

## Package Sidebar

### Install

`npm i disjoint-set`

### Repository

github.com/AndriiHeonia/disjoint-set

### Homepage

github.com/AndriiHeonia/disjoint-set

25

1.1.9

none

17.7 kB

8