D3 Examples - Link Collision Avoidance

Link Collision Avoidance

This is a really simple (and kind of cheap) way to ensure as little link overlap as possible in a force-directed graph. It is inspired by Moritz Stefaner's Force-based label placement, where he uses invisible nodes to avoid overlap of text labels.

In this example, I've taken the classic force-directed graph example of the Les Miserables dataset, and made two simple tweaks: I use the links array to calculate the invisible nodes, and place the nodes at the halfway point of each link. Conceptually, it is very similar to Mike Bostock's Curved Links.

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<style>
​
.node {
  stroke: #fff;
  stroke-width: 1.5px;
}
​
.link {
  stroke: #999;
  stroke-opacity: .6;
}
​
</style>
<body>
<script src="https://d3js.org/d3.v3.min.js"></script>
<script>
​
var width = 960,
    height = 700;
​
var color = d3.scale.category20();
​
var force = d3.layout.force()
    .charge(-120)
    .linkDistance(30)
    .size([width, height]);
​
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);
​
d3.json("miserables.json", function(error, graph) {
  force // tell force layout to use the links as the invisible nodes
      .nodes(graph.nodes.concat(graph.links)) 
      .links(graph.links)
      .start();
​
  var link = svg.selectAll(".link")
      .data(graph.links)
    .enter().append("line")
      .attr("class", "link")
      .style("stroke-width", function(d) { return Math.sqrt(d.value); });
​
  var node = svg.selectAll(".node")
      .data(graph.nodes)
    .enter().append("circle")
      .attr("class", "node")
      .attr("r", 5)
      .style("fill", function(d) { return color(d.group); })
      .call(force.drag);
​
  force.on("tick", function() {
    // place the invisible nodes at the halfway point of the link
    graph.links.forEach(function(d, i) {
      var x1 = d.source.x,
          x2 = d.target.x,
          y1 = d.source.y,
          y2 = d.target.y,
          slope = (y2 - y1) / (x2  - x1);
​
      d.x = (x2 + x1)/ 2;
      d.y = (x2 - x1) * slope / 2 + y1;
​
    });
​
    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; });
  });
});
​
</script>
    