rpgove/.block

## .block
license: gpl-3.0
height: 500
scrolling: no
border: yes


## README.md

      
    Raw
  

              README.md
            
          
    Performance comparison of a brute force kernel density estimation (KDE) heatmap vs. a Barnes-Hut quadtree KDE heatmap.
This example creates an array of node positions at every tick of a force-directed algorithm. Then it generates two heatmaps from all of the collected node positions.
The Barnes-Hut approximation is markedly faster and looks the same when there are many points. When there is a very small number of points, the extra cost of constructing the quadtree makes the Barnes-Hut heatmap slower. But after just a few ticks, there are enough points that the Barnes-Hut heatmap is much, much faster.
In data visualization, the Barnes-Hut approximation is often used for speeding up force-directed graph layouts, but it has many other potential uses, such as this example here.
See also:

Heatmap of Force-Directed Graph Node Positions
Heatmap with 2D Kernel Density Estimation of Force Layout


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

body {
  background: #fff;
  font: 10px sans-serif;
  margin: 0;
}

.container {
  width: 945px;
  height: 315px;
}

.container div {
  display: inline-block;
  width: 315px;
  height: 315px;
  overflow: hidden;
}

.force svg {
  background: rgba(0,0,0,0);
  position: absolute;
  top: 0;
  left: 0;
}

p {
  color: black;
}

.container div p {
  font-size: 12px;
  font-weight: bold;
  text-align: center;
  margin: 0;
  position: relative;
  bottom: 25px;
}

.brute p {
  color: steelblue;
}

.barneshut p {
  color: maroon;
}

svg {
  background: #fff;
}

.node {
  fill: #555;
  stroke: #fff;
  stroke-width: 1px;
}

.link {
  stroke: #555;
  stroke-opacity: 0.6;
}

.point {
  fill: black;
}

</style>
<body>
<div class="container"><div class="force"><canvas></canvas><svg></svg><p>Graph layout node positions</p></div><div class="brute"><canvas></canvas><p>Brute force heatmap</p></div><div class="barneshut"><canvas></canvas><p>Barnes-Hut heatmap</p></div></div>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>

var kdeWidth = 315;
var kdeHeight = 315;

var chartMargin = {top: 10, right: 20, bottom: 30, left: 50};
var chartWidth = 945 - chartMargin.left - chartMargin.right;
var chartHeight = 175 - chartMargin.top - chartMargin.bottom;

var computeTimes = [
  {name: 'Brute force', values: []},
  {name: 'Barnes-Hut', values: []}
];

var gridSize = 9;

var xyPoints = [];
var qt = d3.quadtree()
  .extent([[0, 0], [kdeWidth, kdeHeight]])
  .visitAfter(accumulate);
var h, h2, iqr, xPoints;

// Array of grid cell points. Each point is the center of the grid cell.
var grid = d3.merge(d3.range(0, kdeHeight/gridSize).map(function(i) {
  return d3.range(0, kdeWidth/gridSize).map(function(j) { return [j*gridSize + gridSize/2, i*gridSize + gridSize/2] });
}));

var x = d3.scaleLinear().rangeRound([0, chartWidth]);
var y = d3.scaleLinear().rangeRound([chartHeight, 0]);

var outerScale = d3.scalePow()
    .exponent(0.4)
    .domain([0,1])
    .range([0,1]);
var heatmapColor = d3.scaleLinear()
    .clamp(true)
    .domain([0, 0.1111111111111111, 0.2222222222222222, 0.3333333333333333, 0.4444444444444444, 0.5555555555555555, 0.6666666666666666, 0.7777777777777777, 0.8888888888888888, 1])
    .range(["#fff", "#dadada", "#b9b9b9", "#9b9b9b", "#7f7e7e", "#646363", "#4a4a4a", "#313030", "#161616", "#000"]);

var force = d3.forceSimulation()
  .alphaDecay(0.03)
  .force('link', d3.forceLink().id(function(d, i) { return i; }).distance(10))
  .force('charge', d3.forceManyBody().strength(-40))
  .force('x', d3.forceX(kdeWidth/2))
  .force('y', d3.forceY(kdeHeight/2))
  .force('center', d3.forceCenter(kdeWidth/2, kdeHeight/2));

var tickCount = 0;

var forceSvg = d3.select(".force svg")
    .attr("width", kdeWidth)
    .attr("height", kdeHeight)
    .append("g");

var pointsContext = d3.select('.force canvas')
    .attr("width", kdeWidth)
    .attr("height", kdeHeight)
    .node()
    .getContext('2d');

var bruteCanvas = d3.select(".brute canvas")
    .attr('id', 'brute')
    .attr("width", kdeWidth)
    .attr("height", kdeHeight);

var barneshutCanvas = d3.select(".barneshut canvas")
    .attr('id', 'barneshut')
    .attr("width", kdeWidth)
    .attr("height", kdeHeight);

var chartSvg = d3.select("body").append("svg")
    .attr("width", chartWidth + chartMargin.left + chartMargin.right)
    .attr("height", chartHeight + chartMargin.top + chartMargin.bottom)
    .append('g')
    .attr("transform", "translate(" + chartMargin.left + "," + chartMargin.top + ")");

var line = d3.line()
    .x(function (d) { return x(d.numPoints); })
    .y(function (d) { return y(d.time); });

var bruteContext = bruteCanvas.node().getContext("2d");
var barneshutContext = barneshutCanvas.node().getContext("2d");

d3.json("miserables.json", function(error, graph) {
  if (error) throw error;

  var link = forceSvg.selectAll(".link")
      .data(graph.links)
    .enter().append("line")
      .attr("class", "link")
      .style("stroke-width", function(d) { return Math.sqrt(d.value); });

  var node = forceSvg.selectAll(".node")
      .data(graph.nodes)
    .enter().append("circle")
      .attr("class", "node")
      .attr("r", 3);

  point = forceSvg.selectAll('.point')
      .data(xyPoints)
    .enter().append('circle')
      .attr('class', 'point');

  node.append("title")
      .text(function(d) { return d.name; });

  force.nodes(graph.nodes)
    .on("end", function(event) {
      computeDensities();
      updateChart();
    })
    .on('tick', function(event) {
      link.attr("x1", function(d) { d.source.x = boundedCoords(d.source.x, kdeWidth); return d.source.x; })
          .attr("y1", function(d) { d.source.y = boundedCoords(d.source.y, kdeHeight); return d.source.y; })
          .attr("x2", function(d) { d.target.x = boundedCoords(d.target.x, kdeWidth); return d.target.x; })
          .attr("y2", function(d) { d.target.y = boundedCoords(d.target.y, kdeHeight); return d.target.y; });

      node.attr("cx", function(d) { d.x = boundedCoords(d.x, kdeWidth); return d.x; })
          .attr("cy", function(d) { d.y = boundedCoords(d.y, kdeHeight); return d.y; });

      // Track new node positions
      node.each(function(d) {
        xyPoints.push([d.x,d.y]);

        pointsContext.fillStyle = '#c9c9c9';
        pointsContext.beginPath();
        pointsContext.arc(d.x, d.y, 3, 0, 2*Math.PI);
        pointsContext.fill();
      });

      if (++tickCount == 50) {
        force.stop();
      }

      computeDensities();
      updateChart();
    });

  force.force('link')
    .links(graph.links);
});

