Skip to content

Instantly share code, notes, and snippets.

@rpgove
Last active April 21, 2019 23:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rpgove/28345b65a65753ecbabc3acbe30c3d70 to your computer and use it in GitHub Desktop.
Save rpgove/28345b65a65753ecbabc3acbe30c3d70 to your computer and use it in GitHub Desktop.
Random Vertex Sampling vs. Barnes-Hut Approximation
license: bsd-3-clause
height: 500

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.

// 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 });
})));
<!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>
// 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;
}
}
This file has been truncated, but you can view the full file.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment