The avatar for @bryangingechen
Bryan Gin-ge Chen
here to learn
Published
Edited
Apr 30, 2020
7 forks
Importers
55 stars
1
Meals
Fibonacci formalized 2: bees and carsFibonacci formalized 1: some sums
Union-find data structure
Also listed in…
Data Science in Observable
Data Science
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
config = ({W:svgW, H:svgH, // size of `svg`
x0:svgW/2, y0:svgH/2, // center of positioning circle
R:Math.min(svgW, svgH)/4, // radius of positioning circle
L:4.5, // ratio of links to radius of colored disks
size:20, // max radius of disks; see circleRad
hover:true, // if "true", then the force simulation will be activated when hovering over `svg`
bg:null, outline:null}) // these color the `svg` cell's background `rect` and outline stroke, respectively
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
randomWorker = {
const blob = new Blob(
[
`
importScripts("${await FileAttachment("union-find-1.0.2.js").url()}");

onmessage = event => {
const {data: {numOps, linkProb, findProb}} = event;

const uf = new unionFind(0);
for (let j=0; j < numOps; j++) {
const rnode = () => Math.floor(uf.roots.length*Math.random());
const r = Math.random();
if (uf.roots.length > 1 && r < linkProb) {
const l1 = rnode(),
l2 = rnode();
uf.link(l1,l2);
} else if (uf.roots.length > 0 && r > findProb) {
const f = rnode();
uf.find(f);
} else {
uf.makeSet();
}
// if (j > 0 && j%1000000 === 0)
// postMessage(uf);
}
postMessage(uf);
close();
};
`
],
{ type: "text/javascript" }
);
const script = URL.createObjectURL(blob);
invalidation.then(() => URL.revokeObjectURL(script));
return script;
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
adjMatCell = adjMatWidget(adjMatNumOps)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
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