function updateChart () {
  x.domain([0, xyPoints.length]);
  y.domain([0, d3.max(computeTimes, function (d) { return d3.max(d.values.map(function(v) { return v.time; })); })]);

  chartSvg.selectAll('g').remove();

  chartSvg.append('g')
      .attr('transform', 'translate(0,' + chartHeight + ')')
      .call(d3.axisBottom(x))
    .append("text")
      .attr("fill", "#000")
      .attr('transform', 'translate(' + chartMargin.left + ',' + 0 + ')')
      .attr("y", 19)
      .attr("dy", "0.71em")
      .attr("text-anchor", "begin")
      .text("Number of points");

  chartSvg.append('g')
      .call(d3.axisLeft(y))
    .append("text")
      .attr("fill", "#000")
      .attr("transform", "rotate(-90)")
      .attr("y", 6)
      .attr("dy", "0.71em")
      .attr("text-anchor", "end")
      .text("Compute time (ms)");

  var lineG = chartSvg.selectAll('g.line-g')
      .data(computeTimes)
    .enter().append('g')
      .attr('class', 'line-g');

  lineG.append('path')
      .attr("fill", "none")
      .attr("stroke", function (d) { return d.name === 'Brute force' ? 'steelblue' : 'maroon'; })
      .attr("stroke-linejoin", "round")
      .attr("stroke-linecap", "round")
      .attr("stroke-width", 1.5)
      .attr("d", function (d) { return line(d.values); });

  lineG.append("text")
      .datum(function(d) { return {name: d.name, value: d.values[d.values.length - 1]}; })
      .attr("transform", function(d) { return "translate(" + x(d.value.numPoints) + "," + y(d.value.time) + ")"; })
      .attr("x", 3)
      .attr('y', -6)
      .attr("dy", "0.35em")
      .attr('text-anchor', 'end')
      .style("font", "10px sans-serif")
      .text(function(d) { return d.name; });
}

function computeDensities () {
  // Density at each (x,y) coordinate in the grid
  var densities = [];
  var startTime;

  // Update bandwidth
  // Use same bandwidth for each dimension
  xPoints = xyPoints.map(function(d) { return d[0] }).sort(function(a,b) { return a - b });
  iqr = d3.quantile(xPoints, 0.75) - d3.quantile(xPoints, 0.25);
  h = 1.06 * Math.min(d3.deviation(xPoints), iqr / 1.34) * Math.pow(xyPoints.length, -0.2);
  h2 = h*h;

  // Compute KDE for each (x,y) pair and update the color scale
  startTime = new Date();
  densities = grid.map(function(point) { return kdeBrute(point); });
  computeTimes[0].values.push({numPoints: xyPoints.length, time: new Date() - startTime})
  outerScale.domain([0, d3.max(densities)]);
  drawHeatmap(bruteContext, densities);

  startTime = new Date();
  qt = d3.quadtree(xyPoints)
    .extent([[0, 0], [kdeWidth, kdeHeight]])
    .visitAfter(accumulate);
  densities = grid.map(function(point) { return kdeBarneshut(point); });
  computeTimes[1].values.push({numPoints: xyPoints.length, time: new Date() - startTime})
  outerScale.domain([0, d3.max(densities)]);
  drawHeatmap(barneshutContext, densities);
}

function drawHeatmap(context, densities) {
  // Draw the grid
  grid.forEach(function(point, idx) {
    context.beginPath();
    context.fillStyle = heatmapColor(outerScale(densities[idx]));
    // Subtract to get the corner of the grid cell
    context.rect(point[0] - gridSize/2, point[1] - gridSize/2, gridSize, gridSize);
    context.fill();
    context.closePath();
  });
}

function boundedCoords(pos, maxPos) {
  return Math.min(maxPos, Math.max(0, pos));
}

function accumulate(quad) {
  // Sum of x/y coordinates
  var sx = 0;
  var sy = 0;

  var count = 0, q;

  // This quadrant has children.
  if (quad.length) {
    var i = -1;
    var c;
    while (++i < 4) {
      c = quad[i];
      if (c == null) continue;
      count += c.count;
      sx += c.sx;
      sy += c.sy;
    }
  }

  // This is a leaf node.
  else {
    q = quad;
    do {
      count += 1;
      sx += q.data[0];
      sy += q.data[1];
    } while (q = q.next);
  }

  quad.sx = sx;
  quad.sy = sy;
  quad.count = count;
}

// Use same bandwidth for each dimension
function kdeBrute(gridPoint) {
  return d3.mean(xyPoints, function(p) { return gaussian(norm(p, gridPoint) / h) }) / h2;
}

function kdeBarneshut(gridPoint) {
  //return d3.mean(xyPoints, function(p) { return gaussian(norm(p, gridPoint) / h) }) / h2;
  var estimate = 0;
  var theta2 = 0.64;

  function recurse(quadNode, x1, y1, x2, y2) {
    // Average x/y coordinates in this quadrant.
    var p = [quadNode.sx/quadNode.count, quadNode.sy/quadNode.count];
    var dx = p[0] - gridPoint[0];
    var dy = p[1] - gridPoint[1];
    var dw = x2 - x1;
    var dist = dx * dx + dy * dy;

    // Barnes-Hut: If the quadrant size is small relative to its
    // distance from the grid point, then aggregate the points in
    // that quadrant and treat them as a single large point (or many
    // individual points all in the same location).
    if (dw * dw / theta2 < dist && !(gridPoint[0] >= x1 && gridPoint[0] < x2 && gridPoint[1] >= y1 && gridPoint[1] < y2)) {
      estimate += quadNode.count * gaussian(norm(p, gridPoint) / h);
      return true;
    }

    if (quadNode.point) {
      estimate += gaussian(norm(quadNode.point, gridPoint) / h);
    }

    // Stop recursing if there are no more nodes.
    return !quadNode.count;
  }

  qt.visit(recurse);

  return estimate / xyPoints.length;
}

// Norm of 2D arrays/vectors
function norm(v1, v2) {
  return Math.sqrt((v1[0] - v2[0]) * (v1[0] - v2[0]) + (v1[1] - v2[1]) * (v1[1] - v2[1]));
}

function gaussian(x) {
  // sqrt(2 * PI) is approximately 2.5066
  return Math.exp(-x * x / 2) / 2.5066;
}

</script>

