Skip to content

Instantly share code, notes, and snippets.

@mbostock

mbostock/.block

Last active February 9, 2016 01:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save mbostock/bbd5e7e9c0e2575e4e18 to your computer and use it in GitHub Desktop.
Save mbostock/bbd5e7e9c0e2575e4e18 to your computer and use it in GitHub Desktop.
Download ZIP
Analyzing Spanning Trees
Raw
.block
license: gpl-3.0
Raw
.gitignore
.DS_Store
node_modules
Raw
README.md

These histograms show great-grandchildren counts for spanning trees generated by various algorithms. Randomized depth-first traversal has a strong tendency to generate long non-branching passages, where most nodes only have one child.

Raw
analyze-algorithms
#!/usr/bin/env node
var d3 = require("d3");
var direction = require("./direction");
var algorithms = {
"random-traversal": require("./random-traversal"),
"randomized-depth-first-traversal": require("./randomized-depth-first-traversal"),
"prims-algorithm": require("./prims-algorithm"),
"wilsons-algorithm": require("./wilsons-algorithm")
};
var width = 200,
height = 200,
size = width * height;
var results = d3.map(),
depth = 3,
breadth = 3 * depth;
for (var key in algorithms) {
results.set(key, d3.nest()
.key(countAncestors(depth))
.rollup(function(v) { return v.length; })
.map(generateTree(algorithms[key], width, height), d3.map));
}
console.log(d3.tsv.format(d3.keys(algorithms).map(function(key) {
var row = {name: key};
for (var i = 0; i < breadth; ++i) row[i] = (results.get(key).get(i) || 0) / size;
return row;
})));
function countAncestors(n) {
if (n === 1) return function(d) { return d.children.length; };
var countChildren = countAncestors(n - 1);
return function(d) { return d3.sum(d.children, countChildren); };
}
function generateTree(algorithm, width, height) {
var cells = algorithm(width, height), // each cell’s edge bits
visited = d3.range(width * height).map(function() { return false; }),
root = {index: cells.length - 1, children: []},
nodes = [root],
frontier = [root],
parent,
child,
childIndex,
cell;
while ((parent = frontier.pop()) != null) {
cell = cells[parent.index];
if (cell & direction.E && !visited[childIndex = parent.index + 1]) visit();
if (cell & direction.W && !visited[childIndex = parent.index - 1]) visit();
if (cell & direction.S && !visited[childIndex = parent.index + width]) visit();
if (cell & direction.N && !visited[childIndex = parent.index - width]) visit();
}
function visit() {
visited[childIndex] = true;
child = {index: childIndex, children: []};
parent.children.push(child);
frontier.push(child);
nodes.push(child);
}
return nodes;
}
Raw
direction.js
exports.N = 1 << 0;
exports.S = 1 << 1;
exports.W = 1 << 2;
exports.E = 1 << 3;
Raw
histogram.tsv
0 1 2 3 4 5 6 7 8 name
0.562025 0.1364 0.14125 0.09035 0.04715 0.016875 0.004975 0.00085 0.00015 random-traversal
0.190775 0.63785 0.153375 0.0169 0.00105 0.000075 0 0 0 randomized-depth-first-traversal
0.53955 0.15855 0.151175 0.09075 0.039825 0.01505 0.00395 0.00095 0.000225 prims-algorithm
0.517625 0.17845 0.164425 0.087575 0.034825 0.0131 0.003275 0.000625 0.000125 wilsons-algorithm
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
font: 10px sans-serif;
}
.axis line {
fill: none;
stroke: #000;
shape-rendering: crispEdges;
}
.axis path {
display: none;
}
.axis--y-inside line {
stroke: #fff;
stroke-opacity: 1;
}
.axis--y-inside .tick:first-of-type line {
stroke: #000;
}
.axis--y-inside text {
display: none;
}
.axis--x path {
display: none;
}
.title {
font-weight: bold;
}
rect {
fill: steelblue;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
var margin = {top: 20, right: 20, bottom: 30, left: 40},
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
var x = d3.scale.ordinal()
.domain(d3.range(9))
.rangeRoundBands([0, width], .1);
var y0 = d3.scale.ordinal()
.domain(["randomized-depth-first-traversal", "random-traversal", "prims-algorithm", "wilsons-algorithm"])
.rangeRoundBands([0, height], .15, 0);
var y1 = d3.scale.linear()
.domain([0, .65])
.range([y0.rangeBand(), 0]);
var color = d3.scale.category10();
var xAxis = d3.svg.axis()
.scale(x)
.orient("bottom");
var yAxis = d3.svg.axis()
.scale(y1)
.orient("left")
.ticks(4, "%");
var svg = d3.select("body").append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
svg.append("g")
.attr("class", "axis axis--x")
.attr("transform", "translate(0," + height + ")")
.call(xAxis);
var multiple = svg.selectAll(".multiple")
.data(y0.domain().map(function(d) { return {name: d}; }))
.enter().append("g")
.attr("class", "multiple")
.attr("transform", function(d) { return "translate(0," + y0(d.name) + ")"; });
multiple.append("g")
.attr("class", "axis axis--y axis--y-inside")
.call(yAxis.tickSize(-width));
multiple.append("g")
.attr("class", "axis axis--y axis--y-outside")
.call(yAxis.tickSize(6));
multiple.append("text")
.attr("class", "title")
.attr("transform", "translate(" + (width - 6) + "," + (y0.rangeBand() - 6) + ")")
.style("text-anchor", "end")
.text(function(d) { return d.name.replace(/-/g, " "); });
svg.select(".axis--y-outside").append("text")
.attr("x", 3)
.attr("y", y1(y1.ticks(4).pop()))
.attr("dy", ".35em")
.attr("class", "title")
.text("Probability");
d3.tsv("histogram.tsv", function(error, data) {
if (error) throw error;
multiple
.data(data, function(d) { return d.name; })
.selectAll("rect")
.data(function(d) { return x.domain().map(function(i) { return {key: i, value: +d[i]}; }); })
.enter().insert("rect", "*")
.attr("width", x.rangeBand())
.attr("x", function(d) { return x(d.key); })
.attr("y", function(d) { return y1(d.value); })
.attr("height", function(d) { return y0.rangeBand() - y1(d.value); });
});
</script>
Raw
Makefile
all: histogram.tsv
clean:
rm -f -- histogram.tsv
.PHONY: all clean
histogram.tsv: analyze-algorithms *.js
./analyze-algorithms > $@
Raw
package.json
{
"name": "anonymous",
"private": true,
"version": "0.0.1",
"dependencies": {
"d3": "3"
}
}
Raw
prims-algorithm.js
var direction = require("./direction");
module.exports = function(width, height) {
var cells = new Array(width * height),
frontier = minHeap(function(a, b) { return a.weight - b.weight; }),
startIndex = (height - 1) * width;
cells[startIndex] = 0;
frontier.push({index: startIndex, direction: direction.N, weight: Math.random()});
frontier.push({index: startIndex, direction: direction.E, weight: Math.random()});
while ((edge = frontier.pop()) != null) {
var edge,
i0 = edge.index,
d0 = edge.direction,
i1 = i0 + (d0 === direction.N ? -width : d0 === direction.S ? width : d0 === direction.W ? -1 : +1),
x0 = i0 % width,
y0 = i0 / width | 0,
x1,
y1,
d1,
open = cells[i1] == null; // opposite not yet part of the maze
if (d0 === direction.N) x1 = x0, y1 = y0 - 1, d1 = direction.S;
else if (d0 === direction.S) x1 = x0, y1 = y0 + 1, d1 = direction.N;
else if (d0 === direction.W) x1 = x0 - 1, y1 = y0, d1 = direction.E;
else x1 = x0 + 1, y1 = y0, d1 = direction.W;
if (open) {
cells[i0] |= d0, cells[i1] |= d1;
if (y1 > 0 && cells[i1 - width] == null) frontier.push({index: i1, direction: direction.N, weight: Math.random()});
if (y1 < height - 1 && cells[i1 + width] == null) frontier.push({index: i1, direction: direction.S, weight: Math.random()});
if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: direction.W, weight: Math.random()});
if (x1 < width - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: direction.E, weight: Math.random()});
}
}
return cells;
function minHeap(compare) {
var heap = {},
array = [],
size = 0;
heap.empty = function() {
return !size;
};
heap.push = function(value) {
up(array[size] = value, size++);
return size;
};
heap.pop = function() {
if (size <= 0) return;
var removed = array[0], value;
if (--size > 0) value = array[size], down(array[0] = value, 0);
return removed;
};
function up(value, i) {
while (i > 0) {
var j = ((i + 1) >> 1) - 1,
parent = array[j];
if (compare(value, parent) >= 0) break;
array[i] = parent;
array[i = j] = value;
}
}
function down(value, i) {
while (true) {
var r = (i + 1) << 1,
l = r - 1,
j = i,
child = array[j];
if (l < size && compare(array[l], child) < 0) child = array[j = l];
if (r < size && compare(array[r], child) < 0) child = array[j = r];
if (j === i) break;
array[i] = child;
array[i = j] = value;
}
}
return heap;
}
};
Raw
random-traversal.js
var direction = require("./direction");
module.exports = function(width, height) {
var cells = new Array(width * height),
frontier = [],
startIndex = (height - 1) * width;
cells[startIndex] = 0;
frontier.push({index: startIndex, direction: direction.N});
frontier.push({index: startIndex, direction: direction.E});
while ((edge = popRandom(frontier)) != null) {
var edge,
i0 = edge.index,
d0 = edge.direction,
i1 = i0 + (d0 === direction.N ? -width : d0 === direction.S ? width : d0 === direction.W ? -1 : +1),
x0 = i0 % width,
y0 = i0 / width | 0,
x1,
y1,
d1,
open = cells[i1] == null; // opposite not yet part of the maze
if (d0 === direction.N) x1 = x0, y1 = y0 - 1, d1 = direction.S;
else if (d0 === direction.S) x1 = x0, y1 = y0 + 1, d1 = direction.N;
else if (d0 === direction.W) x1 = x0 - 1, y1 = y0, d1 = direction.E;
else x1 = x0 + 1, y1 = y0, d1 = direction.W;
if (open) {
cells[i0] |= d0, cells[i1] |= d1;
if (y1 > 0 && cells[i1 - width] == null) frontier.push({index: i1, direction: direction.N});
if (y1 < height - 1 && cells[i1 + width] == null) frontier.push({index: i1, direction: direction.S});
if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: direction.W});
if (x1 < width - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: direction.E});
}
}
return cells;
function popRandom(array) {
if (!array.length) return;
var n = array.length, i = Math.random() * n | 0, t;
t = array[i], array[i] = array[n - 1], array[n - 1] = t;
return array.pop();
}
};
Raw
randomized-depth-first-traversal.js
var direction = require("./direction");
module.exports = function(width, height) {
var cells = new Array(width * height), // each cell’s edge bits
frontier = [];
var start = (height - 1) * width;
cells[start] = 0;
frontier.push({index: start, direction: direction.N});
frontier.push({index: start, direction: direction.E});
shuffle(frontier, 0, 2);
while (!exploreFrontier());
return cells;
function exploreFrontier() {
if ((edge = frontier.pop()) == null) return true;
var edge,
i0 = edge.index,
d0 = edge.direction,
i1 = i0 + (d0 === direction.N ? -width : d0 === direction.S ? width : d0 === direction.W ? -1 : +1),
x0 = i0 % width,
y0 = i0 / width | 0,
x1,
y1,
d1,
open = cells[i1] == null; // opposite not yet part of the maze
if (d0 === direction.N) x1 = x0, y1 = y0 - 1, d1 = direction.S;
else if (d0 === direction.S) x1 = x0, y1 = y0 + 1, d1 = direction.N;
else if (d0 === direction.W) x1 = x0 - 1, y1 = y0, d1 = direction.E;
else x1 = x0 + 1, y1 = y0, d1 = direction.W;
if (open) {
cells[i0] |= d0, cells[i1] |= d1;
var m = 0;
if (y1 > 0 && cells[i1 - width] == null) frontier.push({index: i1, direction: direction.N}), ++m;
if (y1 < height - 1 && cells[i1 + width] == null) frontier.push({index: i1, direction: direction.S}), ++m;
if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: direction.W}), ++m;
if (x1 < width - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: direction.E}), ++m;
shuffle(frontier, frontier.length - m, frontier.length);
}
}
function shuffle(array, i0, i1) {
var m = i1 - i0, t, i, j;
while (m) {
i = Math.random() * m-- | 0;
t = array[m + i0], array[m + i0] = array[i + i0], array[i + i0] = t;
}
return array;
}
};
Raw
wilsons-algorithm.js
var direction = require("./direction");
module.exports = function(width, height) {
var cells = new Array(width * height), // each cell’s edge bits
remaining = range(width * height), // cell indexes to visit
previous = new Array(width * height); // current random walk
// Add the starting cell.
var start = remaining.pop();
cells[start] = 0;
// While there are remaining cells,
// add a loop-erased random walk to the maze.
while (!loopErasedRandomWalk());
return cells;
function loopErasedRandomWalk() {
var i0,
i1,
x0,
y0;
// Pick a location that’s not yet in the maze (if any).
do if ((i0 = remaining.pop()) == null) return true;
while (cells[i0] >= 0);
// Perform a random walk starting at this location,
previous[i0] = i0;
while (true) {
x0 = i0 % width;
y0 = i0 / width | 0;
// picking a legal random direction at each step.
i1 = Math.random() * 4 | 0;
if (i1 === 0) { if (y0 <= 0) continue; --y0, i1 = i0 - width; }
else if (i1 === 1) { if (y0 >= height - 1) continue; ++y0, i1 = i0 + width; }
else if (i1 === 2) { if (x0 <= 0) continue; --x0, i1 = i0 - 1; }
else { if (x0 >= width - 1) continue; ++x0, i1 = i0 + 1; }
// If this new cell was visited previously during this walk,
// erase the loop, rewinding the path to its earlier state.
if (previous[i1] >= 0) eraseWalk(i0, i1);
// Otherwise, just add it to the walk.
else previous[i1] = i0;
// If this cell is part of the maze, we’re done walking.
if (cells[i1] >= 0) {
// Add the random walk to the maze by backtracking to the starting cell.
// Also erase this walk’s history to not interfere with subsequent walks.
while ((i0 = previous[i1]) !== i1) {
if (i1 === i0 + 1) cells[i0] |= direction.E, cells[i1] |= direction.W;
else if (i1 === i0 - 1) cells[i0] |= direction.W, cells[i1] |= direction.E;
else if (i1 === i0 + width) cells[i0] |= direction.S, cells[i1] |= direction.N;
else cells[i0] |= direction.N, cells[i1] |= direction.S;
previous[i1] = NaN;
i1 = i0;
}
previous[i1] = NaN;
return;
}
i0 = i1;
}
}
function eraseWalk(i0, i2) {
var i1;
do i1 = previous[i0], previous[i0] = NaN, i0 = i1; while (i1 !== i2);
}
function range(n) {
var array = new Array(n), i = -1;
while (++i < n) array[i] = i;
return array;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment