disjointset
Disjoint-set implementation (with path compression and ranks heuristic).
Installation
$ npm i disjointset
Usage
var DisjointSet = ; var edges = v: 0 u: 1 w: 7 v: 0 u: 3 w: 5 v: 1 u: 2 w: 8 v: 1 u: 3 w: 9 v: 1 u: 4 w: 7 v: 2 u: 4 w: 5 v: 3 u: 4 w: 15 v: 3 u: 5 w: 6 v: 4 u: 5 w: 8 v: 4 u: 6 w: 9 v: 5 u: 6 w: 11 ; // n - vertices count { var edges = edges set = n mst = ; edges; return mst;}
Another example – find groups of elements with connectivity defined by fn
(optimised variant):
function subsets(items, fn) {
var set = new DisjointSet(items.length),
roots = set.roots,
result = [];
for (var i = 0, len = items.length; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (!set.isConnected(i, j) && fn(items[i], items[j])) {
set.union(i, j);
}
}
(result[roots[i]] || (result[roots[i]] = [])).push(items[i]);
}
return result.filter(Boolean);
}
API
size
License
MIT