## miserables.json
{
  "nodes":[
    {"name":"Myriel","group":1},
    {"name":"Napoleon","group":1},
    {"name":"Mlle.Baptistine","group":1},
    {"name":"Mme.Magloire","group":1},
    {"name":"CountessdeLo","group":1},
    {"name":"Geborand","group":1},
    {"name":"Champtercier","group":1},
    {"name":"Cravatte","group":1},
    {"name":"Count","group":1},
    {"name":"OldMan","group":1},
    {"name":"Labarre","group":2},
    {"name":"Valjean","group":2},
    {"name":"Marguerite","group":3},
    {"name":"Mme.deR","group":2},
    {"name":"Isabeau","group":2},
    {"name":"Gervais","group":2},
    {"name":"Tholomyes","group":3},
    {"name":"Listolier","group":3},
    {"name":"Fameuil","group":3},
    {"name":"Blacheville","group":3},
    {"name":"Favourite","group":3},
    {"name":"Dahlia","group":3},
    {"name":"Zephine","group":3},
    {"name":"Fantine","group":3},
    {"name":"Mme.Thenardier","group":4},
    {"name":"Thenardier","group":4},
    {"name":"Cosette","group":5},
    {"name":"Javert","group":4},
    {"name":"Fauchelevent","group":0},
    {"name":"Bamatabois","group":2},
    {"name":"Perpetue","group":3},
    {"name":"Simplice","group":2},
    {"name":"Scaufflaire","group":2},
    {"name":"Woman1","group":2},
    {"name":"Judge","group":2},
    {"name":"Champmathieu","group":2},
    {"name":"Brevet","group":2},
    {"name":"Chenildieu","group":2},
    {"name":"Cochepaille","group":2},
    {"name":"Pontmercy","group":4},
    {"name":"Boulatruelle","group":6},
    {"name":"Eponine","group":4},
    {"name":"Anzelma","group":4},
    {"name":"Woman2","group":5},
    {"name":"MotherInnocent","group":0},
    {"name":"Gribier","group":0},
    {"name":"Jondrette","group":7},
    {"name":"Mme.Burgon","group":7},
    {"name":"Gavroche","group":8},
    {"name":"Gillenormand","group":5},
    {"name":"Magnon","group":5},
    {"name":"Mlle.Gillenormand","group":5},
    {"name":"Mme.Pontmercy","group":5},
    {"name":"Mlle.Vaubois","group":5},
    {"name":"Lt.Gillenormand","group":5},
    {"name":"Marius","group":8},
    {"name":"BaronessT","group":5},
    {"name":"Mabeuf","group":8},
    {"name":"Enjolras","group":8},
    {"name":"Combeferre","group":8},
    {"name":"Prouvaire","group":8},
    {"name":"Feuilly","group":8},
    {"name":"Courfeyrac","group":8},
    {"name":"Bahorel","group":8},
    {"name":"Bossuet","group":8},
    {"name":"Joly","group":8},
    {"name":"Grantaire","group":8},
    {"name":"MotherPlutarch","group":9},
    {"name":"Gueulemer","group":4},
    {"name":"Babet","group":4},
    {"name":"Claquesous","group":4},
    {"name":"Montparnasse","group":4},
    {"name":"Toussaint","group":5},
    {"name":"Child1","group":10},
    {"name":"Child2","group":10},
    {"name":"Brujon","group":4},
    {"name":"Mme.Hucheloup","group":8}
  ],
  "links":[
    {"source":1,"target":0,"value":1},
    {"source":2,"target":0,"value":8},
    {"source":3,"target":0,"value":10},
    {"source":3,"target":2,"value":6},
    {"source":4,"target":0,"value":1},
    {"source":5,"target":0,"value":1},
    {"source":6,"target":0,"value":1},
    {"source":7,"target":0,"value":1},
    {"source":8,"target":0,"value":2},
    {"source":9,"target":0,"value":1},
    {"source":11,"target":10,"value":1},
    {"source":11,"target":3,"value":3},
    {"source":11,"target":2,"value":3},
    {"source":11,"target":0,"value":5},
    {"source":12,"target":11,"value":1},
    {"source":13,"target":11,"value":1},
    {"source":14,"target":11,"value":1},
    {"source":15,"target":11,"value":1},
    {"source":17,"target":16,"value":4},
    {"source":18,"target":16,"value":4},
    {"source":18,"target":17,"value":4},
    {"source":19,"target":16,"value":4},
    {"source":19,"target":17,"value":4},
    {"source":19,"target":18,"value":4},
    {"source":20,"target":16,"value":3},
    {"source":20,"target":17,"value":3},
    {"source":20,"target":18,"value":3},
    {"source":20,"target":19,"value":4},
    {"source":21,"target":16,"value":3},
    {"source":21,"target":17,"value":3},
    {"source":21,"target":18,"value":3},
    {"source":21,"target":19,"value":3},
    {"source":21,"target":20,"value":5},
    {"source":22,"target":16,"value":3},
    {"source":22,"target":17,"value":3},
    {"source":22,"target":18,"value":3},
    {"source":22,"target":19,"value":3},
    {"source":22,"target":20,"value":4},
    {"source":22,"target":21,"value":4},
    {"source":23,"target":16,"value":3},
    {"source":23,"target":17,"value":3},
    {"source":23,"target":18,"value":3},
    {"source":23,"target":19,"value":3},
    {"source":23,"target":20,"value":4},
    {"source":23,"target":21,"value":4},
    {"source":23,"target":22,"value":4},
    {"source":23,"target":12,"value":2},
    {"source":23,"target":11,"value":9},
    {"source":24,"target":23,"value":2},
    {"source":24,"target":11,"value":7},
    {"source":25,"target":24,"value":13},
    {"source":25,"target":23,"value":1},
    {"source":25,"target":11,"value":12},
    {"source":26,"target":24,"value":4},
    {"source":26,"target":11,"value":31},
    {"source":26,"target":16,"value":1},
    {"source":26,"target":25,"value":1},
    {"source":27,"target":11,"value":17},
    {"source":27,"target":23,"value":5},
    {"source":27,"target":25,"value":5},
    {"source":27,"target":24,"value":1},
    {"source":27,"target":26,"value":1},
    {"source":28,"target":11,"value":8},
    {"source":28,"target":27,"value":1},
    {"source":29,"target":23,"value":1},
    {"source":29,"target":27,"value":1},
    {"source":29,"target":11,"value":2},
    {"source":30,"target":23,"value":1},
    {"source":31,"target":30,"value":2},
    {"source":31,"target":11,"value":3},
    {"source":31,"target":23,"value":2},
    {"source":31,"target":27,"value":1},
    {"source":32,"target":11,"value":1},
    {"source":33,"target":11,"value":2},
    {"source":33,"target":27,"value":1},
    {"source":34,"target":11,"value":3},
    {"source":34,"target":29,"value":2},
    {"source":35,"target":11,"value":3},
    {"source":35,"target":34,"value":3},
    {"source":35,"target":29,"value":2},
    {"source":36,"target":34,"value":2},
    {"source":36,"target":35,"value":2},
    {"source":36,"target":11,"value":2},
    {"source":36,"target":29,"value":1},
    {"source":37,"target":34,"value":2},
    {"source":37,"target":35,"value":2},
    {"source":37,"target":36,"value":2},
    {"source":37,"target":11,"value":2},
    {"source":37,"target":29,"value":1},
    {"source":38,"target":34,"value":2},
    {"source":38,"target":35,"value":2},
    {"source":38,"target":36,"value":2},
    {"source":38,"target":37,"value":2},
    {"source":38,"target":11,"value":2},
    {"source":38,"target":29,"value":1},
    {"source":39,"target":25,"value":1},
    {"source":40,"target":25,"value":1},
    {"source":41,"target":24,"value":2},
    {"source":41,"target":25,"value":3},
    {"source":42,"target":41,"value":2},
    {"source":42,"target":25,"value":2},
    {"source":42,"target":24,"value":1},
    {"source":43,"target":11,"value":3},
    {"source":43,"target":26,"value":1},
    {"source":43,"target":27,"value":1},
    {"source":44,"target":28,"value":3},
    {"source":44,"target":11,"value":1},
    {"source":45,"target":28,"value":2},
    {"source":47,"target":46,"value":1},
    {"source":48,"target":47,"value":2},
    {"source":48,"target":25,"value":1},
    {"source":48,"target":27,"value":1},
    {"source":48,"target":11,"value":1},
    {"source":49,"target":26,"value":3},
    {"source":49,"target":11,"value":2},
    {"source":50,"target":49,"value":1},
    {"source":50,"target":24,"value":1},
    {"source":51,"target":49,"value":9},
    {"source":51,"target":26,"value":2},
    {"source":51,"target":11,"value":2},
    {"source":52,"target":51,"value":1},
    {"source":52,"target":39,"value":1},
    {"source":53,"target":51,"value":1},
    {"source":54,"target":51,"value":2},
    {"source":54,"target":49,"value":1},
    {"source":54,"target":26,"value":1},
    {"source":55,"target":51,"value":6},
    {"source":55,"target":49,"value":12},
    {"source":55,"target":39,"value":1},
    {"source":55,"target":54,"value":1},
    {"source":55,"target":26,"value":21},
    {"source":55,"target":11,"value":19},
    {"source":55,"target":16,"value":1},
    {"source":55,"target":25,"value":2},
    {"source":55,"target":41,"value":5},
    {"source":55,"target":48,"value":4},
    {"source":56,"target":49,"value":1},
    {"source":56,"target":55,"value":1},
    {"source":57,"target":55,"value":1},
    {"source":57,"target":41,"value":1},
    {"source":57,"target":48,"value":1},
    {"source":58,"target":55,"value":7},
    {"source":58,"target":48,"value":7},
    {"source":58,"target":27,"value":6},
    {"source":58,"target":57,"value":1},
    {"source":58,"target":11,"value":4},
    {"source":59,"target":58,"value":15},
    {"source":59,"target":55,"value":5},
    {"source":59,"target":48,"value":6},
    {"source":59,"target":57,"value":2},
    {"source":60,"target":48,"value":1},
    {"source":60,"target":58,"value":4},
    {"source":60,"target":59,"value":2},
    {"source":61,"target":48,"value":2},
    {"source":61,"target":58,"value":6},
    {"source":61,"target":60,"value":2},
    {"source":61,"target":59,"value":5},
    {"source":61,"target":57,"value":1},
    {"source":61,"target":55,"value":1},
    {"source":62,"target":55,"value":9},
    {"source":62,"target":58,"value":17},
    {"source":62,"target":59,"value":13},
    {"source":62,"target":48,"value":7},
    {"source":62,"target":57,"value":2},
    {"source":62,"target":41,"value":1},
    {"source":62,"target":61,"value":6},
    {"source":62,"target":60,"value":3},
    {"source":63,"target":59,"value":5},
    {"source":63,"target":48,"value":5},
    {"source":63,"target":62,"value":6},
    {"source":63,"target":57,"value":2},
    {"source":63,"target":58,"value":4},
    {"source":63,"target":61,"value":3},
    {"source":63,"target":60,"value":2},
    {"source":63,"target":55,"value":1},
    {"source":64,"target":55,"value":5},
    {"source":64,"target":62,"value":12},
    {"source":64,"target":48,"value":5},
    {"source":64,"target":63,"value":4},
    {"source":64,"target":58,"value":10},
    {"source":64,"target":61,"value":6},
    {"source":64,"target":60,"value":2},
    {"source":64,"target":59,"value":9},
    {"source":64,"target":57,"value":1},
    {"source":64,"target":11,"value":1},
    {"source":65,"target":63,"value":5},
    {"source":65,"target":64,"value":7},
    {"source":65,"target":48,"value":3},
    {"source":65,"target":62,"value":5},
    {"source":65,"target":58,"value":5},
    {"source":65,"target":61,"value":5},
    {"source":65,"target":60,"value":2},
    {"source":65,"target":59,"value":5},
    {"source":65,"target":57,"value":1},
    {"source":65,"target":55,"value":2},
    {"source":66,"target":64,"value":3},
    {"source":66,"target":58,"value":3},
    {"source":66,"target":59,"value":1},
    {"source":66,"target":62,"value":2},
    {"source":66,"target":65,"value":2},
    {"source":66,"target":48,"value":1},
    {"source":66,"target":63,"value":1},
    {"source":66,"target":61,"value":1},
    {"source":66,"target":60,"value":1},
    {"source":67,"target":57,"value":3},
    {"source":68,"target":25,"value":5},
    {"source":68,"target":11,"value":1},
    {"source":68,"target":24,"value":1},
    {"source":68,"target":27,"value":1},
    {"source":68,"target":48,"value":1},
    {"source":68,"target":41,"value":1},
    {"source":69,"target":25,"value":6},
    {"source":69,"target":68,"value":6},
    {"source":69,"target":11,"value":1},
    {"source":69,"target":24,"value":1},
    {"source":69,"target":27,"value":2},
    {"source":69,"target":48,"value":1},
    {"source":69,"target":41,"value":1},
    {"source":70,"target":25,"value":4},
    {"source":70,"target":69,"value":4},
    {"source":70,"target":68,"value":4},
    {"source":70,"target":11,"value":1},
    {"source":70,"target":24,"value":1},
    {"source":70,"target":27,"value":1},
    {"source":70,"target":41,"value":1},
    {"source":70,"target":58,"value":1},
    {"source":71,"target":27,"value":1},
    {"source":71,"target":69,"value":2},
    {"source":71,"target":68,"value":2},
    {"source":71,"target":70,"value":2},
    {"source":71,"target":11,"value":1},
    {"source":71,"target":48,"value":1},
    {"source":71,"target":41,"value":1},
    {"source":71,"target":25,"value":1},
    {"source":72,"target":26,"value":2},
    {"source":72,"target":27,"value":1},
    {"source":72,"target":11,"value":1},
    {"source":73,"target":48,"value":2},
    {"source":74,"target":48,"value":2},
    {"source":74,"target":73,"value":3},
    {"source":75,"target":69,"value":3},
    {"source":75,"target":68,"value":3},
    {"source":75,"target":25,"value":3},
    {"source":75,"target":48,"value":1},
    {"source":75,"target":41,"value":1},
    {"source":75,"target":70,"value":1},
    {"source":75,"target":71,"value":1},
    {"source":76,"target":64,"value":1},
    {"source":76,"target":65,"value":1},
    {"source":76,"target":66,"value":1},
    {"source":76,"target":63,"value":1},
    {"source":76,"target":62,"value":1},
    {"source":76,"target":48,"value":1},
    {"source":76,"target":58,"value":1}
  ]
}

