function aldousBroder(grid, rGen) {
const visited = Array.from(Array(grid.nRows), (_) =>
Array(grid.nCols).fill(false)
);
let numVisited = 0;
let c = randSample([...grid.eachCell()], rGen);
while (numVisited < grid.nRows * grid.nCols) {
const c2 = randSample(c.adjacent.filter(Boolean), rGen);
if (!visited[c2.row][c2.col]) {
c.link(c2);
visited[c2.row][c2.col] = true;
numVisited++;
}
c = c2;
}
return grid;
}
function wilson(grid, rGen) {
const start = grid.randomCell(rGen);
const visited = Array.from(Array(grid.nRows), (_) =>
Array(grid.nCols).fill(false)
);
visited[start.row][start.col] = true;
let unvisited = [...grid.eachCell()].filter(
(cell) => !visited[cell.row][cell.col]
);
while (unvisited.length > 0) {
// Start a loop-erased random walk from a random unvisited cell until we hit a visited one.
let cell = randSample(unvisited, rGen);
let path = [cell];
while (!visited[cell.row][cell.col]) {
cell = randSample(cell.adjacent.filter(Boolean), rGen);
const indexInPath = path.findIndex(
(p) => p.row === cell.row && p.col === cell.col
);
if (indexInPath === -1) {
path.push(cell);
} else {
path = path.slice(0, indexInPath + 1); // We've self-intersected, so erase the loop.
}
}
// Now that we have a valid path, connect cells and update visited/unvisited lists
for (let i = 0; i < path.length - 1; i++) {
path[i].link(path[i + 1]);
visited[path[i].row][path[i].col] = true;
}
unvisited = unvisited.filter((cell) => !visited[cell.row][cell.col]);
}
return grid;
}
function randomMST(grid, rGen) {
const g = toGraph(grid);
for (const e of g.serialize().links) {
g.setEdgeWeight(e.source, e.target, randInt(1000, rGen));
}
return g.mst();
}
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.
