block by mbostock bbd5e7e9c0e2575e4e18

Analyzing Spanning Trees

Full Screen

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.

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>

Makefile

all: histogram.tsv

clean:
	rm -f -- histogram.tsv

.PHONY: all clean

histogram.tsv: analyze-algorithms *.js
	./analyze-algorithms > $@

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;
}

direction.js

exports.N = 1 << 0;
exports.S = 1 << 1;
exports.W = 1 << 2;
exports.E = 1 << 3;

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

package.json

{
  "name": "anonymous",
  "private": true,
  "version": "0.0.1",
  "dependencies": {
    "d3": "3"
  }
}

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;
  }
};

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();
  }
};

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;
  }
};

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;
  }
};