disjoint-set

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
add(<Object> val)	this	Constant	Adds object to the set.
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
set.add(person1)
    .add(person2)
    .add(person3)
    .add(person4)
    .add(person5)
    .add(person6);

// 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.9 — 22.02.2024

• minor fixes (readme, package.json)

1.1.8 — 04.02.2015

• minor fixes (readme, package.json)

1.1.7 — 04.02.2015

• minor fixes (readme, package.json)

1.1.6 — 21.10.2014

• minor fixes (readme, package.json)

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

• connected() method added
• find() method changed

1.0.0 — 06.04.2014

• First Disjoint-set release