D3 Examples - Random Vertex Sampling vs. Barnes-Hut Approximation

Random Vertex Sampling vs. Barnes-Hut Approximation

A performance comparison of d3.forceManyBodySampled() in d3-force-sampled and the standard d3.forceManyBody() in d3-force. d3.forceManyBodySampled() tends to perform 2-3x faster than d3.forceManyBody() on common graph sizes. It achieves this performance improvement by using the Random Vertex Sampling algorithm instead of the Barnes-Hut approximation, and therefore it achieves linear runtime and space complexity. See d3-force-sampled and the research paper for more details:

Robert Gove. "A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts." Computer Graphics Forum 38, 3 (2019). Preprint PDF.

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<style>
  body {
    font-family: Arial, "Helvetica Neue", Helvetica, sans-serif;
    background: white;
  }
​
  .container {
    width: 840px;
  }
​
  canvas {
    display: inline-block;
    margin: 10px;
  }
​
  svg {
    display: block;
    margin: auto;
  }
​
  text {
    font-size: 12px;
    fill: #333;
  }
​
  .axis text {
    font-weight: normal;
  }
​
  .sampled {
    fill: #d30000;
  }
​
  .bh {
    fill: #666;
  }
</style>
<body>
​
<div class="container">
  <canvas id="sampled" width="400" height="400"></canvas><canvas id="bh" width="400" height="400"></canvas>
  <svg width="400" height="70"></svg>
</div>
​
<script src="https://d3js.org/d3.v5.min.js"></script>
<script src="d3-force-sampled.js"></script>
<script>
​
var radius = 1;
var margin = {left: 150, right: 20, top: 0, bottom: 35};
​
d3.json('tvcg.json').then(function(graph) {
  graph.links.forEach(function (l) {
    l.source = graph.nodes[l.source];
    l.target = graph.nodes[l.target];
  })
​
  drawNetwork(graph, 'sampled', document.querySelector('#sampled'));
  drawNetwork(graph, 'bh', document.querySelector('#bh'));
​
  var timeData = ['sampled', 'bh'].map(function (d) {
    var mean = d3.mean(graph.time[d]);
    return { name: d, mean: mean };
  });
​
  var svg = d3.select('svg');
  var width = +svg.attr('width') - margin.left - margin.right;
  var height = +svg.attr('height') - margin.top - margin.bottom;
​
  var xScale = d3.scaleLinear()
    .domain([0, d3.max(timeData, function (d) { return d.mean; })])
    .range([0, width])
    .nice();
​
  var yScale = d3.scaleBand()
    .domain(timeData.map(function (d) { return d.name; }).reverse())
    .range([height, 0])
    .padding(0.4);
​
  svg = svg.append('g')
    .attr('transform', 'translate(' + margin.left + ',' + margin.top + ')');
​
  svg.selectAll('rect').data(timeData)
    .enter().append('rect')
    .attr('class', function (d) { return d.name; })
    .attr('width', function (d) { return xScale(d.mean); })
    .attr('height', function (d) { return yScale.bandwidth(); })
    .attr('x', 0)
    .attr('y', function (d) { return yScale(d.name); });
​
  svg.append('g')
    .attr('transform', 'translate(0,' + height + ')')
    .call(d3.axisBottom(xScale))
    .append("text")
    .attr("fill", "#000")
    .attr('transform', 'translate(0,0)')
    .attr("y", 21)
    .attr("dy", "0.71em")
    .attr("text-anchor", "start")
    .text("Mean runtime (seconds)");
​
  svg.append('g')
    .attr('transform', 'translate(0,' + 0 + ')')
    .call(d3.axisLeft(yScale).tickSizeOuter(0).tickFormat(function (d) {
      return displayName(d);
    }));
});
​
function drawNetwork (graph, simType, canvas) {
  var context = canvas.getContext('2d');
  var width = canvas.width;
  var height = canvas.height;
​
  var xScale = d3.scaleLinear()
    .range([radius, width - radius]);
  var yScale = d3.scaleLinear()
    .range([radius, height - radius]);
​
  // Adjust scales
  xScale.domain([
    d3.min(graph.nodes, function (d) { return Math.min(d[simType].x, d[simType].y); }),
    d3.max(graph.nodes, function (d) { return Math.max(d[simType].x, d[simType].y); })
  ]);
  yScale.domain([
    d3.min(graph.nodes, function (d) { return Math.min(d[simType].x, d[simType].y); }),
    d3.max(graph.nodes, function (d) { return Math.max(d[simType].x, d[simType].y); })
  ]);
​
  context.clearRect(0, 0, width, height);
  context.fillStyle = '#ffffff';
  context.fillRect(0, 0, width, height);
​
  context.font = '12px Arial';
  context.fillStyle = '#333';
  context.fillText(displayName(simType), 10, 10);
​
  // Draw links.
  context.strokeStyle = 'rgba(90, 90, 90, 0.30)';
  context.lineWidth = 1;
  graph.links.forEach(function(d) {
    context.beginPath();
    var pos = [xScale(d.source[simType].x), yScale(d.source[simType].y)];
    context.moveTo(pos[0], pos[1]);
    pos = [xScale(d.target[simType].x), yScale(d.target[simType].y)];
    context.lineTo(pos[0], pos[1]);
    context.stroke();
  });
​
  // Draw nodes.
  context.fillStyle = '#d30000';
  if (simType === 'bh')
    context.fillStyle = '#333';
  context.beginPath();
  graph.nodes.forEach(function(d) {
    var pos = [xScale(d[simType].x), yScale(d[simType].y)];
    context.moveTo(pos[0], pos[1]);
    context.arc(pos[0], pos[1], radius, 0, 2 * Math.PI);
  });
  context.fill();
}
​
function displayName (dataName) {
  return dataName === 'bh' ? 'Barnes-Hut' : 'Random Vertex Sampling';
}
​
</script>
    