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.

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

Modified http://d3js.org/d3.v3.min.js to a secure url

https://d3js.org/d3.v3.min.js