## preview.png

      
    Raw
  

              preview.png
            
          
## thumbnail.png

      
    Raw
  

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

	body {
	background: #fff;
	font: 10px sans-serif;
	margin: 0;
	}

	.container {
	width: 945px;
	height: 315px;
	}

	.container div {
	display: inline-block;
	width: 315px;
	height: 315px;
	overflow: hidden;
	}

	.force svg {
	background: rgba(0,0,0,0);
	position: absolute;
	top: 0;
	left: 0;
	}

	p {
	color: black;
	}

	.container div p {
	font-size: 12px;
	font-weight: bold;
	text-align: center;
	margin: 0;
	position: relative;
	bottom: 25px;
	}

	.brute p {
	color: steelblue;
	}

	.barneshut p {
	color: maroon;
	}

	svg {
	background: #fff;
	}

	.node {
	fill: #555;
	stroke: #fff;
	stroke-width: 1px;
	}

	.link {
	stroke: #555;
	stroke-opacity: 0.6;
	}

	.point {
	fill: black;
	}

	</style>
	<body>
	<div class="container"><div class="force"><canvas></canvas><svg></svg><p>Graph layout node positions</p></div><div class="brute"><canvas></canvas><p>Brute force heatmap</p></div><div class="barneshut"><canvas></canvas><p>Barnes-Hut heatmap</p></div></div>
	<script src="https://d3js.org/d3.v4.min.js"></script>
	<script>

	var kdeWidth = 315;
	var kdeHeight = 315;

	var chartMargin = {top: 10, right: 20, bottom: 30, left: 50};
	var chartWidth = 945 - chartMargin.left - chartMargin.right;
	var chartHeight = 175 - chartMargin.top - chartMargin.bottom;

	var computeTimes = [
	{name: 'Brute force', values: []},
	{name: 'Barnes-Hut', values: []}
	];

	var gridSize = 9;

	var xyPoints = [];
	var qt = d3.quadtree()
	.extent([[0, 0], [kdeWidth, kdeHeight]])
	.visitAfter(accumulate);
	var h, h2, iqr, xPoints;

	// Array of grid cell points. Each point is the center of the grid cell.
	var grid = d3.merge(d3.range(0, kdeHeight/gridSize).map(function(i) {
	return d3.range(0, kdeWidth/gridSize).map(function(j) { return [jgridSize + gridSize/2, igridSize + gridSize/2] });
	}));

	var x = d3.scaleLinear().rangeRound([0, chartWidth]);
	var y = d3.scaleLinear().rangeRound([chartHeight, 0]);

	var outerScale = d3.scalePow()
	.exponent(0.4)
	.domain([0,1])
	.range([0,1]);
	var heatmapColor = d3.scaleLinear()
	.clamp(true)
	.domain([0, 0.1111111111111111, 0.2222222222222222, 0.3333333333333333, 0.4444444444444444, 0.5555555555555555, 0.6666666666666666, 0.7777777777777777, 0.8888888888888888, 1])
	.range(["#fff", "#dadada", "#b9b9b9", "#9b9b9b", "#7f7e7e", "#646363", "#4a4a4a", "#313030", "#161616", "#000"]);

	var force = d3.forceSimulation()
	.alphaDecay(0.03)
	.force('link', d3.forceLink().id(function(d, i) { return i; }).distance(10))
	.force('charge', d3.forceManyBody().strength(-40))
	.force('x', d3.forceX(kdeWidth/2))
	.force('y', d3.forceY(kdeHeight/2))
	.force('center', d3.forceCenter(kdeWidth/2, kdeHeight/2));

	var tickCount = 0;

	var forceSvg = d3.select(".force svg")
	.attr("width", kdeWidth)
	.attr("height", kdeHeight)
	.append("g");

	var pointsContext = d3.select('.force canvas')
	.attr("width", kdeWidth)
	.attr("height", kdeHeight)
	.node()
	.getContext('2d');

	var bruteCanvas = d3.select(".brute canvas")
	.attr('id', 'brute')
	.attr("width", kdeWidth)
	.attr("height", kdeHeight);

	var barneshutCanvas = d3.select(".barneshut canvas")
	.attr('id', 'barneshut')
	.attr("width", kdeWidth)
	.attr("height", kdeHeight);

	var chartSvg = d3.select("body").append("svg")
	.attr("width", chartWidth + chartMargin.left + chartMargin.right)
	.attr("height", chartHeight + chartMargin.top + chartMargin.bottom)
	.append('g')
	.attr("transform", "translate(" + chartMargin.left + "," + chartMargin.top + ")");

	var line = d3.line()
	.x(function (d) { return x(d.numPoints); })
	.y(function (d) { return y(d.time); });

	var bruteContext = bruteCanvas.node().getContext("2d");
	var barneshutContext = barneshutCanvas.node().getContext("2d");

	d3.json("miserables.json", function(error, graph) {
	if (error) throw error;

	var link = forceSvg.selectAll(".link")
	.data(graph.links)
	.enter().append("line")
	.attr("class", "link")
	.style("stroke-width", function(d) { return Math.sqrt(d.value); });

	var node = forceSvg.selectAll(".node")
	.data(graph.nodes)
	.enter().append("circle")
	.attr("class", "node")
	.attr("r", 3);

	point = forceSvg.selectAll('.point')
	.data(xyPoints)
	.enter().append('circle')
	.attr('class', 'point');

	node.append("title")
	.text(function(d) { return d.name; });

	force.nodes(graph.nodes)
	.on("end", function(event) {
	computeDensities();
	updateChart();
	})
	.on('tick', function(event) {
	link.attr("x1", function(d) { d.source.x = boundedCoords(d.source.x, kdeWidth); return d.source.x; })
	.attr("y1", function(d) { d.source.y = boundedCoords(d.source.y, kdeHeight); return d.source.y; })
	.attr("x2", function(d) { d.target.x = boundedCoords(d.target.x, kdeWidth); return d.target.x; })
	.attr("y2", function(d) { d.target.y = boundedCoords(d.target.y, kdeHeight); return d.target.y; });

	node.attr("cx", function(d) { d.x = boundedCoords(d.x, kdeWidth); return d.x; })
	.attr("cy", function(d) { d.y = boundedCoords(d.y, kdeHeight); return d.y; });

	// Track new node positions
	node.each(function(d) {
	xyPoints.push([d.x,d.y]);

	pointsContext.fillStyle = '#c9c9c9';
	pointsContext.beginPath();
	pointsContext.arc(d.x, d.y, 3, 0, 2*Math.PI);
	pointsContext.fill();
	});

	if (++tickCount == 50) {
	force.stop();
	}

	computeDensities();
	updateChart();
	});

	force.force('link')
	.links(graph.links);
	});

	function updateChart () {
	x.domain([0, xyPoints.length]);
	y.domain([0, d3.max(computeTimes, function (d) { return d3.max(d.values.map(function(v) { return v.time; })); })]);

	chartSvg.selectAll('g').remove();

	chartSvg.append('g')
	.attr('transform', 'translate(0,' + chartHeight + ')')
	.call(d3.axisBottom(x))
	.append("text")
	.attr("fill", "#000")
	.attr('transform', 'translate(' + chartMargin.left + ',' + 0 + ')')
	.attr("y", 19)
	.attr("dy", "0.71em")
	.attr("text-anchor", "begin")
	.text("Number of points");

	chartSvg.append('g')
	.call(d3.axisLeft(y))
	.append("text")
	.attr("fill", "#000")
	.attr("transform", "rotate(-90)")
	.attr("y", 6)
	.attr("dy", "0.71em")
	.attr("text-anchor", "end")
	.text("Compute time (ms)");

	var lineG = chartSvg.selectAll('g.line-g')
	.data(computeTimes)
	.enter().append('g')
	.attr('class', 'line-g');

	lineG.append('path')
	.attr("fill", "none")
	.attr("stroke", function (d) { return d.name === 'Brute force' ? 'steelblue' : 'maroon'; })
	.attr("stroke-linejoin", "round")
	.attr("stroke-linecap", "round")
	.attr("stroke-width", 1.5)
	.attr("d", function (d) { return line(d.values); });

	lineG.append("text")
	.datum(function(d) { return {name: d.name, value: d.values[d.values.length - 1]}; })
	.attr("transform", function(d) { return "translate(" + x(d.value.numPoints) + "," + y(d.value.time) + ")"; })
	.attr("x", 3)
	.attr('y', -6)
	.attr("dy", "0.35em")
	.attr('text-anchor', 'end')
	.style("font", "10px sans-serif")
	.text(function(d) { return d.name; });
	}

	function computeDensities () {
	// Density at each (x,y) coordinate in the grid
	var densities = [];
	var startTime;

	// Update bandwidth
	// Use same bandwidth for each dimension
	xPoints = xyPoints.map(function(d) { return d[0] }).sort(function(a,b) { return a - b });
	iqr = d3.quantile(xPoints, 0.75) - d3.quantile(xPoints, 0.25);
	h = 1.06 * Math.min(d3.deviation(xPoints), iqr / 1.34) * Math.pow(xyPoints.length, -0.2);
	h2 = h*h;

	// Compute KDE for each (x,y) pair and update the color scale
	startTime = new Date();
	densities = grid.map(function(point) { return kdeBrute(point); });
	computeTimes[0].values.push({numPoints: xyPoints.length, time: new Date() - startTime})
	outerScale.domain([0, d3.max(densities)]);
	drawHeatmap(bruteContext, densities);

	startTime = new Date();
	qt = d3.quadtree(xyPoints)
	.extent([[0, 0], [kdeWidth, kdeHeight]])
	.visitAfter(accumulate);
	densities = grid.map(function(point) { return kdeBarneshut(point); });
	computeTimes[1].values.push({numPoints: xyPoints.length, time: new Date() - startTime})
	outerScale.domain([0, d3.max(densities)]);
	drawHeatmap(barneshutContext, densities);
	}

	function drawHeatmap(context, densities) {
	// Draw the grid
	grid.forEach(function(point, idx) {
	context.beginPath();
	context.fillStyle = heatmapColor(outerScale(densities[idx]));
	// Subtract to get the corner of the grid cell
	context.rect(point[0] - gridSize/2, point[1] - gridSize/2, gridSize, gridSize);
	context.fill();
	context.closePath();
	});
	}

	function boundedCoords(pos, maxPos) {
	return Math.min(maxPos, Math.max(0, pos));
	}

	function accumulate(quad) {
	// Sum of x/y coordinates
	var sx = 0;
	var sy = 0;

	var count = 0, q;

	// This quadrant has children.
	if (quad.length) {
	var i = -1;
	var c;
	while (++i < 4) {
	c = quad[i];
	if (c == null) continue;
	count += c.count;
	sx += c.sx;
	sy += c.sy;
	}
	}

	// This is a leaf node.
	else {
	q = quad;
	do {
	count += 1;
	sx += q.data[0];
	sy += q.data[1];
	} while (q = q.next);
	}

	quad.sx = sx;
	quad.sy = sy;
	quad.count = count;
	}

	// Use same bandwidth for each dimension
	function kdeBrute(gridPoint) {
	return d3.mean(xyPoints, function(p) { return gaussian(norm(p, gridPoint) / h) }) / h2;
	}

	function kdeBarneshut(gridPoint) {
	//return d3.mean(xyPoints, function(p) { return gaussian(norm(p, gridPoint) / h) }) / h2;
	var estimate = 0;
	var theta2 = 0.64;

	function recurse(quadNode, x1, y1, x2, y2) {
	// Average x/y coordinates in this quadrant.
	var p = [quadNode.sx/quadNode.count, quadNode.sy/quadNode.count];
	var dx = p[0] - gridPoint[0];
	var dy = p[1] - gridPoint[1];
	var dw = x2 - x1;
	var dist = dx * dx + dy * dy;

	// Barnes-Hut: If the quadrant size is small relative to its
	// distance from the grid point, then aggregate the points in
	// that quadrant and treat them as a single large point (or many
	// individual points all in the same location).
	if (dw * dw / theta2 < dist && !(gridPoint[0] >= x1 && gridPoint[0] < x2 && gridPoint[1] >= y1 && gridPoint[1] < y2)) {
	estimate += quadNode.count * gaussian(norm(p, gridPoint) / h);
	return true;
	}

	if (quadNode.point) {
	estimate += gaussian(norm(quadNode.point, gridPoint) / h);
	}

	// Stop recursing if there are no more nodes.
	return !quadNode.count;
	}

	qt.visit(recurse);

	return estimate / xyPoints.length;
	}

	// Norm of 2D arrays/vectors
	function norm(v1, v2) {
	return Math.sqrt((v1[0] - v2[0]) * (v1[0] - v2[0]) + (v1[1] - v2[1]) * (v1[1] - v2[1]));
	}

	function gaussian(x) {
	// sqrt(2 * PI) is approximately 2.5066
	return Math.exp(-x * x / 2) / 2.5066;
	}

	</script>
	{
	"nodes":[
	{"name":"Myriel","group":1},
	{"name":"Napoleon","group":1},
	{"name":"Mlle.Baptistine","group":1},
	{"name":"Mme.Magloire","group":1},
	{"name":"CountessdeLo","group":1},
	{"name":"Geborand","group":1},
	{"name":"Champtercier","group":1},
	{"name":"Cravatte","group":1},
	{"name":"Count","group":1},
	{"name":"OldMan","group":1},
	{"name":"Labarre","group":2},
	{"name":"Valjean","group":2},
	{"name":"Marguerite","group":3},
	{"name":"Mme.deR","group":2},
	{"name":"Isabeau","group":2},
	{"name":"Gervais","group":2},
	{"name":"Tholomyes","group":3},
	{"name":"Listolier","group":3},
	{"name":"Fameuil","group":3},
	{"name":"Blacheville","group":3},
	{"name":"Favourite","group":3},
	{"name":"Dahlia","group":3},
	{"name":"Zephine","group":3},
	{"name":"Fantine","group":3},
	{"name":"Mme.Thenardier","group":4},
	{"name":"Thenardier","group":4},
	{"name":"Cosette","group":5},
	{"name":"Javert","group":4},
	{"name":"Fauchelevent","group":0},
	{"name":"Bamatabois","group":2},
	{"name":"Perpetue","group":3},
	{"name":"Simplice","group":2},
	{"name":"Scaufflaire","group":2},
	{"name":"Woman1","group":2},
	{"name":"Judge","group":2},
	{"name":"Champmathieu","group":2},
	{"name":"Brevet","group":2},
	{"name":"Chenildieu","group":2},
	{"name":"Cochepaille","group":2},
	{"name":"Pontmercy","group":4},
	{"name":"Boulatruelle","group":6},
	{"name":"Eponine","group":4},
	{"name":"Anzelma","group":4},
	{"name":"Woman2","group":5},
	{"name":"MotherInnocent","group":0},
	{"name":"Gribier","group":0},
	{"name":"Jondrette","group":7},
	{"name":"Mme.Burgon","group":7},
	{"name":"Gavroche","group":8},
	{"name":"Gillenormand","group":5},
	{"name":"Magnon","group":5},
	{"name":"Mlle.Gillenormand","group":5},
	{"name":"Mme.Pontmercy","group":5},
	{"name":"Mlle.Vaubois","group":5},
	{"name":"Lt.Gillenormand","group":5},
	{"name":"Marius","group":8},
	{"name":"BaronessT","group":5},
	{"name":"Mabeuf","group":8},
	{"name":"Enjolras","group":8},
	{"name":"Combeferre","group":8},
	{"name":"Prouvaire","group":8},
	{"name":"Feuilly","group":8},
	{"name":"Courfeyrac","group":8},
	{"name":"Bahorel","group":8},
	{"name":"Bossuet","group":8},
	{"name":"Joly","group":8},
	{"name":"Grantaire","group":8},
	{"name":"MotherPlutarch","group":9},
	{"name":"Gueulemer","group":4},
	{"name":"Babet","group":4},
	{"name":"Claquesous","group":4},
	{"name":"Montparnasse","group":4},
	{"name":"Toussaint","group":5},
	{"name":"Child1","group":10},
	{"name":"Child2","group":10},
	{"name":"Brujon","group":4},
	{"name":"Mme.Hucheloup","group":8}
	],
	"links":[
	{"source":1,"target":0,"value":1},
	{"source":2,"target":0,"value":8},
	{"source":3,"target":0,"value":10},
	{"source":3,"target":2,"value":6},
	{"source":4,"target":0,"value":1},
	{"source":5,"target":0,"value":1},
	{"source":6,"target":0,"value":1},
	{"source":7,"target":0,"value":1},
	{"source":8,"target":0,"value":2},
	{"source":9,"target":0,"value":1},
	{"source":11,"target":10,"value":1},
	{"source":11,"target":3,"value":3},
	{"source":11,"target":2,"value":3},
	{"source":11,"target":0,"value":5},
	{"source":12,"target":11,"value":1},
	{"source":13,"target":11,"value":1},
	{"source":14,"target":11,"value":1},
	{"source":15,"target":11,"value":1},
	{"source":17,"target":16,"value":4},
	{"source":18,"target":16,"value":4},
	{"source":18,"target":17,"value":4},
	{"source":19,"target":16,"value":4},
	{"source":19,"target":17,"value":4},
	{"source":19,"target":18,"value":4},
	{"source":20,"target":16,"value":3},
	{"source":20,"target":17,"value":3},
	{"source":20,"target":18,"value":3},
	{"source":20,"target":19,"value":4},
	{"source":21,"target":16,"value":3},
	{"source":21,"target":17,"value":3},
	{"source":21,"target":18,"value":3},
	{"source":21,"target":19,"value":3},
	{"source":21,"target":20,"value":5},
	{"source":22,"target":16,"value":3},
	{"source":22,"target":17,"value":3},
	{"source":22,"target":18,"value":3},
	{"source":22,"target":19,"value":3},
	{"source":22,"target":20,"value":4},
	{"source":22,"target":21,"value":4},
	{"source":23,"target":16,"value":3},
	{"source":23,"target":17,"value":3},
	{"source":23,"target":18,"value":3},
	{"source":23,"target":19,"value":3},
	{"source":23,"target":20,"value":4},
	{"source":23,"target":21,"value":4},
	{"source":23,"target":22,"value":4},
	{"source":23,"target":12,"value":2},
	{"source":23,"target":11,"value":9},
	{"source":24,"target":23,"value":2},
	{"source":24,"target":11,"value":7},
	{"source":25,"target":24,"value":13},
	{"source":25,"target":23,"value":1},
	{"source":25,"target":11,"value":12},
	{"source":26,"target":24,"value":4},
	{"source":26,"target":11,"value":31},
	{"source":26,"target":16,"value":1},
	{"source":26,"target":25,"value":1},
	{"source":27,"target":11,"value":17},
	{"source":27,"target":23,"value":5},
	{"source":27,"target":25,"value":5},
	{"source":27,"target":24,"value":1},
	{"source":27,"target":26,"value":1},
	{"source":28,"target":11,"value":8},
	{"source":28,"target":27,"value":1},
	{"source":29,"target":23,"value":1},
	{"source":29,"target":27,"value":1},
	{"source":29,"target":11,"value":2},
	{"source":30,"target":23,"value":1},
	{"source":31,"target":30,"value":2},
	{"source":31,"target":11,"value":3},
	{"source":31,"target":23,"value":2},
	{"source":31,"target":27,"value":1},
	{"source":32,"target":11,"value":1},
	{"source":33,"target":11,"value":2},
	{"source":33,"target":27,"value":1},
	{"source":34,"target":11,"value":3},
	{"source":34,"target":29,"value":2},
	{"source":35,"target":11,"value":3},
	{"source":35,"target":34,"value":3},
	{"source":35,"target":29,"value":2},
	{"source":36,"target":34,"value":2},
	{"source":36,"target":35,"value":2},
	{"source":36,"target":11,"value":2},
	{"source":36,"target":29,"value":1},
	{"source":37,"target":34,"value":2},
	{"source":37,"target":35,"value":2},
	{"source":37,"target":36,"value":2},
	{"source":37,"target":11,"value":2},
	{"source":37,"target":29,"value":1},
	{"source":38,"target":34,"value":2},
	{"source":38,"target":35,"value":2},
	{"source":38,"target":36,"value":2},
	{"source":38,"target":37,"value":2},
	{"source":38,"target":11,"value":2},
	{"source":38,"target":29,"value":1},
	{"source":39,"target":25,"value":1},
	{"source":40,"target":25,"value":1},
	{"source":41,"target":24,"value":2},
	{"source":41,"target":25,"value":3},
	{"source":42,"target":41,"value":2},
	{"source":42,"target":25,"value":2},
	{"source":42,"target":24,"value":1},
	{"source":43,"target":11,"value":3},
	{"source":43,"target":26,"value":1},
	{"source":43,"target":27,"value":1},
	{"source":44,"target":28,"value":3},
	{"source":44,"target":11,"value":1},
	{"source":45,"target":28,"value":2},
	{"source":47,"target":46,"value":1},
	{"source":48,"target":47,"value":2},
	{"source":48,"target":25,"value":1},
	{"source":48,"target":27,"value":1},
	{"source":48,"target":11,"value":1},
	{"source":49,"target":26,"value":3},
	{"source":49,"target":11,"value":2},
	{"source":50,"target":49,"value":1},
	{"source":50,"target":24,"value":1},
	{"source":51,"target":49,"value":9},
	{"source":51,"target":26,"value":2},
	{"source":51,"target":11,"value":2},
	{"source":52,"target":51,"value":1},
	{"source":52,"target":39,"value":1},
	{"source":53,"target":51,"value":1},
	{"source":54,"target":51,"value":2},
	{"source":54,"target":49,"value":1},
	{"source":54,"target":26,"value":1},
	{"source":55,"target":51,"value":6},
	{"source":55,"target":49,"value":12},
	{"source":55,"target":39,"value":1},
	{"source":55,"target":54,"value":1},
	{"source":55,"target":26,"value":21},
	{"source":55,"target":11,"value":19},
	{"source":55,"target":16,"value":1},
	{"source":55,"target":25,"value":2},
	{"source":55,"target":41,"value":5},
	{"source":55,"target":48,"value":4},
	{"source":56,"target":49,"value":1},
	{"source":56,"target":55,"value":1},
	{"source":57,"target":55,"value":1},
	{"source":57,"target":41,"value":1},
	{"source":57,"target":48,"value":1},
	{"source":58,"target":55,"value":7},
	{"source":58,"target":48,"value":7},
	{"source":58,"target":27,"value":6},
	{"source":58,"target":57,"value":1},
	{"source":58,"target":11,"value":4},
	{"source":59,"target":58,"value":15},
	{"source":59,"target":55,"value":5},
	{"source":59,"target":48,"value":6},
	{"source":59,"target":57,"value":2},
	{"source":60,"target":48,"value":1},
	{"source":60,"target":58,"value":4},
	{"source":60,"target":59,"value":2},
	{"source":61,"target":48,"value":2},
	{"source":61,"target":58,"value":6},
	{"source":61,"target":60,"value":2},
	{"source":61,"target":59,"value":5},
	{"source":61,"target":57,"value":1},
	{"source":61,"target":55,"value":1},
	{"source":62,"target":55,"value":9},
	{"source":62,"target":58,"value":17},
	{"source":62,"target":59,"value":13},
	{"source":62,"target":48,"value":7},
	{"source":62,"target":57,"value":2},
	{"source":62,"target":41,"value":1},
	{"source":62,"target":61,"value":6},
	{"source":62,"target":60,"value":3},
	{"source":63,"target":59,"value":5},
	{"source":63,"target":48,"value":5},
	{"source":63,"target":62,"value":6},
	{"source":63,"target":57,"value":2},
	{"source":63,"target":58,"value":4},
	{"source":63,"target":61,"value":3},
	{"source":63,"target":60,"value":2},
	{"source":63,"target":55,"value":1},
	{"source":64,"target":55,"value":5},
	{"source":64,"target":62,"value":12},
	{"source":64,"target":48,"value":5},
	{"source":64,"target":63,"value":4},
	{"source":64,"target":58,"value":10},
	{"source":64,"target":61,"value":6},
	{"source":64,"target":60,"value":2},
	{"source":64,"target":59,"value":9},
	{"source":64,"target":57,"value":1},
	{"source":64,"target":11,"value":1},
	{"source":65,"target":63,"value":5},
	{"source":65,"target":64,"value":7},
	{"source":65,"target":48,"value":3},
	{"source":65,"target":62,"value":5},
	{"source":65,"target":58,"value":5},
	{"source":65,"target":61,"value":5},
	{"source":65,"target":60,"value":2},
	{"source":65,"target":59,"value":5},
	{"source":65,"target":57,"value":1},
	{"source":65,"target":55,"value":2},
	{"source":66,"target":64,"value":3},
	{"source":66,"target":58,"value":3},
	{"source":66,"target":59,"value":1},
	{"source":66,"target":62,"value":2},
	{"source":66,"target":65,"value":2},
	{"source":66,"target":48,"value":1},
	{"source":66,"target":63,"value":1},
	{"source":66,"target":61,"value":1},
	{"source":66,"target":60,"value":1},
	{"source":67,"target":57,"value":3},
	{"source":68,"target":25,"value":5},
	{"source":68,"target":11,"value":1},
	{"source":68,"target":24,"value":1},
	{"source":68,"target":27,"value":1},
	{"source":68,"target":48,"value":1},
	{"source":68,"target":41,"value":1},
	{"source":69,"target":25,"value":6},
	{"source":69,"target":68,"value":6},
	{"source":69,"target":11,"value":1},
	{"source":69,"target":24,"value":1},
	{"source":69,"target":27,"value":2},
	{"source":69,"target":48,"value":1},
	{"source":69,"target":41,"value":1},
	{"source":70,"target":25,"value":4},
	{"source":70,"target":69,"value":4},
	{"source":70,"target":68,"value":4},
	{"source":70,"target":11,"value":1},
	{"source":70,"target":24,"value":1},
	{"source":70,"target":27,"value":1},
	{"source":70,"target":41,"value":1},
	{"source":70,"target":58,"value":1},
	{"source":71,"target":27,"value":1},
	{"source":71,"target":69,"value":2},
	{"source":71,"target":68,"value":2},
	{"source":71,"target":70,"value":2},
	{"source":71,"target":11,"value":1},
	{"source":71,"target":48,"value":1},
	{"source":71,"target":41,"value":1},
	{"source":71,"target":25,"value":1},
	{"source":72,"target":26,"value":2},
	{"source":72,"target":27,"value":1},
	{"source":72,"target":11,"value":1},
	{"source":73,"target":48,"value":2},
	{"source":74,"target":48,"value":2},
	{"source":74,"target":73,"value":3},
	{"source":75,"target":69,"value":3},
	{"source":75,"target":68,"value":3},
	{"source":75,"target":25,"value":3},
	{"source":75,"target":48,"value":1},
	{"source":75,"target":41,"value":1},
	{"source":75,"target":70,"value":1},
	{"source":75,"target":71,"value":1},
	{"source":76,"target":64,"value":1},
	{"source":76,"target":65,"value":1},
	{"source":76,"target":66,"value":1},
	{"source":76,"target":63,"value":1},
	{"source":76,"target":62,"value":1},
	{"source":76,"target":48,"value":1},
	{"source":76,"target":58,"value":1}
	]
	}