ngraph.disjoint-set

Disjoint-set data structure

usage

var DisjointSet = require('ngraph.disjoint-set');

// we can create two separate sets:
var a = new DisjointSet();
var b = new DisjointSet();

// Unite them:
a.union(b);

// After sets are united, searching for representative element of the set
// should result in exact same element:
assert(a.find() === b.find());

Optionally you can pass payload to identify element of the set:

var DisjointSet = require('ngraph.disjoint-set');

// we can create two separate sets:
var a = new DisjointSet('a');
assert(a.payload === 'a');

Performance

Worst-case running time of O(α(N)) per union(), find() operations. Creation of a new set is O(1).

α(N) is inverse of Ackerman function; In practice the amortized running time per operation is a small constant (less than 5 for all practical values of n).

install

With npm do:

npm install ngraph.disjoint-set

license

MIT