block by rpgove 28345b65a65753ecbabc3acbe30c3d70

Random Vertex Sampling vs. Barnes-Hut Approximation

Full Screen

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.

index.html

<!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>

d3-force-sampled.js

// Copyright 2019 Two Six Labs, LLC. v1.0.0 d3-force-sampled https://github.com/twosixlabs/d3-force-sampled/
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
typeof define === 'function' && define.amd ? define(['exports'], factory) :
(factory((global.d3 = global.d3 || {})));
}(this, (function (exports) { 'use strict';

function constant(x) {
  return function() {
    return x;
  };
}

function manyBodySampled() {
  var nodes,
      alpha,
      strength = constant(-30),
      strengths,
      indicesRepulse,
      prevIndex = 0,
      distanceMin2 = 1,
      distanceMax2 = Infinity,
      neighborSize = function () {
        return 15;
      },
      updateSize = function (nodes) { return Math.pow(nodes.length, 0.75); },
      sampleSize = function (nodes) { return Math.pow(nodes.length, 0.25); },
      numNeighbors,
      numUpdate,
      numSamples,
      chargeMultiplier = function (nodes) {
        return nodes.length < 100 ? 1 : nodes.length < 200 ? 3 : Math.sqrt(nodes.length);
      },
      cMult,
      rand = Math.random;

  function addRandomNode(node) {
    var randIdx = Math.floor(rand() * nodes.length),
        randNode = nodes[randIdx],
        randDist = (node.x - randNode.x) * (node.x - randNode.x) + (node.y - randNode.y) * (node.y - randNode.y),
        currIdx,
        currNode,
        currDist,
        maxI,
        maxDist = -Infinity,
        i = -1;

    // Is this already in the list?
    if (node.nearest.indexOf(randIdx) >= 0) return;

    // If there is room for another, add it.
    if (node.nearest.length < numNeighbors) {
      node.nearest.push(randIdx);
      return;
    }

    // Replace the farthest away "neighbor" with the new node.
    while (++i < node.nearest.length) {
      currIdx = node.nearest[i];
      currNode = nodes[currIdx];
      currDist = Math.hypot(node.x - currNode.x, node.y - currNode.y);
      if (currDist > maxDist) {
        maxI = i;
        maxDist = currDist;
      }
    }

    if (randDist < maxDist) {
      node.nearest[maxI] = randIdx;
    }
  }

  function getRandIndices(indices, num) {
    num = Math.floor(num);
    var i,
        n = nodes.length,
        cnt = n - num,
        randIdx,
        temp;

    // Choose random indices.
    for (i = n-1; i >= cnt; --i) {
      randIdx = Math.floor(rand() * i);
      temp = indices[randIdx];
      indices[randIdx] = indices[i];
      indices[i] = temp;
    }

    return indices.slice(cnt);
  }

  function approxRepulse(node) {
    var i,
        randIndices,
        currNode,
        w,
        x,
        y,
        l;

    // Choose random nodes to update.
    randIndices = getRandIndices(indicesRepulse, numSamples);

    for (i = randIndices.length - 1; i >= 0; --i) {
      currNode = nodes[randIndices[i]];

      if (currNode === node) continue;

      x = currNode.x - node.x;
      y = currNode.y - node.y;
      l = x * x + y * y;

      if (l >= distanceMax2) continue;

      // Limit forces for very close nodes; randomize direction if coincident.
      if (x === 0) x = (rand() - 0.5) * 1e-6, l += x * x;
      if (y === 0) y = (rand() - 0.5) * 1e-6, l += y * y;
      if (l < distanceMin2) l = Math.sqrt(distanceMin2 * l);

      w = strengths[node.index] * alpha * cMult / l;
      node.vx += x * w;
      node.vy += y * w;
    }
  }

  function constantRepulse(node) {
    var i,
        nearest,
        currNode,
        w,
        x,
        y,
        l;

    // Update the list of nearest nodes.
    if (numNeighbors) addRandomNode(node);

    nearest = node.nearest;

    if (numNeighbors) for (i = nearest.length - 1; i >= 0; --i) {
      currNode = nodes[nearest[i]];

      if (currNode === node) continue;

      x = currNode.x - node.x;
      y = currNode.y - node.y;
      l = x * x + y * y;

      if (l >= distanceMax2) continue;

      // Limit forces for very close nodes; randomize direction if coincident.
      if (x === 0) x = (rand() - 0.5) * 1e-6, l += x * x;
      if (y === 0) y = (rand() - 0.5) * 1e-6, l += y * y;
      if (l < distanceMin2) l = Math.sqrt(distanceMin2 * l);

      w = strengths[node.index] * alpha * cMult / l;
      node.vx += x * w;
      node.vy += y * w;
    }
  }

  function force(_) {
    var i = 0, j = prevIndex, n = nodes.length, upperIndex = prevIndex + numUpdate;
    for (alpha = _; i < n || j < upperIndex; ++i, ++j) {
      if (j < upperIndex) approxRepulse(nodes[j%n]);
      if (numNeighbors && i < n) constantRepulse(nodes[i]);
    }
    prevIndex = upperIndex % n;
  }

  function initialize() {
    if (!nodes) return;
    var i, n = nodes.length, node;
    indicesRepulse = new Array(n);
    for (i = 0; i < n; ++i) indicesRepulse[i] = i;
    strengths = new Array(n);
    
    // Cannot be negative.
    numNeighbors = Math.min(Math.ceil(neighborSize(nodes)), n);
    numNeighbors = numNeighbors < 0 ? 0 : Math.min(numNeighbors, nodes.length);
    numUpdate = Math.ceil(updateSize(nodes));
    numUpdate = numUpdate < 0 ? 0 : Math.min(numUpdate, n);
    numSamples = Math.ceil(sampleSize(nodes));
    numSamples = numSamples < 0 ? 0 : Math.min(numSamples, n);

    cMult = chargeMultiplier(nodes);

    alpha = 1;
    for (i = 0; i < n; ++i) {
      node = nodes[i];
      strengths[node.index] = +strength(node, i, nodes);
      node.nearest = [];
      while (node.nearest.length < numNeighbors) addRandomNode(node);
    }
  }

  force.initialize = function(_) {
    nodes = _;
    initialize();
  };

  force.strength = function(_) {
    return arguments.length ? (strength = typeof _ === "function" ? _ : constant(+_), initialize(), force) : strength;
  };

  force.distanceMin = function(_) {
    return arguments.length ? (distanceMin2 = _ * _, force) : Math.sqrt(distanceMin2);
  };

  force.distanceMax = function(_) {
    return arguments.length ? (distanceMax2 = _ * _, force) : Math.sqrt(distanceMax2);
  };

  force.neighborSize = function(_) {
    return arguments.length ? (neighborSize = typeof _ === "function" ? _ : constant(+_), initialize(), force) : neighborSize;
  };

  force.updateSize = function(_) {
    return arguments.length ? (updateSize = typeof _ === "function" ? _ : constant(+_), initialize(), force) : updateSize;
  };

  force.sampleSize = function(_) {
    return arguments.length ? (sampleSize = typeof _ === "function" ? _ : constant(+_), initialize(), force) : sampleSize;
  };

  force.chargeMultiplier = function(_) {
    return arguments.length ? (chargeMultiplier = typeof _ === "function" ? _ : constant(+_), initialize(), force) : chargeMultiplier;
  };

  force.source = function(_) {
    return arguments.length ? (rand = _, force) : rand;
  };

  return force;
}

exports.forceManyBodySampled = manyBodySampled;

Object.defineProperty(exports, '__esModule', { value: true });

})));

