mbostock/.block

## .block
license: gpl-3.0

## README.md

      
    Raw
  

              README.md
            
          
    Applying a tree layout on Prim’s algorithm.

  
## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>

.link {
  fill: none;
  stroke: #000;
  stroke-width: 1.5px;
}

</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var margin = {top: 20, right: 20, bottom: 20, left: 20},
    width = 960 - margin.left - margin.right,
    height = 500 - margin.top - margin.bottom;

var N = 1 << 0,
    S = 1 << 1,
    W = 1 << 2,
    E = 1 << 3;

var root = generateTree(40, 40);

var tree = d3.layout.tree()
    .size([height, width]);

var nodes = tree.nodes(root),
    links = tree.links(nodes);

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.selectAll(".link")
    .data(links)
  .enter().append("path")
    .attr("class", "link")
    .attr("d", function(d) { return "M" + d.source.y + "," + d.source.x + "L" + d.target.y + "," + d.target.x; });

function generateTree(width, height) {
  var cells = generateMaze(width, height), // each cell’s edge bits
      visited = d3.range(width * height).map(function() { return false; }),
      root = {index: cells.length - 1, children: []},
      frontier = [root],
      parent,
      child,
      childIndex,
      cell;

  while ((parent = frontier.pop()) != null) {
    cell = cells[parent.index];
    if (cell & E && !visited[childIndex = parent.index + 1]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
    if (cell & W && !visited[childIndex = parent.index - 1]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
    if (cell & S && !visited[childIndex = parent.index + width]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
    if (cell & N && !visited[childIndex = parent.index - width]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
  }

  return root;
}

function generateMaze(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: N, weight: Math.random()});
  frontier.push({index: startIndex, direction: E, weight: Math.random()});

  while ((edge = frontier.pop()) != null) {
    var edge,
        i0 = edge.index,
        d0 = edge.direction,
        i1 = i0 + (d0 === N ? -width : d0 === S ? width : d0 === 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 === N) x1 = x0, y1 = y0 - 1, d1 = S;
    else if (d0 === S) x1 = x0, y1 = y0 + 1, d1 = N;
    else if (d0 === W) x1 = x0 - 1, y1 = y0, d1 = E;
    else x1 = x0 + 1, y1 = y0, d1 = W;

    if (open) {
      cells[i0] |= d0, cells[i1] |= d1;
      if (y1 > 0 && cells[i1 - width] == null) frontier.push({index: i1, direction: N, weight: Math.random()});
      if (y1 < height - 1 && cells[i1 + width] == null) frontier.push({index: i1, direction: S, weight: Math.random()});
      if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W, weight: Math.random()});
      if (x1 < width - 1 && cells[i1 + 1] == null) frontier.push({index: i1, 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;
  }
}

</script>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

	.link {
	fill: none;
	stroke: #000;
	stroke-width: 1.5px;
	}

	</style>
	<body>
	<script src="//d3js.org/d3.v3.min.js"></script>
	<script>

	var margin = {top: 20, right: 20, bottom: 20, left: 20},
	width = 960 - margin.left - margin.right,
	height = 500 - margin.top - margin.bottom;

	var N = 1 << 0,
	S = 1 << 1,
	W = 1 << 2,
	E = 1 << 3;

	var root = generateTree(40, 40);

	var tree = d3.layout.tree()
	.size([height, width]);

	var nodes = tree.nodes(root),
	links = tree.links(nodes);

	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.selectAll(".link")
	.data(links)
	.enter().append("path")
	.attr("class", "link")
	.attr("d", function(d) { return "M" + d.source.y + "," + d.source.x + "L" + d.target.y + "," + d.target.x; });

	function generateTree(width, height) {
	var cells = generateMaze(width, height), // each cell’s edge bits
	visited = d3.range(width * height).map(function() { return false; }),
	root = {index: cells.length - 1, children: []},
	frontier = [root],
	parent,
	child,
	childIndex,
	cell;

	while ((parent = frontier.pop()) != null) {
	cell = cells[parent.index];
	if (cell & E && !visited[childIndex = parent.index + 1]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
	if (cell & W && !visited[childIndex = parent.index - 1]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
	if (cell & S && !visited[childIndex = parent.index + width]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
	if (cell & N && !visited[childIndex = parent.index - width]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
	}

	return root;
	}

	function generateMaze(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: N, weight: Math.random()});
	frontier.push({index: startIndex, direction: E, weight: Math.random()});

	while ((edge = frontier.pop()) != null) {
	var edge,
	i0 = edge.index,
	d0 = edge.direction,
	i1 = i0 + (d0 === N ? -width : d0 === S ? width : d0 === 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 === N) x1 = x0, y1 = y0 - 1, d1 = S;
	else if (d0 === S) x1 = x0, y1 = y0 + 1, d1 = N;
	else if (d0 === W) x1 = x0 - 1, y1 = y0, d1 = E;
	else x1 = x0 + 1, y1 = y0, d1 = W;

	if (open) {
	cells[i0] \|= d0, cells[i1] \|= d1;
	if (y1 > 0 && cells[i1 - width] == null) frontier.push({index: i1, direction: N, weight: Math.random()});
	if (y1 < height - 1 && cells[i1 + width] == null) frontier.push({index: i1, direction: S, weight: Math.random()});
	if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W, weight: Math.random()});
	if (x1 < width - 1 && cells[i1 + 1] == null) frontier.push({index: i1, 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;
	}
	}

	</script>