Published
Edited
Jan 13, 2022
Importers
4 stars
Hello, PGLiteINSEE ParquetHello, apcachDruidJS workerHello, OrbitWord Tour: 40k words and their friendsHello, spectral.jsHello, petite-vueHello, @thi.ng/grid-iteratorsHello, thumbhashHello, SwissGLHello, QOI (and glitches)Hello, orbHello, cosmographHello, TabulatorUsing d3.blur with PlotMath.cbrtHello debounceColorcetHello, gliiHello, Open MeteoHello, PyWaveletsHello, typesenseHello, libgifHello, kmeans-engineHappy anniversary, Project Gutenberg!Hello, fflateHello, ArchieML!Hello, d3-bboxCollideHello, jsgeoda!Hello, EDTF!Hello, protovis!Hello, placekeyHello, fuse.jsHello, Reorder.jsHello, shadow DOMjszipHello, procedural-glHello, qhullHello, genetic-jsDruidJSHello, Tippy.jsHello, paintWorkletBig πHello, AutoencoderHello, Shakespearean UUIDsHello, ccwt.jsHello, constrainautorHello, talismanHello, polygon-offsetHello p-queueHello async-poolHello rollup-plugin-asciiHello, algebra.jsHello, pixi.jsHello, d3-renderHello zip/unzipCumulative Wikipedia DonationsHTML <details>regl textureHello, npyjsHello protobufHello, pencil touchHello, LOESSHello html2canvaslegra mapscolor2cssHello, ecsy2D point distributionsHello, delatinThe gpu.js loopDijkstra’s shortest-path treeHello nojacko/Dijkstras-jsHello, tcort/dijkstrajsHello, lambdabaa/dijkstraHello, gpu.js v2Hello jsqrHello qrcodeHello SharedArrayBufferHello GamePad APIHello vtk.jsHello nd4jsHello BiofabricTravelling with a self-organizing mapHello glitchHello UMAP-jsHello pandemoniumHello iocaneHello JSON-editorHello d3-griddingHello mljs/knnWorkerHello lalolibImage to GPU.jsImage to blink.jsTissot's indicatrixVega projectionsHello WebCLGLUsing d3-inertia with observableVideo contouring 3ngraph: pagerank, louvain…Perceptron (simple statistics)mljsHello h3-jsEmoji FlagsHello, poisson-disk-sampling
Union-Find
// 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;
})()
// 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))
}
// unit test
JSON.stringify(test) === "[0,0,0,0,4,5,5,0,8]"
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.
