Public
Edited
Aug 12, 2023
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function pruferEncoding(adjacencyList) {
const n = adjacencyList.length;
const degree = adjacencyList.map(neighbors => neighbors.length);
const isLeaf = v => degree[v] === 1;
const pruferSequence = [];
for (const v of Generators.range(n)) {
for (let u = v; isLeaf(u) && u <= v;) {
// Find the remaining neighbor, and disconnect from it.
u = adjacencyList[u].find(neighbor => !isLeaf(neighbor));
--degree[u];
pruferSequence.push(u)
}
}
pruferSequence.pop();
return pruferSequence;
}
Insert cell
Insert cell
function pruferDecoding(pruferSequence) {
const n = pruferSequence.length + 2;
const reference = new Array(n).fill(0);
for (const v of pruferSequence) {
++reference[v];
}
const unbounded = v => reference[v] === 0;
pruferSequence.push(n - 1);
const pruferIterator = pruferSequence.values();
const adjacencyList = Array.from({length: n}, () => []);
for (const v of Generators.range(n)) {
for (let u = v; unbounded(u) && u <= v;) {
const w = pruferIterator.next().value;
--reference[w];
adjacencyList[u].push(w);
adjacencyList[w].push(u);
u = w;
}
}
return adjacencyList;
}
Insert cell
Insert cell
function randomTree(n) {
if (n < 2) {
throw new RangeError('Size of tree must be at least 2.');
}
return pruferDecoding(Array.from({length: n - 2}, () => Math.floor(Math.random() * n)));
}
Insert cell
Insert cell
Insert cell
function adjacencyList2d3Graph(adjacencyList) {
const n = adjacencyList.length;
const links = [];
// breadth-first search
const visited = new Array(n).fill(false);
const queue = [0];
while (queue.length) {
const u = queue.pop();
visited[u] = true;
for (const v of adjacencyList[u]) {
if (visited[v]) {
continue;
}
links.push({source: u, target: v});
queue.push(v);
}
}
return {
nodes: Array.from({length: n}, () => ({})),
links: links,
};
}
Insert cell
html`<style>
.link {
stroke: #000;
stroke-width: 1.5px;
}
.node {
cursor: move;
fill: #ccc;
stroke: #000;
stroke-width: 1.5px;
}
.node.fixed {
fill: #f00;
}
</style>`
Insert cell
Insert cell
d3 = require("d3@6")
Insert cell
import {Button, Range} from "@observablehq/inputs"
Insert cell
Insert cell
[...Generators.range(10)]
Insert cell
{
function* gen(n) {
for (let i = 0; i < n; ++i) {
yield i;
}
}
return [...gen(10)];
}
Insert cell

Purpose-built for displays of data

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