Avoid collision between nodes and edges in D3 force layout

Question

In this example: http://bl.ocks.org/mbostock/1747543:

...Mike shows us how to avoid collision among nodes so that no two nodes overlap each other.

I wonder if it is possible to avoid collision between nodes and edges so that no node 'clips' or overlaps an edge unless it is connected by that edge.

The following example using D3 force-direct shows that node L overlaps with the edge connecting I and A, and similarly, node M overlaps with the edge connecting L and D. How do we prevent such cases?

Sabu

This isn't possible with the force layout implementation in D3. You would need to implement this yourself. Note that this is actually a very hard problem (computationally), so even if you had an implementation it probably wouldn't want to run it in the browser. – Epigrammatize

@LarsKotthoff, are you saying, in general, no known graph layout algorithm (including the one implemented for D3) can efficiently solve this problem? – Sabu

That depends on your definition of efficiently. To find a (static) solution to this sounds at least NP-hard to me. This doesn't mean that it can be solved quickly at all in specific cases, but that's it's difficult in general (and for large graphs you probably can't do it quickly). To then change that initial solution such that the nodes would move slightly (as the simulation would do) would be very easy as you only need to do local repairs. – Epigrammatize

This is not a hard problem. Just add forces to the edges in addition to the nodes. If possible, simply increasing the size of the graph would help significantly. – Lauds

@tba, what exactly do you mean by adding forces to the edges? Increasing graph size is not very flexible because the area available for displaying the graph may be limited by the application. – Sabu

D3 visualizes the graph by using a physical simulation -- Nodes have the same "charge" and thus repel each other. In theory, we could adjust the simulation by adding "charge" to the edges as well. Unfortunately D3 doesn't support this out of the box. – Lauds

I am wondering if collision force can be used to nudge the nodes. github.com/d3/d3-force/blob/master/src/collide.js#L45-L47 in this code it calculuates distance between a node to another. It doesn't seem prohibitingly expensive to do simular for a node to a edge. I try see if I can implement that easily in my environment. I am totally new to D3 and this Q is fairly old. So not sure my comments are in line with the original Q though. – Valuer

Answer 1

If your graph doesn't have too many nodes, you can fake it. Just insert one or more nodes for each link, and set their position along the link in the tick handler. Check out http://bl.ocks.org/couchand/7190660 for an example, but the changes to Mike Bostock's version amount to basically just:

var linkNodes = [];

graph.links.forEach(function(link) {
  linkNodes.push({
    source: graph.nodes[link.source],
    target: graph.nodes[link.target]
  });
});

and

// force.on('tick', function() {
linkNodes.forEach(function(node) {
  node.x = (node.source.x + node.target.x) * 0.5;
  node.y = (node.source.y + node.target.y) * 0.5;
});

This will introduce a pretty serious performance overhead if you have very many nodes and edges, but if your graph doesn't get much larger than your example it would hardly be noticed.

You may also want to fiddle with the relative force of the real nodes versus the link nodes.

Take this one step further and you get the nice curved links of http://bl.ocks.org/mbostock/4600693.

Barefaced