Published
Edited
Jan 13, 2022
Importers
4 stars
Insert cell
Insert cell
// https://github.com/mikolalysenko/union-find
UnionFind = (function() {

"use strict"; "use restrict";


function UnionFind(count) {
this.roots = new Array(count);
this.ranks = new Array(count);
for(var i=0; i<count; ++i) {
this.roots[i] = i;
this.ranks[i] = 0;
}
}

var proto = UnionFind.prototype

Object.defineProperty(proto, "length", {
"get": function() {
return this.roots.length
}
})

proto.makeSet = function() {
var n = this.roots.length;
this.roots.push(n);
this.ranks.push(0);
return n;
}

proto.find = function(x) {
var x0 = x
var roots = this.roots;
while(roots[x] !== x) {
x = roots[x]
}
while(roots[x0] !== x) {
var y = roots[x0]
roots[x0] = x
x0 = y
}
return x;
}

proto.link = function(x, y) {
var xr = this.find(x)
, yr = this.find(y);
if(xr === yr) {
return;
}
var ranks = this.ranks
, roots = this.roots
, xd = ranks[xr]
, yd = ranks[yr];
if(xd < yd) {
roots[xr] = yr;
} else if(yd < xd) {
roots[yr] = xr;
} else {
roots[yr] = xr;
++ranks[xr];
}
}

return UnionFind;
})()
Insert cell
// adapted from https://github.com/mikolalysenko/union-find
test = {
var vertices = [0,1,2,3,4,5,6,7,8];
var edges = [
[0,1],
[1,2],
[2,3],
[5,6],
[7,1]
]

// Link all the nodes together
var forest = new UnionFind(vertices.length)
edges.forEach(edge => forest.link(edge[0], edge[1]))

// Label components
return vertices.map(i => forest.find(i))
}
Insert cell
// unit test
JSON.stringify(test) === "[0,0,0,0,4,5,5,0,8]"
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more