29:null 2a:["$","title",null,{"children":"Union-find data structure | Jean Constant | Observable"}] 2f:T16d0,svg = { if (show) { const svgW = config.W, svgH = config.H, hover = config.hover; const strokeW = circleRad / 3, fontSize = 1.2 * circleRad; const svg = (this && this.tagName === 'svg') ? d3.select(this) : d3.select(DOM.svg(svgW, svgH)); if (!this && (config.bg || config.outline)) svg.append('rect') .attr('width', '100%') .attr('height', '100%') .attr('stroke', config.outline || 'none') .attr('stroke-width', config.outline ? 4 : 'none') .attr('fill', config.bg || 'none'); const widthChanged = parseInt(svg.attr('width')) !== svgW; const uid = svg.attr('data-arrow-id') || DOM.uid('arrow').id; svg.attr('data-arrow-id', uid) .attr('width', svgW) .attr('height', svgH) .attr('viewBox', `0 0 ${svgW} ${svgH}`); if (hover) { svg.on("mouseover", () => sim.alphaTarget(1).restart()); svg.on("mouseout", () => sim.alphaTarget(0)); } // defs const defs = svg.select("defs").empty() ? svg.append("defs") : svg.select("defs"); let arrow = defs.selectAll("marker").data(dataLabels, d => d.key); arrow.exit().remove(); const enterArrow = arrow.enter() .append("marker") .attr("viewBox", "0 -5 10 10") .attr("refX", 5) .attr("refY", 0) .attr("markerWidth", 3) .attr("markerHeight", 3) .attr("orient", "auto"); enterArrow .append("path") .attr("d", "M0,-5L10,0L0,5") .attr("fill", d => colorArray[d.key]) .attr("stroke", d => colorArray[d.key]); arrow = arrow.merge(enterArrow); arrow .attr("id", d => `${uid}-${d.key}`); // main g const g = svg.select("g").empty() ? svg.append('g') : svg.select("g"); let selection = g.selectAll('g').data(dataLabels, d => d.key); let edge = g.selectAll("path").data(links, d => d.id); // exit const exitSelection = selection.exit(); exitSelection.remove(); const exitEdge = edge.exit(); exitEdge.remove(); // enter const enterEdge = edge.enter().append("path").lower() // place at the bottom .attr("stroke", "red") .attr("stroke-width", 1.5*strokeW) .attr("marker-mid", d => `url(#${uid}-${d.t})`); const enterSelection = selection.enter().append('g') .attr("cursor", "grab") .attr('transform', d => { const pad = circleRad * (d.rank/3 + 1); // constrain to svg d.x = Math.min(Math.max(pad, d.x), svgW - pad); d.y = Math.min(Math.max(d.y, pad), svgH - pad); return `translate(${d.x},${d.y})`; }) .call(d3.drag() .on("start", dragstarted) .on("drag", dragged) .on("end", dragended)); const circles = enterSelection.append('circle') .attr('stroke-width', d => (d.root === d.key) ? strokeW : strokeW / 2) .attr('stroke', 'red'); const text = enterSelection.append('text') .attr("text-anchor", "middle") .attr("dominant-baseline", "central") .attr("font-size", fontSize) .attr("font-weight", d => (d.root === d.key) ? "bold" : "normal") .text(d => d.key); // update selection.selectAll('circle') .attr('stroke-width', d => (d.root === d.key) ? 2 : 1) .attr('stroke', "currentColor"); selection.selectAll('text') .attr("font-size", fontSize); edge .attr("stroke-width", strokeW) .attr("stroke", d => colorArray[d.t]); // merge selection = selection.merge(enterSelection); selection.selectAll('circle') .attr("stroke-dasharray", d => (d.root === d.key) ? "2 1" : "none") .attr('fill', d => colorArray[d.key]) .attr('r', d => circleRad * (d.rank/5 + 1)); selection.selectAll('text') .attr('fill', d => invertColor(colorArray[d.key], true)); edge = edge.merge(enterEdge); // the following conditional keeps sim quiescent if no changes to labels occurred // (useful when the sim is going crazy due to disk-packing issues) if (!enterEdge.empty() || !enterSelection.empty() || !exitEdge.empty() || !exitSelection.empty()) sim.force('charge', d3.forceManyBody() .strength(d => ((d.root === d.key) ? -70 : 0))) .force('collision', d3.forceCollide() .radius(d => ((d.root === d.key) ? 0 : (circleRad*(d.rank/5 + 1) + 5)))) .on("tick", ticked) .alpha(1).restart(); if (widthChanged) sim.on("tick", ticked).alpha(1).restart(); // Functions begin here function ticked() { selection.attr('transform', d => { const pad = circleRad * (d.rank/5 + 1) + strokeW; // constrain to svg d.x = Math.min(Math.max(pad, d.x), svgW - pad); d.y = Math.min(Math.max(d.y, pad), svgH - pad); return `translate(${d.x},${d.y})`; }); edge.attr("d", d => { const source = d.source; const target = d.target; return `M${source.x},${source.y} L${ (source.x + target.x) / 2},${ (source.y + target.y) / 2} L${ target.x},${target.y}`; }); } function dragstarted(d) { if (!d3.event.active) sim.alphaTarget(1).restart(); d3.select(this).attr("cursor", "grabbing"); d.fx = d3.event.x; d.fy = d3.event.y; } function dragged(d) { d.fx = d3.event.x; d.fy = d3.event.y; } function dragended(d) { if (!hover && !d3.event.active) sim.alphaTarget(0); d3.select(this).attr("cursor", "grab"); d.fx = null; d.fy = null; } return svg.node(); } else return hideSVG(); }30:Tce3,viewof labels = { if (navigator.userAgent.match('HeadlessChrome')) return ''; const labels = (this && state === "finished" || state === 'random') ? this.value : new UnionFind(0); function inputHandler(div, e) { function makeSpan(index, method) { const size = 32; const isTreeRoot = (labels.roots[index] === index); return ` `; } const ev = e.detail; mutable highlight = ev; const status = div.querySelector('#status'); if (ev.method === 'make') { const made = labels.makeSet(); status.innerHTML = `status ${numNodeText()}: made new set ${makeSpan(made,'make')}`; mutable highlight.nodes = [made]; } else if (ev.method === 'find') { if (ev.hasOwnProperty('nodes')) { const found = labels.find(ev.nodes[0]); status.innerHTML = `status ${numNodeText()}: found ${makeSpan(found,'find')} from ${makeSpan(ev.nodes[0])}`; mutable highlight.nodes = [ev.nodes[0],found]; } else { console.log(`ev missing property nodes: ${ev}`); } } else if (ev.method === 'link') { if (ev.hasOwnProperty('nodes')) { if (typeof labels.roots[ev.nodes[0]] !== "undefined" && typeof labels.roots[ev.nodes[1]] !== "undefined") { labels.link(ev.nodes[0], ev.nodes[1]); status.innerHTML = `status ${numNodeText()}: linked ${makeSpan(ev.nodes[0],'link')} to ${makeSpan(ev.nodes[1],'link')}`; } else { status.innerHTML = `status ${numNodeText()}: failed to link! labels.roots[${ev.nodes[0]}]: ${labels.roots[ev.nodes[0]] }, labels.roots[${ev.nodes[1]}]: ${labels.roots[ev.nodes[1]]}`; } } else { console.log(`ev missing property nodes: ${ev}`); } } else { status.innerHTML = `status ${numNodeText()}: unrecognized method: ${JSON.stringify(ev)}`; } div.querySelector('code').innerHTML = `${formatCode(labels)}`; } function numNodeText() { const l = labels.roots.length; return `(${l} set${l === 1 ? '' : 's'}; see chart)`; } function makeDiv(){ const div = html`

${formatCode(labels)}

status ${numNodeText()}: initialized`; div.addEventListener("input", e => inputHandler(div,e)); return div; } function formatCode(labels) { return JSON.stringify(labels).replace(/,"/g,',
"').replace(/,/g, ', '); } const div = (this && state === "finished") ? this : // avoid reattaching event listener over and over makeDiv(); const status = div.firstChild.nextSibling.nextSibling; div.value = labels; return div; }31:Tafe,controls = { if (navigator.userAgent.match('HeadlessChrome')) return ''; if (state === 'example') { return (this && this.id === 'example') ? this : html`

${delayControl()}`; } else if (state === 'random') { return (this && this.id === 'random') ? this : html`

${delayControl()} ${randomControl(viewof randomProbs)}`; } const disableFindLink = (labels.roots.length === 0 || state !== "finished"); // only allow input if "finished" const buttonMakeSet = html` `; div.value = "example"; // by default, run example const clear = div.firstChild; clear.onclick = (event) => { mutable highlight = ({nodes:[], method:''}); mutable exampleState = 0; div.value = "clear"; div.dispatchEvent(new CustomEvent("input")); }; const example = clear.nextElementSibling; example.onclick = (event) => { if (div.value !== 'example') { div.value = "example"; mutable exampleState = 0; div.dispatchEvent(new CustomEvent("input")); } else { div.value = "finished"; div.dispatchEvent(new CustomEvent("input")); } }; const random = example.nextElementSibling; random.onclick = (event) => { if (div.value !== 'random') { div.value = "random"; div.dispatchEvent(new CustomEvent("input")); } else { div.value = "finished"; div.dispatchEvent(new CustomEvent("input")); } }; div.addEventListener('input', (event) => { if (div.value === 'example') { example.textContent = 'Stop running example'; random.textContent = 'Run random operations'; } else if (div.value === 'random') { example.textContent = 'Re-run example'; random.textContent = 'Stop random operations'; } else if (div.value === 'finished' || div.value === 'clear') { example.textContent = 'Re-run example'; random.textContent = 'Run random operations'; } }); return div; }33:T2410,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; return md`The above is a visualization of the [union-find (or disjoint-set) data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) with "union-by-rank" and "path-compression" as implemented in [the "\`union-find\`" module](https://github.com/mikolalysenko/union-find) by Mikola Lysenko. This first section is an introduction to this data structure with a different flavor than the discussion on Wikipedia; feel free to [skip ahead](#chartSection) if you're already familiar with it! Here's a prototypical problem where organizing your data with a union-find data structure is helpful: suppose you're studying the dynamics of friend groups in a certain country where (1) friendships are only ever created, never broken, and (2) when two people become friends, their respective groups of friends become one. How might you keep track of the groups as they grow and merge together? How might you quickly determine whether two given people are in the same friend group? A first observation is that the friend groups are connected components of the "friendship graph", a [graph (or network)](https://en.wikipedia.org/wiki/Graph_%28discrete_mathematics%29) whose nodes (or vertices) are the individuals and whose links (or edges) are all friendships between them. So really, we're looking for algorithms to label and update connected components of graphs (so, if you prefer, you can think instead about [segmentation of 2D images or 3D scans](https://en.wikipedia.org/wiki/Image_segmentation), or [alias analysis in compiler theory](https://en.wikipedia.org/wiki/Alias_analysis), or [type inference](https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system#Degrees_of_freedom_instantiating_the_rules), or any other situation where stuff gets linked to other stuff and you want to keep track of it as it happens.) Naïvely, you might create an [array](https://en.wikipedia.org/wiki/Array_data_structure) or [list](https://en.wikipedia.org/wiki/List_%28abstract_data_type%29) for each component and then join them when two people from different groups befriend each other. However, when the groups get large, merging arrays (to update the groups) is slow, as is searching lists (to determine what cluster a person is in). Enter the **union-find data structure**! To apply it, associate each person to an element called a "set" in the data structure. Then the "union" and "find" methods will efficiently answer all the questions above. How does it work? Each set has two nonnegative integers, a "parent" and a "rank". In the \`union-find\` module, these are stored in arrays called (confusingly) \`roots\` and (less confusingly) \`ranks\` so that, e.g., the parent of the *j*th set is \`roots[j-1]\` and its rank is \`ranks[j-1]\`. In the graphic above, each set corresponds to a randomly-colored disk, labeled by its index. Sets that are their own parents will be called "roots" in what follows (in ordinary font, not \`code font\`, to distinguish from the poorly-named parent array in this module). Roots are drawn with a special dashed outline. Non-root sets are connected by arrows to their parents. The visualization shows that the sets form [directed trees](https://en.wikipedia.org/wiki/Tree_%28graph_theory%29), rooted precisely at, well, the roots. **If you remember nothing else from this notebook -- remember that the union-find data structure is made up of trees!** These trees (and the underlying data structure) are constructed via the following three operations: - *Make a new set* this adds a new set to the data structure, by appending \`j-1\` to \`roots\` and \`0\` to \`ranks\`. In [code](https://github.com/mikolalysenko/union-find/blob/b0686c58f73e2c84cebdcb1b4f35f75eef168266/index.js#L23): \`\`\`js proto.makeSet = function() { var n = this.roots.length; this.roots.push(n); this.ranks.push(0); return n; } \`\`\` In other words, each new set is initialized as its own parent and with its rank is equal to zero.

The effect of a *Make* operation in the graphic is something from nothing:

- *Find* given an index of some set, this returns the index of the root of its tree. Thus if *Find*(i) = *Find*(j), i and j must be in the same tree. The search procedure is simple: start at the indexed set, and then repeatedly go to the parent; graphically, just "follow the arrows". The [code](https://github.com/mikolalysenko/union-find/blob/b0686c58f73e2c84cebdcb1b4f35f75eef168266/index.js#L30) is straightforward (though I protest again against the fact that the parent array is named \`roots\`): \`\`\`js proto.find = function(x) { var x0 = x var roots = this.roots; while(roots[x] !== x) { x = roots[x] } \`\`\` After the search completes at, say, set \`x\`, each set that was visited is then attached directly to \`x\`. This process, called "path-compression", flattens the tree and makes future *Find* operations faster. \`\`\`js while(roots[x0] !== x) { var y = roots[x0] roots[x0] = x x0 = y } return x; } \`\`\`

A *Find* operation on set 5 returns 6, but also results in both 1 and 5 being reattached to the root 6:

- *Link* (aka *Union*) given two indices, this links the two trees containing those two sets. *Find* operations are first performed to determine the two tree roots. In [code](https://github.com/mikolalysenko/union-find/blob/b0686c58f73e2c84cebdcb1b4f35f75eef168266/index.js#L44): \`\`\`js proto.link = function(x, y) { var xr = this.find(x) , yr = this.find(y); \`\`\` If they are the same, then they were already in the same tree, and no linking is required. \`\`\`js if(xr === yr) { return; } \`\`\` Otherwise, consider the ranks of the two roots. (This is where the "union-by-rank" part of the algorithm starts.) \`\`\`js var ranks = this.ranks , roots = this.roots , xd = ranks[xr] , yd = ranks[yr]; \`\`\` If they differ, the parent of the lower-rank root is set to the larger-rank root. (I remind you again that the \`roots\` array contains references to the parents, not the roots.) \`\`\`js if(xd < yd) { roots[xr] = yr; } else if(yd < xd) { roots[yr] = xr; \`\`\` If the ranks are equal, one of the sets has its rank incremented and then the other set is attached to it. \`\`\`js } else { roots[yr] = xr; ++ranks[xr]; } } \`\`\` Joining the trees at their roots ensures that the data structure always encodes a set of trees (cycles are never formed), and the union-by-rank procedure keeps the trees flat, improving efficiency.

This example *Link* operation was performed on sets 1 and 7 and results in the merging of the trees rooted at 0 and 2:

Now, go ahead and try out these operations using the controls [above](#svg)! Note that only the labels of the sets and the connections between them (i.e. the topology of the graph) in the graphic arise from the data structure discussed here; the force-driven layout is arbitrary and chosen just for aesthetic purposes. For an alternate view (with fewer possibly distracting features): **See also**: [David Galles's JS visualization of disjoint-sets](https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html). Since the algorithm has been engineered to make the trees very flat, the *Find* operations are quick. Similarly, the *Link* operations perform only two *Find* operations and modify \`roots\` and \`ranks\` at two or fewer indices. Indeed, it can be shown that the average time cost per operation is very nearly constant, independent of the total number of sets! For more technical details, see the references in [the Wikipedia article](https://en.wikipedia.org/wiki/Disjoint-set_data_structure). Thus, returning to our friendship application, using this data structure, we can both efficiently keep the friend clusters up-to-date and also quickly query whether two people are in the same cluster, no matter the number of people we wish to track. *A technical side note*: what if you want to keep track of connected components in graphs where both edge additions and deletions are allowed? For example, you might like to study friendship networks without the restriction (1) that friendships, once created are never broken. Well, union-find won't do (it's worth thinking about why!), but it turns out that there do exist fairly efficient algorithms. The keywords are "fully-dynamic graph connectivity algorithms", and one place to start reading might be [these slides by Christian Wulff-Nilsen](https://u.cs.biu.ac.il/~liamr/slides_dynconn.pdf). (I'd love to see a visualization of one of these algorithms!) `}34:T961,chartSection = { if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md`## Grow your own random forests We've seen above a few of the diverse applications that the union-find data structure is handy for, so hopefully you're now convinced that this algorithm works hard and pulls its weight on a variety of jobs. In the rest of this notebook, let's try to get to know union-find on its own terms – what it's like when we let it run freely and grow at its own pace, without being tied to any particular labeling task. Hopefully it's sinking in from the gadget above that the sets in union-find comprise a graph whose components are all trees (such a graph is called a ["forest"](https://en.wikipedia.org/wiki/Tree_%28graph_theory%29), of course). The structure of a union-find forest is fully determined by the sequence of *Make*, *Link* and *Find* operations that is performed. So if we want to understand the possible forests, it's enough to think about the possible sequences of operations. Let's focus on "typical" sequences, by randomly choosing operations and examining the resulting random forests. (Note that these random forests are unrelated to the [random decision forests](https://en.wikipedia.org/wiki/Random_forest) method in machine learning.) **Experiment!** Try playing around with the "Run random operations" button and tuning the relative frequencies of *Link*, *Make* and *Find* operations and comparing what you see [above](#svg) with what you see in the following chart (the displays and controls are linked!). This stacked bar chart shows the number of sets in each tree above over "time", that is, as a function of the number of operations that have been performed, and it can also be switched to display the fraction of sets in each tree. Sets that are isolated roots have been grouped together. ** Question:** The button begins a random walk in the space of operations and so it displays a random sequence of union-find forests. You might be familiar with the fact that [zooming out on long random walks leads to self-similar fractal paths](https://en.wikipedia.org/wiki/Random_walk#Relation_to_Wiener_process). Might these forests also have interesting limiting behavior? How do the distributions of tree sizes / shapes in the forest depend on the relative frequencies as the number of operations performed goes to infinity?`; return div; }35:T7d0,chartButtons = { if (navigator.userAgent.match('HeadlessChrome')) return ''; function updateText() { if (state === 'random') { random.textContent = 'Stop random operations'; } else if (state === 'finished' || state === 'clear') { random.textContent = 'Run random operations'; } } const div = html` Show disks above (slow when number of sets is large)
`; const clear = div.firstChild; clear.onclick = (event) => { mutable highlight = ({nodes:[], method:''}); viewof state.value = "clear"; viewof state.dispatchEvent(new CustomEvent("input")); updateText(); }; const random = clear.nextElementSibling; random.onclick = (event) => { if (state !== 'random') { viewof state.value = "random"; viewof state.dispatchEvent(new CustomEvent("input")); } else { viewof state.value = "finished"; viewof state.dispatchEvent(new CustomEvent("input")); } updateText(); }; const checkbox = div.querySelector('#show'); checkbox.onchange = (event) => { if (checkbox.checked) { mutable show = true; } else { mutable show = false; } }; const radio = div.querySelector('#radioForm'); const rel = div.querySelector('#rel'); radio.onchange = (event) => { if (rel.checked) { mutable chartRel = true; } else { mutable chartRel = false; } }; // defaults updateText(); return div; }36:T962,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md`Tracking random forests step-by-step gives us a direct look at the growth process, but if we're just interested in what very large forests look like, it's more efficient to visualize the final result without tracking each intermediate step. The following gadget draws a random forest using a "circle packing" method implemented by the [\`d3-hierarchy\` library](https://github.com/d3/d3-hierarchy#pack). (The parameters below are independent of the ones chosen above). Each set is drawn as a disk. If the set is not a root, its disk is contained in that of its parent, and thus it also contains its children. This means that a tree in the data structure is represented by its root disk and all the nested disks lying within. You can choose to color the sets / disks either: - by [**depth**](https://en.wikipedia.org/wiki/Tree_%28graph_theory%29#Rooted_tree) (the length of the shortest path to the root), so that roots (which have depth 0) are dark green ${packSVGDepth(0)}, their direct children (depth 1) are light green ${packSVGDepth(1)}, their grandchildren (depth 2) are light brown ${packSVGDepth(2)}, etc. ${packSVGDepth(3)}, etc. ${packSVGDepth(4)}, - or by **index**, so that sets which are created earlier are colored yellow ${packSVGId(0)} and lighter ${packSVGId(0.25)} and sets that are created later ${packSVGId(0.5)} are colored purple ${packSVGId(0.75)} and darker ${packSVGId(1)}. While the actual layout doesn't have any intrinsic significance, it is nice that the packing segregates trees roughly by complexity. If we begin at the perimeter of the graphic and work inwards, we see isolated roots, then trees with one parent and one child, then trees with two children connected to the root, etc., until we get to the center, where the largest and most complex trees are placed. The graphic below can handle much larger forests (up to several million sets) than the ones above (which craps out after a few thousand sets), though be aware that laying out large circle packings can take some time. [On my newish MacBook Pro, it takes roughly 10 seconds to make a picture of a forest arising from 100000 random operations which goes up to 200 seconds for 1 million operations.] You can also disable the packing with the checkbox and just enjoy the statistics and bar charts below.`; return div; }37:T6c9,viewof packing = { const data = ufStratify; const maxId = parseInt(data.id); const L = 20*Math.floor(Math.sqrt(maxId)); const l = Math.min(width, L); if (!showPack) { const div = md`

Packing not computed: see the [checkbox below](#canvasSliders).`; div.value = null; return div; } const scale = l/L; const context = DOM.context2d(l, l); context.clearRect(0, 0, l, l); context.font = `${30*l/width}px serif`; context.textAlign = 'center'; context.fillText(`Packing ${data.children.length} trees...`, l/2, l/2); function draw(nodes) { context.clearRect(0, 0, l, l); context.lineWidth = 1.5*scale; const TWOPI = 2 * Math.PI; context.canvas.value = nodes; context.canvas.data = data; context.canvas.uf = uf; for (const d of nodes) { const frac = parseInt(d.data.id) / maxId; context.fillStyle = (packColorDepth) ? packColorsDepth.fills[d.depth-1] : packColorsId.fills(frac); context.strokeStyle = (packColorDepth) ? packColorsDepth.strokes[d.depth-1] : packColorsId.strokes(frac); context.beginPath(); context.arc(d.x*scale, d.y*scale, d.r*scale, 0, TWOPI); context.fill(); context.stroke(); } context.canvas.dispatchEvent(new CustomEvent('input')); // const t1 = performance.now(); // console.log(t1 - t0); } if (this && this.uf === uf) { draw(this.value); } else { const worker = new Worker(packWorker); invalidation.then(() => worker.terminate()); worker.addEventListener("message", ({data}) => draw(data)); worker.postMessage({data, L, pad:10}); } return context.canvas; }38:T4a4,{ if (!showPack) { return md`Enable the packing to show a download button here.`; } else { const data = viewof packing.data; const maxId = parseInt(data.id); const L = 20*Math.floor(Math.sqrt(maxId)); // second number is roughly the max canvas size in Firefox: // see https://github.com/jhildenbiddle/canvas-size#test-results const l = Math.min(L, 11000); const scale = l/L; const context = DOM.context2d(l, l, 1); context.clearRect(0, 0, l, l); const nodes = packing; context.lineWidth = 1.5*scale; const TWOPI = 2 * Math.PI; for (const d of nodes) { const frac = parseInt(d.data.id) / maxId; context.fillStyle = (packColorDepth) ? packColorsDepth.fills[d.depth-1] : packColorsId.fills(frac); context.strokeStyle = (packColorDepth) ? packColorsDepth.strokes[d.depth-1] : packColorsId.strokes(frac); context.beginPath(); context.arc(d.x*scale, d.y*scale, d.r*scale, 0, TWOPI); context.fill(); context.stroke(); } // console.log('hi!'); return DOM.download(await new Promise(resolve => context.canvas.toBlob(resolve)), 'forest.png', 'Save larger resolution PNG'); } }39:T68f,canvasSliders = { const div = html`

Show packing

Color sets by:
depth
index ${numOpsControl(viewof numOps)} ${randomControl(viewof randomProbs2, false)}`; const button = div.querySelector('#genButton'); const numOpsInput = div.querySelector('.numOpsNumber'); const slider = div.querySelector('.slider'); const checkbox = div.querySelector('#showPack'); const radioDepth = div.querySelector('#colorDepth'); const radioId = div.querySelector('#colorId'); radioDepth.onchange = () => { if (!packColorDepth) { mutable packColorDepth = true; } }; radioId.onchange = () => { if (packColorDepth) { mutable packColorDepth = false; } }; button.onclick = () => { const arr = slider.noUiSlider.get().map(d => d/10000) viewof numOps.value = numOpsInput.value; viewof randomProbs2.value = ({linkProb:arr[0], findProb:arr[1]}); }; checkbox.onchange = (event) => { if (checkbox.checked) { mutable showPack = true; } else { mutable showPack = false; } }; return div; }3a:T1213,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; const numSets = uf.roots.length; const numTrees = his.data.length; function numTreesOfSize(sz) { return his.data.filter(d => d === sz).length; } function numTreesOfHeight(ht) { return heightTrees.filter(d => d === ht).length; } function percentTrees(num) { return `${(100*num/numTrees).toPrecision(3)}%`; } function percentSize(num) { return `${(100*num/numSets).toPrecision(3)}%`; } function numSetsOfDepth(dt) { return depthHisto.filter(d => d === dt).length; } function percentDepth(dt) { return `${(100*numSetsOfDepth(dt)/numSets).toPrecision(3)}%`; } function treeSummary() { let text = `The generated random forest has ${numSets} set` + (numSets !== 1 ? 's' : '') + ` in ${numTrees} ` + (numTrees !== 1 ? 'separate trees' : 'tree') + '. There ' + (numTreesOfSize(1) !== 1 ? 'are' : 'is') + ` ${numTreesOfSize(1)} isolated root` + (numTreesOfSize(1) !== 1 ? 's' : '') + ` (${percentTrees(numTreesOfSize(1))} of the trees)`; let numShown = 1, sz = 1; while (numShown < 6 && sz < his.data[4]) { sz ++; const num = numTreesOfSize(sz); if (num > 0) { numShown ++; text += ', ' + `${num} tree` + (num !== 1 ? 's' : '') + ` of size ${sz} (${percentTrees(num)})`; } } sz ++; let num = numTreesOfSize(sz); while (num === 0 && sz <= his.data[3]) { sz ++; num = numTreesOfSize(sz); } text += `, and ` + `${num} tree` + (num !== 1 ? 's' : '') + ` of size ${sz} (${percentTrees(num)}). `; text += `The largest tree has size ${his.data[0]} (containing ${percentSize(his.data[0])} of the sets)`; if (numTrees === 2) text += ` and the second-largest tree has size ${his.data[1]} (${percentSize(his.data[1])})`; else if (numTrees > 2) text += ` and the second- and third-largest trees have size ${his.data[1]} (${percentSize(his.data[1])}) and ${his.data[2]} (${percentSize(his.data[2])})`; return text + '.'; } function heightSummary() { let text = `We can also look at the [height](https://en.wikipedia.org/wiki/Tree_%28graph_theory%29#Rooted_tree) of each of the trees (the length of the longest directed path in the tree from any set to the root): the aforementioned isolated roots are the trees of height 0. There ${numTreesOfHeight(1) === 1 ? 'is' : 'are'} then `; const maxHt = Math.min(depthNumTicks, 5); if (maxHt === 1) text += 'no trees with height 1 or more'; for (let ht = 1; ht < maxHt; ht++) { text += (ht > 1 ? ', ' : '') + (maxHt > 2 && ht === maxHt - 1 ? 'and ' : '') + `${numTreesOfHeight(ht)} tree` + (numTreesOfHeight(ht) !== 1 ? 's' : '') + ` of height ${ht} (${percentTrees(numTreesOfHeight(ht))})`; } if (maxHt !== depthNumTicks) { const numTreesMaxHt = numTreesOfHeight(depthNumTicks-1); text += `. The maximum height is ${depthNumTicks-1} and there ` + (numTreesMaxHt !== 1 ? 'are' : 'is') + ` ${numTreesMaxHt} tree` + (numTreesMaxHt !== 1 ? 's' : '') + ` of that height (${percentTrees(numTreesMaxHt)})`; } return text + '.'; } function depthSummary() { let text = 'Turning now to the depths of each of the sets, there ' + (numSetsOfDepth(0) !== 1 ? 'are' : 'is') + ` ${numSetsOfDepth(0)} root` + (numSetsOfDepth(0) !== 1 ? 's' : '') + ` (${percentDepth(0)} of the sets)`; const maxDt = Math.min(depthNumTicks, 5); for (let dt = 1; dt < maxDt; dt++) { text += ', ' + (dt === maxDt - 1 ? 'and ' : '') + `${numSetsOfDepth(dt)} set` + (numSetsOfDepth(dt) !== 1 ? 's' : '') + ` of depth ${dt} (${percentDepth(dt)})`; } if (maxDt !== depthNumTicks) { const numSetsMaxDt = numSetsOfDepth(depthNumTicks-1); text += `. The maximum depth is ${depthNumTicks-1} and there ` + (numSetsMaxDt !== 1 ? 'are' : 'is') + ` ${numSetsMaxDt} set` + (numSetsMaxDt !== 1 ? 's' : '') + ` of that depth (${percentDepth(depthNumTicks-1)})`; } return text + '.'; } return md`${treeSummary()} ${heightSummary()} ${depthSummary()} The frequencies of tree sizes are plotted in the following (log-scaled) histogram, and the two insets show the frequencies of tree heights and set depths. Since the largest tree is frequently an extreme outlier, it is included in the main histogram below only if its size is at most twice the size of the second-largest tree.`; }3b:T16a5,secStates = { if (navigator.userAgent.match('HeadlessChrome')) return ''; return md` ## Linking union-find to network science My initial goal with this notebook was just to make a visualization of the union-find data structure which would hopefully shed some light on how it works. But then, on a whim, I created the "random operations" button. I couldn't resist playing around with the forests and so I ended up doing some reading and found another story I wanted to share. Read on if you're curious about how you might make sense of the colorful pictures above or if you've ever been fascinated by [emergent](https://en.wikipedia.org/wiki/Emergence) phenomena! ### States of matter Here's one observation you might have made about the random forests: though there always seem to be a ton of isolated sets and relatively small trees, for some choices of parameters, there's also one very large ("giant") tree. Furthermore, it's extremely rare to see a forest with, say, 500 or more sets that has two disjoint trees which each contain more than 5% of the sets. Let's indulge in some gratuitous handwaving here and talk about our forests at different values of *Make/Link* as if they were samples of a physical substance at varying temperatures. If you've not studied statistical mechanics, it may seem odd to compare the output of some abstract-seeming random algorithm to chunks of matter, but in fact physicists frequently do the reverse and study changes of state like melting, boiling, or even superconductivity by generating random realizations of simple combinatorial structures and seeing how they vary as various probabilities change. It would be easy to dismiss all that work as late-stage "[spherical cow](https://en.wikipedia.org/wiki/Spherical_cow)" syndrome, except for the magic of ["universality"](https://en.wikipedia.org/wiki/Universality_%28dynamical_systems%29) – under certain circumstances (when the toy model and the true system lie in the same "universality class") we can recover exact results about real-world systems by running some silly random graph algorithms! So, with that philosophy in the background, let's continue. Just as water can be solid ice, liquid, or steam, depending on the temperature and pressure, I'll describe here the two different "phases" of our random forests; which one appears depends on the ratio of *Make/Link* frequencies (terminology is nonstandard; references and discussion await in the next section!): * **Vapor phase**: When *Make/Link* is greater than 8, most of the sets are isolated and the trees are all small. Intuitively, when many more *Make*s are occurring than *Link*s, the most likely targets for a random *Link* event are two isolated sets, so it's unlikely for any one tree to get large relative to the size of the others. While the typical sizes of the constituent trees vary as *Make/Link* changes, this and other "large-scale" properties of the forests in this regime change smoothly. This is analogous to how the density of a gas might vary with temperature or pressure while remaining a gas.

This is an image from a sample run with *Make/Link*=18.7; the inset shows the forest after 362 random operations, when it has 268 sets. Click below to show the fraction of sets in each tree over time:

${toggleFig('https://i.imgur.com/NcJ9ZH4.png', 'https://i.imgur.com/Si4AJIt.png')}

This is an image of a larger forest (1 million random operations) with *Make/Link*=9 and *Find*=0 and its tree size histogram. It has 919687 sets in 839376 trees, of which 783022 are isolated roots, 43060 are size 2, and 8356 are of size 3. The largest tree is size 37 and the second-largest is size 32:

* **Droplet phase**: When *Make/Link* is less than 8, then there is almost always one "giant" tree which is appreciably larger than the rest of the other trees and which contains a constant fraction of the sets. To stretch the water analogy, the giant is like a condensing liquid droplet suspended in a "gas" of isolated roots and other small trees. The size of this giant depends on *Make/Link* (wait for [Figure 1 of the reference [CHKNS01] below](#scatterFigCell1) if you're interested in how precisely it varies!): for values near 8, that fraction will be tiny and as *Make/Link* decreases towards zero, the fraction approaches 1. Because of its dominant size, the giant is the most likely target for *Link*s (you might say it "attracts" and absorbs other sets and trees over time) and so it grows steadily as more random operations occur.

This is an image from a sample run with *Make/Link*=1.21; the inset shows the forest after 372 random operations, when it has 151 sets. Click below to show the fraction of sets in each tree over time:

${toggleFig('https://i.imgur.com/5NPVCdk.png', 'https://i.imgur.com/gJ2JRnV.png')}

This is an image of a larger forest (1 million random operations) with *Make/Link*=5.6667 and *Find*=0 and its tree size histogram. It has 850492 sets in 701001 trees, of which 629500 are isolated roots, 47909 are size 2, and 12133 are of size 3. The largest tree is size 9055 and the second-largest is size 364:

* **Phase transition**: When *Make/Link* is equal to 8, something special happens. It's not visually obvious, but the forests undergo a [phase transition](https://en.wikipedia.org/wiki/Phase_transition). However, in fact there are certain quantities related to component sizes that are singular at this point (we'll see an example in [Figure 3 below](#scatterFigCell3)). `; }3c:T1185,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md`### Making contact with the CHKNS model You might be feeling skeptical: the "vapor" and "droplet" phases may seem totally arbitrary – couldn't there be a continuum of behaviors between "gas-like" forests and forests with a giant? And what's up with this magic value *Make/Link* = 8 separating the two phases? In this section, I'll try to explain some of this. I apologize for failing to keep the exposition from becoming more technical here and in the rest of this notebook. If you skim or skip this, you'll just miss two more demos ([reproducing figures from a paper](#scatterFigCell1) and ["pixel plots"](#adjMatSlider)) and some pretty math and network science. The results I sketched in the last section are not my own (though the vapor and droplet names are! These phases are usually called "subcritical" and "supercritical", respectively). Indeed, after my first investigations on the random forests above, I tried the very creative Google search "random graph growth process" and struck immediate gold. The book _Random Graph Dynamics_ by Rick Durrett [D06] led me to the memorably titled "Are randomly grown graphs really random?" by Duncan S. Callaway, John E. Hopcroft, Jon M. Kleinberg, M. E. J. Newman and Steven H. Strogatz [CHKNS01] and several other enlightening papers (bracketed references are listed in the [Bibliography](#bibliography)) that studied models that are very closely related to our forests. [CHKNS01] introduced the following growing random graph process: - Start with an empty graph at time zero, - At each timestep: - add one vertex to the graph, and - with probability ${tex`\delta`}, choose two random vertices and link them with an edge. While this has a clear resemblance to the random union-find forests we've been looking at above, the edge addition procedure is also rather different. For one, the resulting graph is not guaranteed to consist of trees. Secondly, we can't ever have two edges added in a row; every edge addition is followed by a vertex addition. It turns out that both of these differences are less important than you might think. The first issue is more serious. At its core is the fact that a *Link* operation is never a simple edge-addition unless you happen to apply it on two roots. We will have to make some sacrifices here to proceed. If we only measure the number of vertices in each of the connected components of the graphs generated by the two models, the *Link* operations that are used to grow the random forests and the random edge additions in the CHKNS model look the same: - Consider first the random union-find forests. If *Link* is applied to two sets that are not already in the same tree, the net effect is to take two trees, say, of size *m* and *n* and create one tree of size *m+n*. If it is applied to two sets that are already in the same tree, the edges in the tree might be rearranged (due to the *Find* operations), but the number of sets in that tree is unaffected. - Now consider the growing random graphs. If we add an edge between two vertices in different components, say, of size *m* and *n*, the two components are joined into one of size *m+n*, and if we add an edge between two vertices in the same component, though a new cycle is formed in that component, the number of vertices in that component remains the same. Thus in the rest of this section and beyond we will only consider the **sizes** of the trees / subgraphs and not their "shapes", so that the *Link* / edge-addition operations in the two models are indistinguishable. For this reason we can also neglect the *Find* operations for now. Turning to the second issue, note that the probability ${tex`\delta`} is essentially the expected number of edges per vertex in a CHKNS graph. The expected number of edges per vertex in a random union-find forest is the probability of *Link* divided by the probability of *Make*, which is just the reciprocal of *Make/Link*. Apropos of nothing but a gut feeling that there is order to be found in the universe, let's boldly take Figures 1 and 3 from [CHKNS01] and try to reproduce them with random union-find forests. Read the caption to Figure 1 first, and then click either of the "simulate" buttons! (The quantity ${tex`g'(1)`} plotted in Figure 3 is related to the average size of the component containing a random vertex and will be explained later.) `; return div; }3d:T726,scatterFigCell1 = { if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = html`

`; const HEIGHT = 550*798/776; const figW = width > 550 ? 550 : width; const figH = width > 550 ? HEIGHT : width*798/776; const figSel = d3.select(div) .select('#overlayCHKNSfig1') .append('svg') .attr('width', figW) .attr('height', figH) .attr('viewBox', `0 0 550 ${HEIGHT}`) .attr('id', 'scatterSVG1'); const img = figSel.append('image') .attr('xlink:href', 'https://i.imgur.com/WKIChDZ.png') .attr('width', 550) .attr('height', HEIGHT); const opaqueMask1 = figSel.append('g') .classed('opaque', true) .attr('fill', 'white'); const leftRect1 = opaqueMask1.append('rect') .attr('x', 30) .attr('y', 30) .attr('width', 62) .attr('height', 240); const botRect1 = opaqueMask1.append('rect') .attr('x', 75) .attr('y', 293) .attr('width', 450) .attr('height', 55); const transpMask1 = figSel.append('g') .classed('transp', true) .attr('fill', 'white'); const topRect1 = transpMask1.append('rect') .attr('x', 95) .attr('y', 15) .attr('width', 110) .attr('height', 20); const botRect12 = transpMask1.append('rect') .attr('x', 435) .attr('y', 270) .attr('width', 80) .attr('height', 15); const button = div.querySelector('input'); button.onclick = () => { if (!runLoop) { mutable runLoop = true; button.value = 'Stop simulating!'; } else { mutable runLoop = false; button.value = 'Click to simulate!'; } }; return div; }3e:T71f,scatterFigCell3 = { if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = html`

`; const HEIGHT = 443; const figW = width > 550 ? 550 : width; const figH = width > 550 ? HEIGHT : width*443/550; const figSel = d3.select(div) .select('#overlayCHKNSfig3') .append('svg') .attr('width', figW) .attr('height', figH) .attr('viewBox', `0 0 550 ${HEIGHT}`) .attr('id', 'scatterSVG3'); const img = figSel.append('image') .attr('xlink:href', 'https://i.imgur.com/uU0CXRu.png') .attr('width', 550) .attr('height', HEIGHT); const opaqueMask3 = figSel.append('g') .classed('opaque', true) .attr('fill', 'white'); const leftRect3 = opaqueMask3.append('rect') .attr('x', 34) .attr('y', 0) .attr('width', 65) .attr('height', 300); const botRect3 = opaqueMask3.append('rect') .attr('x', 75) .attr('y', 280) .attr('width', 450) .attr('height', 55); const transpMask3 = figSel.append('g') .classed('transp', true) .attr('fill', 'white'); const topRect3 = transpMask3.append('rect') .attr('x', 103) .attr('y', 10) .attr('width', 25) .attr('height', 18); const botRect32 = transpMask3.append('rect') .attr('x', 436) .attr('y', 265) .attr('width', 75) .attr('height', 13); const button = div.querySelector('input'); button.onclick = () => { if (!runLoop) { mutable runLoop = true; button.value = 'Stop simulating!'; } else { mutable runLoop = false; button.value = 'Click to simulate!'; } }; return div; }3f:T615,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md`After clicking, you should see some data points being overlaid on the figures. While you wait, note that the simulation performed here is on much smaller graphs than in the original work: the forests being analyzed are generated by running only 20000 random operations, except in the interval ${tex`0.1\leq\delta\leq0.3`} where 500000 operations are used. These random operations are split between *Make* and *Link* with ${tex`\delta =`} *Link/Make* sampled at intervals of 1/50 between 0 and 1, and we generate only 5 forests at each value of ${tex`\delta`} – [feel free to change these below](#scatterComments). When the simulation finishes (after just a minute or two, hopefully!), the points generated by the simulation should all be fairly close to the data points from [CHKNS01]. There is a bit more scatter since the system sizes are smaller and the random forests are further from their limiting behavior, particularly visible in Figure 3 in the interval ${tex`0.1\leq\delta\leq0.3`} where something seems to be happening in the original figure as well. Nonetheless, the data suggests that at a fixed ratio of edges to vertices, in the limit where the number of vertices is large, the random union-find forests should be the same as CHKNS randomly grown graphs, at least as far as quantities related to their component sizes are concerned. Thus it's reasonable to guess that the properties of the CHKNS model also hold for our random forests! `; return div; }40:Tf60,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md`### Interlude: network models in network science Let's take a break and return to the title of [CHKNS01]: "Are randomly grown graphs really random?" This gives us an opportunity to better situate our questions in the broader field of [network science](https://en.wikipedia.org/wiki/Network_science). So far as I can tell, network scientists aim to shed light on any and all networks in the universe, be they physical, biochemical, social, political, ... etc. Thus it's no surprise that there's an unbelievably diverse zoo of random graph models – the world is complex! The two models that are most relevant to us here are the [Erdős–Rényi model](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) and the [Barabási–Albert model](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model). These two are both among the most well-studied models and exemplify the principle of emergence: rich behavior from simple rules. Here's a quick reminder of how you might construct each of them: - you can generate an Erdős–Rényi random graph (traditionally denoted *G(n,m)*) by starting out with *n* vertices, and then adding *m* random edges, and - you can grow a Barabási–Albert graph by starting with some seed graph of size ${tex`m_0`} and adding one vertex in each timestep which is connected to ${tex`m\leq m_0`} random vertices. The vertices are not chosen with equal probability, but rather with probability proportional to their degree (number of edges already connected). The former was first studied in the late 1950's and is famous for *the* phase transition: in the limit as ${tex`n\rightarrow\infty`}, for almost all *G(n,m)*, when ${tex`\frac{m}{n} < \frac{1}{2}`}, all components of *G(n,m)* are tiny and when ${tex`\frac{m}{n} >\frac{1}{2}`} there is a "giant component" with size proportional to *n*. (Sound familiar?) The latter was introduced in 1999 as a simple model of a growing graph which captured some important features of real-world networks. B-A graphs are ["scale-free"](https://en.wikipedia.org/wiki/Scale-free_network), and one consequence is that they exhibit vertices which are extremely highly connected ("hubs"), in contrast to the E-R graphs. **See also:** Dirk Brockmann's *Complexity Explorables*: [The Blob](http://www.complexity-explorables.org/explorables/giant/) and [Knitworks](http://www.complexity-explorables.org/explorables/networks/), which beautifully illustrate these two models. The former discusses the giant component in both the Erdős–Rényi and Barabási–Albert models and and the latter is an intro to preferential attachment growth models. The CHKNS model can be viewed as lying "between" these two in some sense. It's a "dynamic" model like B-A, but doesn't have the "preferential attachment" feature (where edges are more likely to be added to more popular vertices). Instead, the edges are added uniformly randomly like those in the E-R model. So, in the title, *randomly grown graphs* refers to their CHKNS model and *random* in "really random" refers to random graph models such as E-R which are not grown vertex-by-vertex. In their words: > "As in these studies [of models like B-A], we consider the role of system growth on network structure. However, our purpose is somewhat different. Rather than seeking to explain an observed feature of real-world networks [...], we focus on a minimal model of network growth and compare its properties to those of the familiar [E-R] random graph. We do not claim that our model is an accurate reflection of any particular real-world system, but we find that studying a model that exhibits network growth in the absence of other complicating features leads to several useful insights. In addition, the model turns out to have some interesting mathematical properties, as we will show." `; return div; }41:T1bac,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md`### The CHKNS phase transition After that appetizer, let's turn back to what CHKNS have to say about their model and how similar it is to the E-R model. In fact, CHKNS do not compare their model directly to the E-R model since the degree distributions (histogram of the number of neighbors of each vertex) differ in the two models. However, the model they use instead is in some sense just E-R with the minimal change necessary to get the desired vertex degree distribution, and is generated by the [configuration model](https://en.wikipedia.org/wiki/Configuration_model). Figure 2 of [CHKNS01] takes the giant component size data from [Figure 1](#scatterFigCell1) and compares it to an analytical prediction (the solid line, more on this later) as well as the giant component sizes from the just-described static model:

The circular data points are the same as the ones in Fig. 1. The square data points arise from the E-R-like configuration model of a static random graph.

What does this figure tell us? At low ${tex`\delta`}, neither model has a giant component (the giant component size seems to be 0 up to some point). These are the subcritical phases of the two models (what I called the "vapor phase" earlier). For the CHKNS model, the trend of the (circular) data points smoothly increases after some point (we'll see later that it is ${tex`\delta = 1/8`}). For the static model, there's a clearly visible sharp corner at ${tex`\delta = 1/4`}. These are the supercritical phases. Leaving aside the fact that the critical values of ${tex`\delta`} differ, the more significant difference is the smooth increase versus corner behavior which reflect the initial rate of growth of the giant component – for the static model, the size fraction of the giant component grows linearly once it appears, and for the CHKNS model, the giant component arises rather more slowly. Just how slowly will be discussed at the end of this section. However, we can already see that the answer to the titular question of [CHKNS01] is "No" ([perhaps unsurprisingly](https://en.wikipedia.org/wiki/Betteridge%27s_law_of_headlines)). In their words: > "In a certain sense, therefore, it seems that a randomly grown network is not really random." In the rest of this section (warning: equations ahead!) we look in some more detail at the phase transition, in particular what happens at ${tex`\delta = 1/8`} (or *Make/Link* = 8). Along the way, a long-overdue explanation of Figure 3 is provided. CHKNS first derive a differential equation for a [generating function](https://en.wikipedia.org/wiki/Generating_function) ${tex`g(x)`} related to the component sizes of the graph. Specifically, ${tex.block`g(x) = \sum_{k=1}^\infty b_kx^k,`} where ${tex`b_k`} is the probability that a randomly chosen vertex belongs to a finite (= non-giant) component with exactly ${tex`k`} vertices. Since ${tex`g(1)`} is the probability that a randomly chosen vertex belongs to some non-giant component, the quantity ${tex`S = 1-g(1)`} is the fraction of vertices in the giant component. CHKNS argue that (in the limit when the number of vertices ${tex`n\rightarrow\infty`}), ${tex`g(x)`} satisfies the following nonlinear differential equation: ${tex.block`\frac{dg}{dx} = \frac{1}{2\delta}\left(\frac{1-g/x}{1-g}\right),`} They integrate this numerically (with initial condition ${tex`(x,g) = (x_0,x_0/(1+2\delta))`} for small ${tex`x_0`}) to get the solid line through the circular data points in Fig. 2. Suppose we choose a random vertex outside the giant. Then let ${tex`\langle s\rangle`} be the expected size of the component that it belongs to. Due to the magic of generating functions, we can write an expression for ${tex`\langle s\rangle`} in terms of ${tex`g`}: ${tex.block`\langle s\rangle = \frac{g'(1)}{g(1)},`} (here ${tex`g'(1) = \frac{dg}{dx}`} evaluated at *x=1*); this equation is used to compute the data points for ${tex`g'(1)`} in [Fig. 3](#scatterFigCell3). CHKNS also derive the following expression for ${tex`g'(1)`} in their Equation 18: ${tex.block`g'(1) = \begin{cases} (1-\sqrt{1-8\delta})/4\delta, & \delta\leq 1/8,\\ 1/(2\delta), & \delta>1/8, \end{cases}`} and this yields the solid lines in Fig. 3. Since ${tex`\lim_{\delta\nearrow 1/8}g'(1)=2`} and ${tex`\lim_{\delta\searrow 1/8}g'(1)=4`}, this explains the discontinuity in that figure at ${tex`\delta_c = 1/8`}. Indeed, based on this, CHKNS postulated 1/8 as the location of the critical point between graphs with no giant component (subcritical) and graphs with a giant component (supercritical). Thus ${tex`\delta_c=1/8`} and hence *Make/Link*=8 is thus also presumably where the phase transition between random forests in the subcritical (vapor) phase and supercritical (droplet) phase occurs as well. With this value in hand, CHKNS then took a more careful look at their numerical solution in Fig. 2 for the size *S* of the giant component near ${tex`\delta_c = 1/8`} (see Fig. 4 of [CHKNS01]) and found a great fit to their data using a very unusual asymptotic form: ${tex.block`S(\delta) \sim \exp\left(\alpha /(\delta-\delta_c)^\beta\right),`} where ${tex`\alpha\approx -1.13`} and ${tex`\beta\approx0.499`}. Naturally, they guessed that ${tex`\beta`} was exactly 1/2. Later, S.N. Dorogovtsev, J.F.F. Mendes, and A.N. Samukhin [DMS01] gave a derivation for the asymptotic ${tex`S(\delta) \sim \exp\left(-\frac{\pi}{2\sqrt{2}}(\delta-\delta_c)^{-1/2}\right)`}, confirming this guess. Contrast this with the E-R model, where the corresponding asymptotic behavior for the size of the giant component near the transition is the much simpler linear function ${tex`S(\delta)\sim \delta-\delta_c^{ER}`}. What's unusual about the asymptotic form for the CHKNS model is that all of the derivatives to ${tex`S(\delta)`} at ${tex`\delta = \delta_c`} are equal to zero, making it a function which grows slower than any power of ${tex`\delta-\delta_c`}. When it is joined to the constant zero function for ${tex`\delta < \delta_c`} one obtains an example of a [non-analytic smooth function](https://en.wikipedia.org/wiki/Non-analytic_smooth_function). This is a signature of the rather rare class of "infinite-order" phase transitions (see [the "very technical open question" section](#veryTechnical) at the end for more commentary on this). *Pedantic aside*: While these results are very nice and fit the data quite well, they are not rigorous. Various unjustified assumptions have been made along the way (see [D03] for an entertaining take involving "Theoems" and "Poofs"). Fortunately, these assumptions are justifiable, though much ink had to be spilled in dotting all the i's and crossing all the t's (in addition to [D03] and [D06], see [BJR04], [BJR07], and [JR12]). The payoff to all that work is a much more nuanced understanding, and we will see some hints of this in the next section. `; return div; }42:Tee7,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md`### Details don't matter: more models and pixel pictures Recall that we're still just hypothesizing that the CHKNS model and random union-find forests behave the same here. Let's go yet further out on a limb and guess that at fixed edge to vertex ratio, the fine details of how the random addition of edges and vertices occurs shouldn't matter. Here are a few examples of randomly grown graph models that we might hope will exhibit the same phase transition. In each of the following, begin with an empty graph and at the *k*th timestep, add one vertex and then: - add a random edge with probability ${tex`\delta`}, i.e. draw a random number between 0 and 1 and if it is less than ${tex`\delta`}, choose two vertices uniformly at random as endpoints for the new edge (the CHKNS model), or - add a [Poisson distributed](https://en.wikipedia.org/wiki/Poisson_distribution) number of random edges with mean ${tex`\delta`} (Durrett's "model #1" [D03]), or - add every possible edge with probability ${tex`\delta/\binom{k}{2}`} (equivalent to adding a [binomially distributed](https://en.wikipedia.org/wiki/Binomial_distribution) number of random edges) (mentioned in §16.3 of [BJR07])... We can reformulate our random union-find forests in these terms too! Suppose we perform vertex-addition and edge-addition operations with probabilities 1-*p* and *p*, where ${tex`p=\frac{\delta}{1+\delta}`}. This is equivalent to adding a [geometrically distributed](https://en.wikipedia.org/wiki/Geometric_distribution) number of random edges at each timestep. The good news is that in the limit of large *k*, all these random graphs indeed behave the same, at least if we look at quantities such as the expected size of the largest component. This follows from the work of Bollobás, Janson and Riordan in [BJR04] (§11) and [BJR07] (§16.3). The bad news is that I can only vaguely hint at the ideas behind their results ([BJR07] is 120 pages long!). One key idea is to look at the [adjacency matrices](https://en.wikipedia.org/wiki/Adjacency_matrix) of the random graphs created from these models as the number of operations gets large. For a graph with *n* vertices, its adjacency matrix is an symmetric ${tex`n\times n`} matrix where each entry (*i*, *j*) is 1 if vertices *i* and *j* are connected by an edge and 0 otherwise. We can visualize these matrices by drawing them as ${tex`n\times n`} binary images, where 1's are colored black and 0's are colored white. What might we expect when *n* gets large? Do these random pixel pictures have an interesting limit as *n* goes to infinity? To answer this question, we should first rescale the pictures so that they all have the same size, so let's scale all our images so that they are, say, ${tex`250 \times 250`}. Each pixel of a rescaled image will be the average of the data from each ${tex`(n/250)\times(n/250)`} square of the original image. It's natural to make the rescaled image a grayscale one, with the pixel intensities proportional to the number of original pixels in that region that were dark. In each of the models above, the average number of edges in an *n*-vertex graph is ${tex`\delta n`}. So the ratio of black pixels to white ones in the entire ${tex`n\times n`} adjacency matrix is roughly ${tex`\frac{\delta}{n}`}. As *n* gets large, this fraction goes to zero. So from this point of view, the rescaled images all approach a blank canvas. This is indeed *a* limit of the adjacency matrices, but not a very interesting one. To remedy this, when we compute the grayscale values, we weight the pixels by a factor proportional to *n* so that the average darkness of the rescaled images is constant. If we do this, we see the following: `; return div; }43:T46d,adjMatSlider = { const div = html`

In the pictures below, the (0,0)th entry of the matrix is at the top left (i.e. we're using "computer graphics coordinates"). Left: "Pixel plot" of the adjacency matrix of a random union-find forest generated from ${adjMatNumOps} random *Make* and *Link* operations with Make/Link = 1/8. Right: a density plot of the continuous "kernel" function ${tex`\kappa(x,y) = \frac{1}{4}\left(\frac{1}{\min(x,y)} - 1\right)`} in the unit square (${tex`0< x \leq 1`} and ${tex`0< y\leq 1`}).

${adjMatCell} ${drawKer1(1/50, 250)}

${numOpsControl(viewof adjMatNumOps)}`; const button = div.querySelector('#genButton'); const numOpsInput = div.querySelector('.numOpsNumber'); button.onclick = () => { viewof adjMatNumOps.value = numOpsInput.value; }; return div; }44:T8b1,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md` On the right, we show an image of the limiting continuous function ${tex`\kappa`} that the rescaled adjacency matrices of CHKNS random graphs approach (called a ["kernel"](https://en.wikipedia.org/wiki/Integral_transform#General_form) in [BJR07]). In fact, it is not hard to show (at least heuristically) with some algebra that this same function is the limit for the adjacency matrices of all of the above models. So, in very rough terms, the papers of Durrett and Bollobás, Janson and Riordan show that properties of this kernel determine the nature of the giant component phase transition in the random graph models, thus putting (most of) the results of [CHKNS01] and [DMS01] on solid ground. These ideas are very closely related to the notion of [graphons / graph limits](https://en.wikipedia.org/wiki/Graphon); another short explanation is [Glasscock's AMS Notices article "What is a Graphon?"](http://www.ams.org/notices/201501/rnoti-p46.pdf). Note though that most of the discussion there is on dense graphs, where the number of edges is proportional to ${tex`n^2`}; these correspond to pixel pictures which converge without having to reweight the pixels. "Sparse" random graphs like ours (where the number of edges is proportinal to *n*) are apparently harder to study. That's enough about the math for now. Let's get back to the pictures! Note that the pixel plots show a gradient from dark in the top left to white in the bottom right. This is because the sets created early on tend to have more edges between them (there are fewer choices when selecting a random edge). This is also visible in the pattern of shading in [the circle-packing graphic](#packing) when coloring sets by index:

The following image is of a random forest generated from ~134000 operations at *Make/Link* = 4.7504 with the sets colored by index. Note that the larger trees tend to be colored lighter overall, meaning that their constituent sets have lower indices (were created earlier in the growth process).

`; return div; }45:Ta14,{ if (navigator.userAgent.match('HeadlessChrome')) return ''; return md` ## Conclusion and open (?) questions ## In this second part of the notebook, I've tried to sketch a few areas of math and physics that one is led to when contemplating the rich behavior of the random union-find algorithm. Thanks for reading so far, and I hope you were intrigued enough by the questions we considered to forgive the omissions and tangents along the way to their answers! It's only appropriate for a curiosity-driven notebook to end with yet more questions, so here's an open-ended one to start us off: > What does a random realization of your favorite data structure or algorithm look like? For some ideas, you might look into books like ["The Nature of Computation"](http://www.nature-of-computation.org/) by Mertens and Moore. Next, some loose ends: > What is the average [depth](https://en.wikipedia.org/wiki/Tree_%28graph_theory%29#Rooted_tree) of the trees generated with various frequencies of *Make*, *Link* and *Find*? More generally, what else can we say about the "shapes" of the trees? One of the simplifications we made earlier was to only consider the *sizes* of trees so that we could apply results from the CHKNS model; this also let us ignore *Find* operations. Nonetheless, the "shape" of the typical tree is still interesting and as mentioned at the end of the first part, has consequences for the efficiency of various operations. Because the operations on the union-find data structure continually remodel the trees to get shorter, it's apparent that they should be more like [star graphs](https://en.wikipedia.org/wiki/Star_%28graph_theory%29) rather than tall and thin trees with long paths of edges and little branching. One could look at this quantitatively by studying the average depth or the average [indegree](https://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) of the sets as a function of the frequencies. Of course, as more *Find* operations occur, the trees should get flatter, but it's not clear to me what the functional dependence is. The ultimate dream would be to get a detailed characterization of the limiting trees at a level of detail similar to what's known for the E-R model, see e.g. [this paper of L. Addario-Berry, N. Broutin and C. Goldschmidt](https://arxiv.org/abs/0908.3629). Here's another related question: > How is the phase transition in the sizes of the trees reflected in the shapes? How does the shape of the giant differ from that of the "small" trees, and how does it change with *Make/Link*? `; }46:Td03,veryTechnical = { if (navigator.userAgent.match('HeadlessChrome')) return ''; const div = md`### Appendix: a very technical open question As pointed out in [CHKNS01], the infinite-order phase transition bears a mysterious resemblance to the [Berezinskii-Kosterlitz-Thouless](https://en.wikipedia.org/wiki/Kosterlitz%E2%80%93Thouless_transition) transition ([Kosterlitz & Thouless were awarded the 2016 Nobel Physics Prize for discovering this!](https://www.nobelprize.org/prizes/physics/2016/summary/)), which was originally discovered in the context of the 2D [XY model](https://en.wikipedia.org/wiki/Classical_XY_model). In that model system, there's a 2D rotor at every point in the plane, which prefer to be aligned locally but are affected by temperature-driven fluctuations. The point is this: both the XY model at the BKT transition and the CHKNS model at ${tex`\delta=1/8`} have a very unusual essential singularity of the form ${tex`\exp(a\delta^{-1/2})`} in some of their macroscopic properties at their transition points (for the XY model, consider the specific heat and take ${tex`\delta=|T-T_c|`}). There's more – the intuitive picture for the XY model that I was taught was that at low temperatures, the correlations between rotor directions at two points decay like a power-law where the exponent depends on the temperature (quasi-long-range order!). When the temperature reaches the critical point, there is a proliferation of defect pairs ("vortices" and "anti-vortices") and above this point the correlations decay exponentially (short-range order!). In the CHKNS model, it turns out that in the subcritical (${tex`\delta<1/8`}) phase, ${tex`b_k`} (the probability that a random vertex is in a component of size *k*) decays like a power-law in *k* (where the exponent depends on ${tex`\delta`}) and in the supercritical (${tex`\delta<1/8`}) phase, ${tex`b_k`} decays exponentially (see [DMS01], [D03] and [BJR04]). All of this suggests (to optimists who believe that there's order in the universe) that there should be some deep connection between these two very different models. However, the parallels above based on functional form are more subtle than one might think. In fact, one might have expected the situation with power-law and exponential decays in the previous paragraph to be flipped, since in the usual analogy between percolation-type models (CHKNS) and statistical mechanical "spin" models (XY), the phase with a giant component corresponds to the low-temperature phase. And this is of course ignoring the real elephant in the room which is that the 2D XY model is, well, two-dimensional, and the CHKNS model doesn't seem to have any dimensionality to it at all (except perhaps for the time dimension?). There seem to be a handful more papers discussing statistical mechanical models of or on growing random graphs that exhibit similar behavior (one noteworthy one might be the paper of Bauer and Bernard [BB03] which invokes universality to give some nice scaling arguments; you can find more if you search the term "inverted Berezinskii-Kosterlitz-Thouless"), and all of them note this strange coincidence. So, the open problem is: > Is there some clever "duality" mapping between (variants of?) the 2D XY model and the CHKNS model that **explains** all this? `; return div; }47:T8ee,bibliography = { if (navigator.userAgent.match('HeadlessChrome')) return ''; return md`### Bibliography: [BB03] Michel Bauer and Denis Bernard, [A simple asymmetric evolving random network](https://doi.org/10.1023/A:1022842013935). J. Stat. Phys. 111: 703-737 (2003), ([arXiv:cond-mat/0203232](https://arxiv.org/abs/cond-mat/0203232)). [BJR04] Béla Bollobás, Svante Janson, Oliver Riordan, [The phase transition in the uniformly grown random graph has infinite order](https://doi.org/10.1002/rsa.20041). Random Struct. Alg. 26: 1-36 (2004). [BJR07] Béla Bollobás, Svante Janson, Oliver Riordan, [The phase transition in inhomogeneous random graphs](https://doi.org/10.1002/rsa.20168). Random Struct. Alg. 31: 3-122 (2007), ([arXiv:math/0504589](https://arxiv.org/abs/math/0504589)). [CHKNS01] Duncan S. Callaway, John E. Hopcroft, Jon M. Kleinberg, M. E. J. Newman, Steven H. Strogatz, [Are randomly grown graphs really random?](https://doi.org/10.1103/PhysRevE.64.041902) ([pdf on author's site](https://static.squarespace.com/static/5436e695e4b07f1e91b30155/t/544526bee4b01431efea25c6/1413818046784/are-randomly-grown-graphs-really-random.pdf)) Phys. Rev. E 64, 041902 (2001), ([arXiv:cond-mat/0104546](https://arxiv.org/abs/cond-mat/0104546)). [DMS01] S.N. Dorogovtsev, J.F.F. Mendes, A.N. Samukhin, [Anomalous percolation properties of growing networks](https://doi.org/10.1103/PhysRevE.64.066110). Phys. Rev. E 64, 066110 (2001), ([arXiv:cond-mat/0106141](https://arxiv.org/abs/cond-mat/0106141)). [D03] Rick Durrett, [Rigorous Result for the CHKNS Random Graph Model](https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAC0109/1333.html), in Discrete Random Walks, DRW'03, Cyril Banderier and Christian Krattenthaler (eds.), Discrete Mathematics and Theoretical Computer Science Proceedings AC, pp. 95-104 (2003). [D06] Rick Durrett, "Chapter 7: CHKNS model", [Random Graph Dynamics](https://services.math.duke.edu/~rtd/RGD/RGD.html). Cambridge U. Press, pp. 187-202 (2006). [JR12] Svante Janson, Oliver Riordan, [Susceptibility in inhomogeneous random graphs](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p31). Electronic J. Combinatorics 19, #P31 (2012), ([arXiv:0905.0437](https://arxiv.org/abs/0905.0437)). ` }48:T67c,md`## Implementation notes First, feel free to tweet at me ([@blockspins](https://twitter.com/blockspins)) if you have questions or comments! [Here's](#svg) a link to the topmost \`svg\` cell. The main union-find data structure is defined in a rather complicated cell right beneath it in [\`viewof labels\`](#labels) (the input events dispatched at this cell can have details which tell it to *Make*, *Find*, or *Link*). However, \`svg\` (and [the d3-force simulation cell \`sim\`](#sim)) depend on it only indirectly via [\`dataLabels\`](#dataLabels) ("nodes" array for \`sim\`) and [\`links\`](#links) ("links" array for d3.forceLink in \`sim\`). These latter two cells define arrays which are generated dynamically from \`labels.roots\` and \`labels.ranks\`. I originally began writing this visualization to serve as a component in another (forthcoming) Observable notebook, so hopefully it should be possible to import the top tree graphic into any notebook that uses the \`UnionFind\` module as follows (using the "\`import\` ... \`with\`" syntax to replace some of the cells here with cells in the target notebook): \`\`\`js import {svg} with {labels as labels, config as config, d3 as d3, UnionFind as UnionFind} from "@bryangingechen/union-find-data-structure" \`\`\` The controls I programmed are hacky and likely overly complex. Forks and suggestions for improvement very welcome! Below, I give some brief comments before blocks of related cells; click [here](#chartComments) to skip to the cells related to the stacked bar chart and [here](#scatterComments) to skip to the cells related to the overlays on Figures 1 and 3 of [CHKNS01].`49:T4d9,// re-running this cell creates a new "dataLabels" and should reset the force simulation dataLabels = { // doesn't deal well with "undefined" roots (can occur if linking to an uninitialized set, though that should probably be disallowed by the upstream API...) const svgW = config.W, svgH = config.H, x0 = config.x0, y0 = config.y0, r = config.R/1.4; let dataLabels = (this) ? this : []; labels.roots.forEach((d,i) => { // (assumes labels are added and removed in order) if (i < dataLabels.length) { // update existing labels dataLabels[i].key = i; dataLabels[i].root = d; dataLabels[i].rank = labels.ranks[i]; } if (i >= dataLabels.length) { // add new labels dataLabels.push({key:i, root:d, rank:labels.ranks[i], x:x0 + r*Math.cos(2*Math.PI*Math.random()), y:y0 + r*Math.cos(2*Math.PI*Math.random())}); } if (i+5 >= colorArray.length) { // fill colorArray with random colors const color = '#' + (Math.random().toString(16) + "000000").substring(2, 8); colorArray.push(color); } }); dataLabels = dataLabels.slice(0, labels.roots.length); // remove nonexistent labels return dataLabels; }4a:T407,links = { if (show) { if (this && dataLabels.length >= this.length) { // reset if there are more links than nodes const links = []; const pushed = []; this.filter(link => link.source.root === link.t) // check existing edges .filter(link => link.source === dataLabels[link.s]) .forEach(link => { links.push(link); pushed.push(link.s); }); // add newly created edges dataLabels.filter(d => (d.root !== d.key)) // filter out "tree roots" .filter(d => pushed.every(dd => (dd !== d.key))) // filter out already added edges .forEach(d => links.push({source: d.key, s:d.key, target: d.root, t:d.root, id:DOM.uid('link').id})); return links; } const links = []; dataLabels.forEach(d => { if (d.root !== d.key) links.push({source: d.key, s:d.key, target: d.root, t:d.root, id:DOM.uid('link').id}); }); return links; } else return null; }4b:T635,exampleScript = { if (state === "example") { // a little manually-coded example yield Promises.tick(delay, 'example start'); if (exampleState < 15) { mutable exampleState++; viewof labels.dispatchEvent(new CustomEvent('input', {detail:{method:'make'}})); yield Promises.tick(delay, `making ${exampleState}`); } const links = [[1,2], [3,4], [5,6], [6,7], [2,4], [5,7], [5,3], [9,14], [13,14], [8,0], [13,0], [1,9], ]; if (exampleState < 15 + links.length) { mutable exampleState++; viewof labels.dispatchEvent(new CustomEvent('input', {detail:{method:'link', nodes:links[exampleState - 15]}})); yield Promises.tick(delay, `linking 1 ${exampleState}`); } if (exampleState < 21 + links.length) { mutable exampleState++; viewof labels.dispatchEvent(new CustomEvent('input', {detail:{method:'make'}})); yield Promises.tick(delay, `making ${exampleState - links.length}`); } const links2 = [[20,11], [16,11], [15,18], ]; if (exampleState < 21 + links.length + links2.length) { mutable exampleState++; viewof labels.dispatchEvent(new CustomEvent('input', {detail:{method:'link', nodes:links2[exampleState - 21 - links.length]}})); yield Promises.tick(delay, `linking 2 ${exampleState - links.length -21}`); } mutable exampleState = 0; viewof state.value = "finished"; viewof state.dispatchEvent(new CustomEvent("input")); } yield Promises.tick(delay, 'finished'); }4c:Tc6b,function randomControl(view, instantUpdate = true) { const containerStyle = `style='display:inline-block;'`; const inputAttrs = `type='number' min='0' max='100' step='0.001' style='width:55px'`; const div = html`

% Link, % Make, % Find.
Make/Link = `; const slider = div.querySelector('.slider'); const linkInput = div.querySelector('.linkInput'); const cFindInput = div.querySelector('.cFindInput'); const makeSpan = div.querySelector('.makeSpan'); const makeOverLinkSpan = div.querySelector('.makeOverLinkSpan'); noUiSlider.create(slider, { start: [40000/15., 40000/5.], connect: [true, true, true], range: { 'min': [0], 'max': [10000] } }); const connect = slider.querySelectorAll('.noUi-connect'); const classes = ['c-1-color', 'c-2-color', 'c-3-color']; for (var i = 0; i < connect.length; i++) { connect[i].classList.add(classes[i]); } function updateSpan(arr) { linkInput.value = (100*arr[0]).toFixed(3); cFindInput.value = (100*(1-arr[1])).toFixed(3); makeSpan.innerHTML = `${(100*(arr[1]-arr[0])).toPrecision(5)}% Make,`; makeOverLinkSpan.innerHTML = `Make/Link = ${(arr[1]/arr[0]-1).toPrecision(5)}`; } function numInput(priority) { function constrain(val) { return Math.min(Math.max(val,0),100); } linkInput.value = constrain(linkInput.value); cFindInput.value = constrain(cFindInput.value); if (priority === 'link') { cFindInput.value = Math.min(cFindInput.value, 100 - linkInput.value); } else { linkInput.value = Math.min(linkInput.value, 100 - cFindInput.value); } const arr = [linkInput.value/100, 1 - cFindInput.value/100]; if (instantUpdate) view.value = ({linkProb:arr[0], findProb:arr[1]}); slider.noUiSlider.set(arr.map(d => Math.round(10000*d))); updateSpan(arr); } linkInput.onchange = () => numInput('link'); cFindInput.onchange = () => numInput('find'); slider.noUiSlider.on('slide', (e) => { const arr = slider.noUiSlider.get().map(d => d/10000); if (instantUpdate) view.value = ({linkProb:arr[0], findProb:arr[1]}); updateSpan(arr); }); // https://beta.observablehq.com/@mbostock/synchronized-views const update = () => { const obj = view.value; const arr = [obj.linkProb, obj.findProb]; updateSpan(arr); slider.noUiSlider.set(arr.map(d => Math.round(10000*d))); }; view.addEventListener("input", update); invalidation.then(() => view.removeEventListener("input", update)); update(); return div; }4d:Taac,chartDataObj = { if (navigator.userAgent.match('HeadlessChrome')) return ''; const numNode = labels.roots.length; const numIso = labels.roots.map((d,i) => ({ind:i,root:d})) .filter(d => d.root == d.ind) .filter(d => labels.ranks[d.ind] === 0) .length; const histoMap = d3.rollup(rootsOf(labels), v => v.length, d => d); const numTrees = Array.from(histoMap, ([i,d]) => ({name:`tree rooted at ${i}`, value:d, time:timestep, end:false})) .filter(d => d.value > 1); const names = numTrees.map(d => d.name); names.push('isolated roots'); const dat = (numNode > 0) ? [{name:'isolated roots', value:numIso, time:timestep, end:false}, ... numTrees] : []; const datEnd = dat.map(({name,value,time,end}) => ({name:name, value:value, time:time+1, end:end})); let data = dat.concat(datEnd); let relData = data.map(({name,value,time,end}) => ({name:name, value:value/numNode, time:time, end:end})); function makeStack(data) { // Compute all trees const top = [...multisum(data.map(d => [d.name, d.value]))] .map(d => d[0]); // Group the data by tree, then re-order the data by descending value. const series = multimap(data.map(d => [d.name, d])); data = [].concat(...top.map(name => series.get(name))); const fun = d3.stack() .keys(top) .value( (d, key) => (d.has(key)) ? (d.get(key).end ? // logic for "end" blocks 0 : d.get(key).value) : 0); const arg = Array.from( multimap( data.map(d => [+d.time, d]), (p, v) => p.set(v.name, v), () => new Map ).values() ); // Compute the stack offsets. const stack = fun(arg); // Copy the offsets back into the data. for (const layer of stack) { for (const d of layer) { if (d.data.has(layer.key)) d.data.get(layer.key).values = [d[0], d[1]]; } } return data; } data = makeStack(data); relData = makeStack(relData); if (this && this.abs && this.rel && data.length > 0 && relData.length > 0) { const absArr = this.abs.filter(d => (d.time < timestep || (d.time === timestep && !names.includes(d.name)))); absArr.push(...data); const relArr = this.rel.filter(d => (d.time < timestep || (d.time === timestep && !names.includes(d.name)))); relArr.push(...relData); const treeSet = this.trees; names.forEach(name => treeSet.add(name)); return ({abs:absArr, rel:relArr, trees:treeSet}); } else { const treeSet = new Set(names); return ({abs:data, rel:relData, trees:treeSet}); } }4e:T4a3,// https://beta.observablehq.com/@mbostock/linked-inputs function numOpsControl(view) { const div = html`

Perform random operations`; const range = div.querySelector("[type=range]"); const number = div.querySelector("[type=number]"); range.oninput = () => { number.value = Math.floor(Math.exp(range.valueAsNumber)); }; number.oninput = () => { range.value = Math.log(number.valueAsNumber); }; number.onchange = () => { number.value = Math.floor(Math.max(number.value, 1)); range.value = Math.log(number.valueAsNumber); } // https://beta.observablehq.com/@mbostock/synchronized-views const update = () => { number.value = view.value; range.value = Math.log(number.valueAsNumber); }; view.addEventListener("input", update); invalidation.then(() => view.removeEventListener("input", update)); update(); return div; }4f:T411,loopUfs = { if (navigator.userAgent.match('HeadlessChrome')) return ''; if (runLoop) { const prom = []; const numPts = 50; // number of 'edges per vertex' values to compute between 0 and 1 const numReps = 5; // number of forests to generate at each value of 'edges per vertex' for (let delta = 1; delta <= numPts; delta++) for (let rep = 0; rep < numReps; rep++) { prom.push(await new Promise(notify => { // number of random operations to perform const numOps = (Math.abs(delta/numPts-0.2) <= 0.1) ? 500000 : 20000; const linkProb = delta / (numPts+delta); const worker = new Worker(randomWorker); worker.addEventListener("message", ({data}) => notify({data,delta:delta/numPts})); worker.postMessage({numOps, linkProb, findProb:1}); return () => worker.terminate(); })); yield prom; } mutable runLoop = false; yield prom; // return await Promise.all(prom); } else { yield this || []; } }50:T56b,scatterAppend = { // give this cell an explicit dependency on the cells it acts on scatterFigCell1; scatterFigCell3; const showScatter = runLoop || loopUfs.length > 0; const figSel1 = d3.selectAll('#scatterSVG1'); figSel1.selectAll('.insetScatter').remove(); figSel1.append('g').classed('insetScatter', true) .attr('transform', `translate(56.5,3.75)`) .attr('opacity', showScatter ? 1 : 0) .append(() => scatterChart1); const opaqueMask1 = figSel1.selectAll('.opaque') .attr('opacity', showScatter ? 1 : 0); const transpMask1 = figSel1.selectAll('.transp') .attr('opacity', showScatter ? 0.85 : 0); const figSel3 = d3.selectAll('#scatterSVG3'); figSel3.selectAll('.insetScatter').remove(); figSel3.append('g').classed('insetScatter', true) .attr('transform', `translate(61,-2.2)`) .attr('opacity', showScatter ? 1 : 0) .append(() => scatterChart3); const opaqueMask3 = figSel3.selectAll('.opaque') .attr('opacity', showScatter ? 1 : 0); const transpMask3 = figSel3.selectAll('.transp') .attr('opacity', showScatter ? 0.85 : 0); return md`scatterAppend = This cell appends the scatterplots to the cells [\`scatterFigCell1\`](#scatterFigCell1) and [\`scatterFigCell3\`](#scatterFigCell3). A separate cell is necessary so that the "Stop simulation!" buttons are more responsive.`; }51:T759,function drawAdjMat(uf, fillComponents=false, maxSize=250) { const numVerts = uf.roots.length; const roots = rootsOf(uf); const size = (numVerts < maxSize) ? Math.floor(maxSize/numVerts)*numVerts : maxSize; const context = DOM.context2d(size, size); const pScale = (numVerts < maxSize) ? Math.floor(maxSize/numVerts) : maxSize/numVerts; const pixelSize = (numVerts < maxSize) ? pScale : 1; const map = new Map(); let maxVal = 0; if (fillComponents) { // draw all edges between vertices in the same connected component for (let i = 0; i < numVerts; i++) { for (let j = i+1; j < numVerts; j++) { if (roots[i] === roots[j]) { const key = JSON.stringify([Math.floor(pScale*i), Math.floor(pScale*j)]); if (map.has(key)) { const val = map.get(key); map.set(key, val+1); } else map.set(key, 1); } } } } else { for (let i = 0; i < numVerts; i++) { const j = uf.roots[i]; if (i !==j) { const key = JSON.stringify([Math.floor(pScale*i), Math.floor(pScale*j)]); if (map.has(key)) { const val = map.get(key); map.set(key, val+1); } else map.set(key, 1); } } } for (let i = 0; i < size; i++) for (let j = i; j < size; j++) { const key = JSON.stringify([i,j]); if (map.has(key)) { const val = map.get(key); const gs = (numVerts < size || numVerts < 10 ** 4) ? 0 : Math.floor(255*(1 - (1*10 ** 4)*val/(numVerts))); context.fillStyle = `rgb(${gs}, ${gs}, ${gs})`; context.fillRect(j, i, pixelSize,pixelSize); context.fillRect(i, j, pixelSize,pixelSize); } } context.strokeStyle = `rgb(100,100,100)`; context.strokeRect(0, 0, size, size); return context.canvas; }52:[{"id":"e52ca7fa39bb3f3c2422d727897c914456ab5abe16b88d41356748163a805c34766d83ba5b7334bad85e871fc0e3d1e138c00dbe7bd6ff517be3aa353c3d4b88","href":"https://static.observableusercontent.com/files/e52ca7fa39bb3f3c2422d727897c914456ab5abe16b88d41356748163a805c34766d83ba5b7334bad85e871fc0e3d1e138c00dbe7bd6ff517be3aa353c3d4b88","name":"union-find-1.0.2.js","type":"application/javascript","lastModified":1691688357146.115,"size":1364}] 2d:{"id":"10915f45297ac138","slug":null,"title":"Union-find data structure","thumbnail":"557c813953da3de5a859082f5e7a662ac283b54f2a68e285b205fd0fabceb19c","access_level":"public","create_time":"$D2023-08-10T17:25:57.146Z","update_time":"$D2023-08-10T17:25:57.146Z","view_time":null,"first_public_time":"$D2023-08-10T17:25:57.146Z","fork":{"id":"55b11fe765c656f7","slug":"union-find-data-structure","title":"Union-find data structure","owner":{"id":"d2fd23101beb2a61","login":"bryangingechen","name":"Bryan Gin-ge Chen"}},"stars":0,"starred":false,"owner":{"type":"team","id":"779801569d020938","login":"bysance","name":"Jean Constant","avatar_url":"https://avatars-next.observableusercontent.com/d9f8e121946490c519c81e74442053389852cc121f55569dbcd93451890d616e","tier":"starter_2024"},"version":5918,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"8551b105ce4f03cb","login":"bysance","name":"Jean Constant","avatar_url":"https://avatars-next.observableusercontent.com/d9f8e121946490c519c81e74442053389852cc121f55569dbcd93451890d616e","tier":null}],"members":[{"type":"individual","id":"8551b105ce4f03cb","login":"bysance","name":"Jean Constant","avatar_url":"https://avatars-next.observableusercontent.com/d9f8e121946490c519c81e74442053389852cc121f55569dbcd93451890d616e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Union-find data structure","cells":[{"id":0,"value":"md`# Union-find data structure\n\n${// thumbnail trick from https://beta.observablehq.com/@mootari/custom-notebook-thumbnail\nnavigator.userAgent.match('HeadlessChrome') ? html`

` : ''}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":65,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":188,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":223,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":743,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1333,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1541,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1767,"value":"navigator.userAgent.match('HeadlessChrome') ? '' : chart","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1627,"value":"chartSliders = navigator.userAgent.match('HeadlessChrome') ? '' : html`

${delayControl()} ${randomControl(viewof randomProbs)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3021,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2967,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3384,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2990,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3251,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3193,"value":"histoCell = {\n if (navigator.userAgent.match('HeadlessChrome'))\n return '';\n \n const figSel = d3.select(sizeHistoChart);\n \n figSel.selectAll('.inset').remove();\n \n figSel.append('g').classed('inset', true)\n .attr('transform', `translate(${2*width/3 - 50},0)`)\n .append(() => depthHistoChart);\n \n figSel.append('g').classed('inset', true)\n .attr('transform', `translate(${width/3 - 50},0)`)\n .append(() => heightHistoChart);\n \n return html`

${sizeHistoChart}
\n Size of largest tree: ${his.maxSize}`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4211,"value":"md`** Done exploring? ** Continue on for spoilers.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1539,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2674,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3980,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4772,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4254,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5175,"value":"$40","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5179,"value":"$41","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5181,"value":"$42","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5419,"value":"$43","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5519,"value":"$44","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2885,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5088,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2664,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1319,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":821,"value":"config = ({W:svgW, H:svgH, // size of `svg`\n x0:svgW/2, y0:svgH/2, // center of positioning circle\n R:Math.min(svgW, svgH)/4, // radius of positioning circle\n L:4.5, // ratio of links to radius of colored disks\n size:20, // max radius of disks; see circleRad\n hover:true, // if \"true\", then the force simulation will be activated when hovering over `svg`\n bg:null, outline:null}) // these color the `svg` cell's background `rect` and outline stroke, respectively","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":31,"value":"svgW = width","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":33,"value":"svgH = 500","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":734,"value":"circleRad = Math.min(config.size, (config.size*16) / labels.roots.length)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2331,"value":"md`The next four cells make up the interface between the actual union-find data structure \"\\`labels\\`\" and the visualization \"\\`svg\\`\".`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":67,"value":"colorArray = {\n if (this && state === \"finished\" || state === \"random\") // usually this will be modified by dataLabels\n return this;\n let colorArray = []; // if state is not \"finished\", then we need to seed with a few colors\n for (let i = 0; i < 5; i++) {\n const color = '#' + (Math.random().toString(16) + \"000000\").substring(2, 8);\n colorArray.push(color);\n }\n return colorArray;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":38,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":43,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":28,"value":"sim = {\n if (show) {\n const svgW = config.W,\n svgH = config.H,\n x0 = config.x0,\n y0 = config.y0,\n L = config.L;\n\n if (this)\n // update nodes\n return this.nodes(dataLabels)\n // update centering (needed if width changes)\n .force('center', \n d3.forceRadial(d => config.R, x0, y0)\n .strength(d => (d.root === d.key) ? 1 : 0))\n // update links\n .force('links',\n d3.forceLink(links).id(d => d.key)\n .distance(L*circleRad)\n .strength(1)\n );\n return d3.forceSimulation(dataLabels)\n .force('center', \n d3.forceRadial(d => config.R, x0, y0)\n .strength(d => (d.root === d.key) ? 1 : 0))\n .force('links', \n d3.forceLink(links).id(d => d.key)\n .distance(L*circleRad)\n .strength(1)\n );\n } else\n return null;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2334,"value":"md`The \\`span*\\` cells color the outlines around *Make*, *Link* and *Find*.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1047,"value":"function spanColor(method) {\n return (method === 'find') ? \n 'deeppink' :\n (method === 'link') ?\n 'lawngreen' :\n 'DeepSkyBlue';\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1408,"value":"spanStyle = (method) => \n `style=\"padding:5px; height:15px; border:3px solid ${spanColor(method)}; border-radius:12px;\n display:inline-flex; align-items:center; vertical-align:middle;\"`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2336,"value":"md`The \\`highlight*\\` cells give rise to the colored circles around the disks that indicate whether the most recent operation was *Make*, *Link* or *Find*.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1078,"value":"highlightSVG = {\n if (show) { // highlight\n const selection = d3.select(svg).select(\"g\").selectAll('g').data(dataLabels, d => d.key);\n\n selection.selectAll('.highlight').remove();\n\n selection.filter(d => highlight.nodes.some(dd => d.key === dd))\n .append('circle')\n .classed('highlight', true)\n .attr('r', d => circleRad * (d.rank/5 + 1) + 7)\n .attr('fill', 'none')\n .attr('stroke-width', 3)\n .attr('stroke', d => spanColor(highlight.method));\n } else\n return null;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":988,"value":"mutable highlight = ({nodes:[], method:''})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2338,"value":"md`The next group governs the two \"auto-play\" modes: the pre-programmed example and the random operations button.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1293,"value":"viewof delay = new View(750)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1268,"value":"// https://beta.observablehq.com/@mbostock/linked-inputs\nfunction delayControl() {\n const div = html`

\n
\n ms delay between steps
\n (0 ms delay = pause)\n `;\n const range = div.querySelector(\"[type=range]\");\n const number = div.querySelector(\"[type=number]\");\n \n range.oninput = () => {\n number.value = range.valueAsNumber;\n viewof delay.value = number.valueAsNumber;\n };\n number.onchange = () => {\n range.value = number.valueAsNumber;\n viewof delay.value = number.valueAsNumber;\n };\n \n // https://beta.observablehq.com/@mbostock/synchronized-views\n const update = () => {\n range.value = number.value = viewof delay.value;\n };\n viewof delay.addEventListener(\"input\", update);\n invalidation.then(() => viewof delay.removeEventListener(\"input\", update));\n \n update();\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1303,"value":"mutable exampleState = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1267,"value":"$4b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1387,"value":"viewof randomProbs = new View({linkProb: 0.266667, findProb: 0.8})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1657,"value":"randomProbs","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1343,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1357,"value":"randomControlStyles = html`randomControlStyles = style cell for randomControl noUiSlider gadget`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1266,"value":"randomScript = {\n const rnode = () => Math.floor(labels.roots.length*Math.random());\n \n if (state === 'random') {\n yield Promises.tick(delay, 'randomly doing stuff');\n\n const r = Math.random();\n \n if (labels.roots.length > 1 && r < randomProbs.linkProb) {\n viewof labels.dispatchEvent(new CustomEvent('input', {detail:{method:'link', nodes:[rnode(), rnode()]}}));\n } else if (labels.roots.length > 0 && r > randomProbs.findProb) {\n viewof labels.dispatchEvent(new CustomEvent('input', {detail:{method:'find', nodes:[rnode()]}}));\n } else {\n viewof labels.dispatchEvent(new CustomEvent('input', {detail:{method:'make'}}));\n }\n }\n yield 'finished';\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1985,"value":"md`\\`state\\` is

\"${state}\"`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2536,"value":"md`The next two cells are used to determine when to hide the main tree graphic and what to show in place of it.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2148,"value":"mutable show = navigator.userAgent.match('HeadlessChrome') ? false : true","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2176,"value":"hideSVG = () => html`Graphic hidden by chart control.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2343,"value":"chartComments = md`The stacked bar chart is imported from [Mike Bostock's \"D3 Stacked Area Chart\"](https://beta.observablehq.com/@mbostock/d3-stacked-area-chart). The following cells generate the data, axes, legend, etc. which replace those in the import. The most interesting one is probably [\\`chartDataObj\\`](#chartDataObj) which processes the data structure in \\`labels\\` into entries in two growing timeseries (one for the absolute number of sets in each tree over time and one for the fraction of sets in each tree over time).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2136,"value":"chartMargin = ({top: 5, right: 40, bottom: 30, left: 20})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1770,"value":"chartX = d3.scaleLinear()\n    .domain([0, timestep+1])\n    .range([chartMargin.left + (chartRel ? 110 : 0), width - chartMargin.right])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1775,"value":"chartArea = d3.area()\n    .curve(d3.curveStepAfter)\n    .x(d => chartX(d.time))\n    .y0(d => y(d.values[0]))\n    .y1(d => y(d.values[1]))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1988,"value":"// chartColor = d3.scaleOrdinal(d3.schemeCategory10).domain(chartData.map(d => d.name))\nchartColor = {\n  const namesUniq = Array.from(chartDataObj.trees);\n  return d3.scaleOrdinal(namesUniq.map(d => {\n    if (d === 'isolated roots')\n      return '#AAAAAA';\n    return colorArray[d.match(/ (\\d+)$/)[1]];\n  })).domain(namesUniq);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2083,"value":"chartLegend = svg => {\n  const g = svg\n      .attr(\"font-family\", \"sans-serif\")\n      .attr(\"font-size\", 10)\n    .selectAll(\"g\")\n//   TODO? better choice of trees to include in the legend\n    .data(chartColor.domain().slice(0, chartRel ? 23 : 15).reverse())\n    .enter().append(\"g\")\n      .attr(\"transform\", (d, i) => `translate(0,${i * 20})`);\n\n  g.append(\"rect\")\n      .attr(\"width\", 19)\n      .attr(\"height\", 19)\n      .attr(\"fill\", chartColor);\n\n  g.append(\"text\")\n      .attr(\"x\", 24)\n      .attr(\"y\", 9.5)\n      .attr(\"dy\", \"0.35em\")\n      .text(d => d);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2095,"value":"mutable chartRel = false","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2102,"value":"chartData = chartRel ? chartDataObj.rel : chartDataObj.abs","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1909,"value":"timestep = {\n  if (typeof(this) !== 'number' || labels.roots.length === 0)\n    return 0;\n  else \n    return this+1;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3025,"value":"function rootsOf(labels) {\n  return labels.roots.map(d => {\n    while (d != labels.roots[d])\n      d = labels.roots[d];\n    return d;\n  });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2112,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2678,"value":"md`\\`toggleFig\\` is a little function to allow toggling between absolute and relative bar charts for the \"vapor / droplet state\" screenshots:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2605,"value":"function toggleFig (url1, url2){\n  const div = html`
`;\n  div.addEventListener (\"click\", toggle, false);\n  const img = div.firstChild;\n  function toggle() {\n    img.src = (img.src === url1) ? url2 : url1;\n  }\n  return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2972,"value":"md`The next few cells are used in the \"circle-packing\" visualization of the random forests in [this cell](#packing). I learned how to do this via studying [Mike Bostock's \"Pack-o-matic\"](https://beta.observablehq.com/@mbostock/pack-o-matic) notebook. Because generating large random forests and then packing circles for them is computationally expensive, I have the cells above call [Web Worker](https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers) scripts. See [Fil's \"Worker\"](https://beta.observablehq.com/@fil/worker) and the resources linked there for helpful advice and examples.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3006,"value":"viewof numOps = new View(20000)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3030,"value":"md`numOps is ${numOps}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3008,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2992,"value":"viewof randomProbs2 = new View({linkProb: 0.11111111, findProb: 1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3187,"value":"randomProbs2","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2828,"value":"uf = {\n  if (navigator.userAgent.match('HeadlessChrome'))\n    return '';\n  \n  return Generators.queue(notify => {\n    // const linkProb = .2;\n    // const findProb = 1;\n    const linkProb = randomProbs2.linkProb;\n    const findProb = randomProbs2.findProb;\n    const worker = new Worker(randomWorker);\n    worker.addEventListener(\"message\", ({data}) => notify(data));\n    worker.postMessage({numOps, linkProb, findProb});\n    return () => worker.terminate();\n  });\n\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5911,"value":"randomWorker = {\n  const blob = new Blob(\n    [\n      `\nimportScripts(\"${await FileAttachment(\"union-find-1.0.2.js\").url()}\");\n\nonmessage = event => {\n  const {data: {numOps, linkProb, findProb}} = event;\n\n  const uf = new unionFind(0);\n  for (let j=0; j < numOps; j++) {\n    const rnode = () => Math.floor(uf.roots.length*Math.random());\n    const r = Math.random();\n    if (uf.roots.length > 1 && r < linkProb) {\n      const l1 = rnode(),\n            l2 = rnode();\n      uf.link(l1,l2);\n    } else if (uf.roots.length > 0 && r > findProb) {\n      const f = rnode();\n      uf.find(f);\n    } else {\n      uf.makeSet();\n    }\n    // if (j > 0 && j%1000000 === 0)\n    //   postMessage(uf);\n  }\n  postMessage(uf);\n  close();\n};\n`\n    ],\n    { type: \"text/javascript\" }\n  );\n  const script = URL.createObjectURL(blob);\n  invalidation.then(() => URL.revokeObjectURL(script));\n  return script;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4105,"value":"mutable packColorDepth = true","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2965,"value":"packColorsDepth = ({fills:['#1b5e20', '#82e0aa', '#9a7d0a', 'yellow', 'orange', 'red', 'black'],\n             strokes:['saddlebrown', 'chocolate', 'lightbrown', 'gold', 'blue', 'purple', 'white']})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3315,"value":"packSVGDepth = (i) => ``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4127,"value":"packColorsId = ({fills: (frac) => d3.interpolateInferno(1 - frac),\n                 strokes: (frac) => d3.interpolateGreys(1 - frac)})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4122,"value":"packSVGId = (frac) => ``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3716,"value":"mutable showPack = navigator.userAgent.match('HeadlessChrome') ? false : true","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2969,"value":"packWorker = {\n  const blob = new Blob([`\nimportScripts(\"${await require.resolve(\"d3-hierarchy@1\")}\");\n\nonmessage = event => {\n  const {data: {data, L, pad}} = event;\n\n  const pack = data => d3.pack()\n    .size([L,L])\n    .padding(pad)\n  (d3.hierarchy(data)\n    .sum(d => d.children ? 1 : isNaN(d.value) ? 1 : d.value)\n    .sort((a, b) => b.value - a.value));\nconst root = pack(data);\nconst nodes = root.descendants().slice(1);\n\n  postMessage(nodes);\n\n  close();\n};\n`], {type: \"text/javascript\"});\n  const script = URL.createObjectURL(blob);\n  invalidation.then(() => URL.revokeObjectURL(script));\n  return script;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3405,"value":"md`The next group of cells generate the statistics for the [histogram bar charts](#histoCell). The charts themselves are imported from [a fork](/@bryangingechen/d3-log-scaled-histogram) of Mike Bostock's [\"D3 Histogram\"](/@mbostock/d3-histogram).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2851,"value":"his = {\n  const dat = Array.from(d3.rollup(rootsOf(uf), v => v.length, d=>d).values())\n    .sort((a,b) => b-a);\n  \n  return ({data:dat, maxSize:dat[0]});\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3586,"value":"ufRoots = [...new Set(rootsOf(uf))]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3680,"value":"ufStratify = \n  d3.stratify()\n    .id((d,i) => i)\n    .parentId(d => d)\n    (uf.roots.map(\n      (d,i) => (d === i) ? uf.roots.length : d)\n        .concat(undefined)\n    )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3693,"value":"ufHierarchy = d3.hierarchy(ufStratify)\n    .sum(d => d.children ? 1 : isNaN(d.value) ? 1 : d.value)\n    .sort((a, b) => b.value - a.value)\n  .descendants().slice(1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3217,"value":"sizeHisto = {\n  const dat = his.data.filter(d => d <= 2*his.data[1]);\n  dat.x = 'size';\n  dat.y = 'number of trees';\n  \n  return dat;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3648,"value":"sizeHistoTicks = Math.min(sizeHisto[0], 40)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3419,"value":"depthHisto = {\n  // depth is shifted by one since all sets are contained in a universal root node\n  // see https://github.com/d3/d3-hierarchy#hierarchy\n  const data = ufHierarchy.map(d => d.depth-1);\n  data.x = 'depth';\n  data.y = 'number of sets';\n  return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3438,"value":"depthNumTicks = ufHierarchy.reduce((currMax, d) => {\n  const max = d.depth-1;\n  if (max > currMax)\n    currMax = max;\n  return currMax;\n}, 0)+1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3463,"value":"depthHistoHeight = 500/3","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3465,"value":"depthHistoWidth = width/3","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3633,"value":"packMap = {\n  const map = new Map();\n  for (const obj of ufHierarchy) {\n    map.set(obj.data.id,obj.data);\n  }\n  return map;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3592,"value":"heightTrees = {\n  const data = ufRoots.map(d => packMap.get(d.toString()).height);\n  data.x = 'height';\n  data.y = 'number of trees';\n  return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4061,"value":"scatterComments = md`The next five cells control the simulation that recreates [Figure 1 from [CHKNS01]](#scatterFigCell1). \\`loopUfs\\` is a generator that yields a growing array of random Union-Find structures, which is processed by \\`loopData\\` into \\`loopMaxSizes\\` and \\`loopgPrime\\`, which provide the data for the scatterplots (both imported from a fork to Mike Bostock's \"[D3 Scatterplot](/@mbostock/d3-scatterplot)\").`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4004,"value":"mutable runLoop = false","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3787,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3834,"value":"loopData = {\n  const dat0 = this ? ((this.length <= loopUfs.length) ? this : []) : [];\n  const data = loopUfs.slice(dat0.length).map(({data:uf, delta}) => {\n    const dat = Array.from(d3.rollup(rootsOf(uf), v => v.length, d=>d).values())\n    .sort((a,b) => b-a);\n    \n    const maxSize = dat[0]/uf.roots.length;\n    // see equation 14 in [CHKNS01]\n    // note that by \"average size of components\" they mean with respect to a randomly chosen set, not tree\n    const gPrime = (delta < 1/8) ?\n      dat.reduce((a,b) => a+b*b) / uf.roots.length : \n      (1 - maxSize) * dat.slice(1).reduce((a,b) => a+b*b) / (uf.roots.length-dat[0]);\n    return ({delta, maxSize, gPrime});\n  });\n  return dat0.concat(data);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4723,"value":"loopMaxSizes = {\n  const data = loopData.map(({delta,maxSize}) => ({x:delta, y:maxSize}));\n  data.x = 'edges per vertex';\n  data.y = 'giant component size';\n  return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4731,"value":"loopgPrime = {\n  const data = loopData.map(({delta,gPrime}) => ({x:delta, y:gPrime}));\n  data.x = 'edges per vertex';\n  data.y = \"g'(1)\";\n  return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4607,"value":"$50","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3870,"value":"scatterW1 = 485.5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3872,"value":"scatterH1 = 312.5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4047,"value":"scatterX1 = d3.scaleLinear()\n    .domain([0,1]).nice()\n    .range([40, scatterW1 - 30])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4051,"value":"scatterY1 = d3.scaleLinear()\n    .domain([0,0.65]).nice()\n    .range([scatterH1 - 30, 20])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4799,"value":"scatterW3 = 479.5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4801,"value":"scatterH3 = 310","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4803,"value":"scatterX3 = d3.scaleLinear()\n    .domain([0,1]).nice()\n    .range([40, scatterW3 - 30])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4739,"value":"scatterY3 = d3.scaleLinear()\n    .domain([0,5]).nice()\n    .range([scatterH3 - 30, 20])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4430,"value":"md`The following cells plot the adjacency matrix of a union-find object.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5440,"value":"viewof adjMatNumOps = new View(2000)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5346,"value":"adjMatCell = adjMatWidget(adjMatNumOps)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5277,"value":"function drawKer1(lam, maxSize=250) {\n  const context = DOM.context2d(maxSize, maxSize);\n  context.strokeStyle = `rgb(100,100,100)`;\n  context.strokeRect(0, 0, maxSize, maxSize);\n\n  for (let i = 0; i < maxSize; i++)\n    for (let j = 0; j < maxSize; j++) {\n      const pScale = lam * (1 / Math.max(i/maxSize,j/maxSize) -1);\n      context.fillStyle = `rgba(0,0,0,${pScale})`;\n      context.fillRect(i, j, 1, 1);\n    }\n  return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4434,"value":"$51","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5344,"value":"function adjMatWidget(numOps) {\n  return Generators.queue(notify => {\n    const linkProb = 0.125;\n    const findProb = 1;\n    const worker = new Worker(randomWorker);\n    worker.addEventListener(\"message\", ({data}) => notify(drawAdjMat(data, false, 250)));\n    worker.postMessage({numOps, linkProb, findProb});\n    return () => worker.terminate();\n  });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8,"value":"md`## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6,"value":"// https://github.com/mikolalysenko/union-find\nUnionFind = require(await FileAttachment(\"union-find-1.0.2.js\").url())\n// UnionFind = require('https://bundle.run/union-find@1.0.2')\n// UnionFind = require('https://packd.now.sh/union-find@1.0.2') // if bundle.run is down","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4,"value":"d3 = require('d3@5','d3-array@2')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":74,"value":"// Code by Onur Yıldırım: https://stackoverflow.com/a/35970186/\nfunction invertColor(hex, bw=true) {\n    if (hex.indexOf('#') === 0) {\n        hex = hex.slice(1);\n    }\n    // convert 3-digit hex to 6-digits.\n    if (hex.length === 3) {\n        hex = hex[0] + hex[0] + hex[1] + hex[1] + hex[2] + hex[2];\n    }\n    if (hex.length !== 6) {\n        throw new Error('Invalid HEX color.');\n    }\n    var r = parseInt(hex.slice(0, 2), 16),\n        g = parseInt(hex.slice(2, 4), 16),\n        b = parseInt(hex.slice(4, 6), 16);\n    if (bw) {\n        // http://stackoverflow.com/a/3943023/112731\n        return (r * 0.299 + g * 0.587 + b * 0.114) > 186\n            ? '#000000'\n            : '#FFFFFF';\n    }\n    // invert color components\n    r = (255 - r).toString(16);\n    g = (255 - g).toString(16);\n    b = (255 - b).toString(16);\n    // pad each with zeros and return\n    return \"#\" + padZero(r) + padZero(g) + padZero(b);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":76,"value":"// Code by Onur Yıldırım: https://stackoverflow.com/a/35970186/\nfunction padZero(str, len) {\n    len = len || 2;\n    var zeros = new Array(len).join('0');\n    return (zeros + str).slice(-len);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1346,"value":"import {noUiSlider} from '@bryangingechen/hello-nouislider'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1552,"value":"import {View} from '@mbostock/synchronized-views@374'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1765,"value":"import {chart, multisum, multimap, y} \nwith {chartMargin as margin, chartX as x, chartArea as area, \n      chartData as data, chartColor as color, chartLegend as legend,\n      d3 as d3} \nfrom '@mbostock/d3-stacked-area-chart@251'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3189,"value":"import {chart as sizeHistoChart} with {d3 as d3, sizeHisto as data, sizeHistoTicks as numTicks} \nfrom '@bryangingechen/d3-log-scaled-histogram'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3626,"value":"import {chart as depthHistoChart} with {d3 as d3, depthHisto as data,\n                                             depthHistoHeight as height, depthHistoWidth as width, \n                                              depthNumTicks as numTicks} \nfrom '@bryangingechen/d3-log-scaled-histogram'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3630,"value":"import {chart as heightHistoChart} with {d3 as d3, heightTrees as data,\n                                             depthHistoHeight as height, depthHistoWidth as width, \n                                              depthNumTicks as numTicks} \nfrom '@bryangingechen/d3-log-scaled-histogram'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3845,"value":"import {chart as scatterChart1} with {loopMaxSizes as data, d3 as d3, \n                                     scatterW1 as width, scatterH1 as height,\n                                     scatterX1 as x, scatterY1 as y} \nfrom '@bryangingechen/d3-scatterplot'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4733,"value":"import {chart as scatterChart3} with {loopgPrime as data, d3 as d3, \n                                     scatterW3 as width, scatterH3 as height,\n                                     scatterX3 as x, scatterY3 as y} \nfrom '@bryangingechen/d3-scatterplot'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5898,"value":"md`## Version log:\n\n- [2019/01/20](https://observablehq.com/@bryangingechen/union-find-data-structure@5853): First publish\n- [2019/05/06](https://observablehq.com/@bryangingechen/union-find-data-structure@5907): pin dependencies, use [d3.rollup](https://observablehq.com/@d3/d3-group) for histograms\n- 2020/04/30: removed bundle.run dependencies in favor of [FileAttachments](https://observablehq.com/@observablehq/file-attachments).\n\n## TODO:\n* Fix bugs that occur when putting the tab in the background due to use of \\`Promises.tick\\` in [\\`exampleScript\\`](#exampleScript)\n* Redo forms with [Form input](https://observablehq.com/@mbostock/form-input)?\n* Maybe use selection.join() in a few places\n* ~~Known issue: basically unusable in Chrome on a MacBook due to [this Chrome bug](https://bugs.chromium.org/p/chromium/issues/detail?id=852348)~~ This was fixed in Chrome 78 or so.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W52","stdlib":"1","titling":"auto"}}
2e:"$2d:body"