Mnemonist

StaticDisjointSet


A StaticDisjointSet is a structure representing sets of sets using the “union-find” technique.

This implementation is static because it works on a range of indices starting from 0 and going up to a fixed size given at instantiation time.

It is however a very memory-efficient way to solve some issues such as finding connected components in a graph.

var StaticDisjointSet = require('mnemonist/static-disjoint-set');

Constructor

The StaticDisjointSet takes an initial size at instantiation time (i.e. the total number of items we are going to handle, the number of nodes in your graph, for instance).

var sets = new StaticDisjointSet(size);

Members

Methods

Mutation

Read

#.dimension

Total number of sets known by the disjoint set (obviously less than or equal to the size).

var sets = new StaticDisjointSet(4);

sets.union(1, 2);
sets.union(1, 3);

set.size;
>>> 4
set.dimension;
>>> 2

#.size

Total number of stored items.

var sets = new StaticDisjointSet(4);

set.size;
>>> 4

#.union

O(1) or O(α(n)) to be exact.

Perform the union of two items. If they belong to different sets, their respective sets will be merged into a single one.

var sets = new StaticDisjointSet(4);

sets.union(1, 2);
sets.union(1, 3);

#.compile

O(n) or O(n α(n)) to be exact.

Compile the disjoint sets into an array of arrays.

var sets = new StaticDisjointSet(4);

sets.union(1, 2);
sets.union(1, 3);

sets.compile();
>>> [[0], [1, 2, 3]]

#.find

O(1) or O(α(n)) to be exact.

Returns the root item of the given item’s current set.

var sets = new StaticDisjointSet(4);

sets.union(1, 2);
sets.union(1, 3);

sets.find(2);
>>> 1

#.mapping

O(n) or O(n α(n)) to be exact.

Returns an array whose values are the id of the item’s set.

var sets = new StaticDisjointSet(4);

sets.union(1, 2);
sets.union(1, 3);

sets.mapping();
>>> [0, 1, 1, 1]