ngraph.disjoint-set

1.2.0 • Public • Published

ngraph.disjoint-set build status

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

Package Sidebar

Install

npm i ngraph.disjoint-set

Weekly Downloads

6

Version

1.2.0

License

MIT

Unpacked Size

5.05 kB

Total Files

6

Last publish

Collaborators

  • anvaka