A performance comparison of d3.forceManyBodyReuse()
in d3-force-reuse and the standard d3.forceManyBody()
in d3-force. d3.forceManyBodyReuse()
tends to perform faster than d3.forceManyBody()
, often with a total runtime of about 70% of that in d3.forceManyBody()
. It achieves this performance improvement by reusing Barnes-Hut approximations instead of calculating a new one at each tick of the algorithm. See d3-force-reuse and the research paper for more details:
Robert Gove. "It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster." Proceedings of Forum Media Technology, 2018. Preprint PDF.
Contains code from Mike Bostock's force-directed layout example and my KDE heatmap example.
forked from rpgove's block: d3-force-reuse crash [UNLISTED]
xxxxxxxxxx
<meta charset="utf-8">
<style>
svg {
overflow: visible;
}
text.runtime {
text-anchor: middle;
font-family: sans-serif;
font-weight: bold;
fill: #888;
font-size: 72px;
}
.links line {
stroke: #999;
stroke-opacity: 0.6;
}
.nodes circle {
stroke: #fff;
stroke-width: 1.5px;
}
</style>
<svg id="d3-force" width="400" height="400"></svg>
<svg id="d3-force-reuse" width="400" height="400"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="d3-force-reuse.js"></script>
<script>
var svg = d3.select("#d3-force").attr('transform', 'scale(0.75)'),
width = +svg.attr("width"),
height = +svg.attr("height");
var svgReuse = d3.select("#d3-force-reuse").attr('transform', 'scale(0.75)');
var runtime = svg.append('text')
.attr('class', 'runtime')
.attr('x', width/2)
.attr('y', height/4);
var runtimeReuse = svgReuse.append('text')
.attr('class', 'runtime')
.attr('x', width/2)
.attr('y', height/4);
var dispatch = d3.dispatch('tickend');
var computeTimes = [
{name: 'd3-force', values: []},
{name: 'd3-force-reuse', values: []}
];
var chartMargin = {top: 10, right: 20, bottom: 30, left: 50};
var chartWidth = 800 - chartMargin.left - chartMargin.right;
var chartHeight = 175 - chartMargin.top - chartMargin.bottom;
var x = d3.scaleLinear().rangeRound([0, chartWidth]);
var y = d3.scaleLinear().rangeRound([chartHeight, 0]);
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.i); })
.y(function (d) { return y(d.time); });
var simulation = d3.forceSimulation()
.force("link", d3.forceLink().id(function(d) { return d.id; }))
.force("charge", d3.forceManyBody())
.force("center", d3.forceCenter(width / 2, height / 2));
var simulationReuse = d3.forceSimulation()
.force("link", d3.forceLink().id(function(d) { return d.id; }))
.force("charge", d3.forceManyBodyReuse())
.force("center", d3.forceCenter(width / 2, height / 2));
d3.json("miserables.json", function(error, forceGraph) {
if (error) throw error;
d3.json("miserables.json", function(errorReuse, forceReuseGraph) {
if (errorReuse) throw errorReuse;
forceGraph.nodes.forEach((d,i)=> {
d.x = 100 //+i*1e-9;
d.y = 100 //+(i%3)*1e-9;
});
forceReuseGraph.nodes.forEach((d,i)=> {
d.x = 100 //+i*1e-9;
d.y = 100 //+(i%3)*1e-9;
});
// Setup d3-force
var link = svg.append("g")
.attr("class", "links")
.selectAll("line")
.data(forceGraph.links)
.enter().append("line")
.attr("stroke-width", function(d) { return Math.sqrt(d.value); });
var node = svg.append("g")
.attr("class", "nodes")
.selectAll("circle")
.data(forceGraph.nodes)
.enter().append("circle")
.attr("r", 5)
.attr("fill", 'steelblue');
node.append("title")
.text(function(d) { return d.id; });
simulation
.nodes(forceGraph.nodes)
.stop();
simulation.force("link")
.links(forceGraph.links);
// Setup d3-force-reuse
var linkReuse = svgReuse.append("g")
.attr("class", "links")
.selectAll("line")
.data(forceReuseGraph.links)
.enter().append("line")
.attr("stroke-width", function(d) { return Math.sqrt(d.value); });
var nodeReuse = svgReuse.append("g")
.attr("class", "nodes")
.selectAll("circle")
.data(forceReuseGraph.nodes)
.enter().append("circle")
.attr("r", 5)
.attr("fill", 'maroon');
nodeReuse.append("title")
.text(function(d) { return d.id; });
simulationReuse
.nodes(forceReuseGraph.nodes)
.stop();
simulationReuse.force("link")
.links(forceReuseGraph.links);
dispatch.on('tickend', function () {
drawGraph();
updateChart();
});
// Compute 300 ticks of each layout.
var i = 0;
var stepper = d3.timer(function () {
var prevTime = i > 0 ? computeTimes[0].values[i-1].time : 0;
var startTime = new Date();
simulation.tick();
var totalTime = new Date() - startTime;
computeTimes[0].values.push({i: i, time: totalTime + prevTime});
prevTime = i > 0 ? computeTimes[1].values[i-1].time : 0;
startTime = new Date();
simulationReuse.tick();
var totalTime = new Date() - startTime;
computeTimes[1].values.push({i: i, time: totalTime + prevTime});
dispatch.call('tickend', simulation);
++i;
if (i >= 300) {
stepper.stop();
}
});
function updateChart () {
var forceTime = computeTimes[0].values[computeTimes[0].values.length - 1].time;
var forceReuseTime = computeTimes[1].values[computeTimes[1].values.length - 1].time;
var percentTime = Math.round(100 * forceReuseTime / forceTime);
runtime.text(forceTime + ' ms');
runtimeReuse.text(forceReuseTime + ' ms (' + percentTime + '%)');
x.domain([0, computeTimes[0].values.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(' + 32 + ',' + 0 + ')')
.attr("y", 19)
.attr("dy", "0.71em")
.attr("text-anchor", "begin")
.text("Iteration");
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 === 'd3-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.i) + "," + 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 drawGraph () {
link
.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
node
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
linkReuse
.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
nodeReuse
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
}
});
});
</script>
https://d3js.org/d3.v4.min.js