layout.js

// layout.js

const fs = require('fs');
const d3 = require('./d3.v5.js');
const manyBodySampled = require('./d3-force-sampled.js');

const NS_PER_SEC = 1e9;

var s, f, simType, i, sim, t, jsonString, jsonObj, startTime, totalTime;
var numSamples = 20; // Number of layouts per graph
var numTicks = 300;

var barnesHutSim = function barnesHutSim (nodes, links) {
  var simulation = d3.forceSimulation()
    .force('link', d3.forceLink().id(function(d,i) { return d.id; }))
    .force('charge', d3.forceManyBody())
    .force('forceX', d3.forceX().strength(0.001))
    .force('forceY', d3.forceY().strength(0.001))
    .force('center', d3.forceCenter(0,0))
    .alpha(1)
    .nodes(nodes)
    .stop();
  simulation.force('link').links(links);

  return simulation;
};

var sampledSim = function sampledSim (nodes, links) {
  var simulation = d3.forceSimulation()
    .force('charge', manyBodySampled.forceManyBodySampled())
    .force('link', d3.forceLink().id(function(d,i) { return d.id; }))
    .force('forceX', d3.forceX().strength(0.001))
    .force('forceY', d3.forceY().strength(0.001))
    .force('center', d3.forceCenter(0,0))
    .velocityDecay(0.2)
    .alpha(1)
    .nodes(nodes)
    .stop();
  simulation.force('link').links(links);

  return simulation;
};



var simulations = [sampledSim, barnesHutSim];
var time = {};

simulations.forEach(function (s) {
  time[getSimName(s)] = [];
});

jsonString = fs.readFileSync('tvcg.json', 'utf8');
jsonObj = JSON.parse(jsonString);

for (s = 0; s < simulations.length; ++s) {
  simType = simulations[s];

  for (i = 0; i < numSamples; ++i) {

    sim = simType(jsonObj.nodes, jsonObj.links);

    startTime = process.hrtime();
    for (t = 0; t < numTicks; ++t) {
      sim.tick();
    }
    totalTime = process.hrtime(startTime);

    time[getSimName(simType)].push(totalTime[0] + totalTime[1] / NS_PER_SEC);

    if (i === numSamples - 1) {
      jsonObj.nodes.forEach(function (n) {
        n[getSimName(simType)] = {};
        n[getSimName(simType)].x = n.x;
        n[getSimName(simType)].y = n.y;
      });
    }

    resetNodes(jsonObj.nodes);
  }
}

jsonObj.time = time;

jsonObj.links.forEach(function (l) {
  l.source = l.source.id;
  l.target = l.target.id;
});

jsonString = JSON.stringify(jsonObj);

fs.writeFile('tvcg.json', jsonString, 'utf8', function (err) {/* no op */});

function getSimName (s) {
  if (s.name === 'sampledSim')
    return 'sampled';
  return 'bh';
}

function resetNodes (nodes) {
  var i = 0, n = nodes.length, node;

  for (; i < n; ++i) {
    node = nodes[i];
    delete node.x;
    delete node.y;
    delete node.vx;
    delete node.vy;
  }
}