D3: Force Layout with fixed Y ranges - Reducing link overlap

Question

I have created a graph where each node fits into one of the fixed y ranges. I am using a force layout to display the graph but I don't know how to ensure that the minimum of crossed links occurs - some crossing will be inevitable. I think it is a combination of gravity, force, linkDistance etc. but none of my changes seem to work

The graph is located at: http://plnkr.co/edit/wyWjk37mkDCWcwpZvzxe?p=preview

The ideal configuration is

But it often comes out as a mess:

Any thoughts would be really appreciated

Answer 1

Take a look at this example.

This is your example, but a little bit modified. The basic idea is to do forced layout in two passes:

• first will allow a little bit more relaxed way of layout: nodes will be allowed to deviate from their "level"; this will allow spontaneous jumping one over another to achieve better link layout (less intersection)
• second will "return" nodes to their respective level

Key portions of the code:

Custom force:

  graph.nodes.forEach(function(o, i) {
    o.y += (y(o.level) - o.y) * k; 
  });

Layout definition:

  var force = d3.layout.force()
    .charge(-1000)
    .gravity(0.2)
    .linkDistance(30)                    
    .size([width, height])

Calling force.start() two times:

force
  .nodes(graph.nodes)
  .links(graph.links)
  .on("tick", tick)
  .start();

setTimeout(function() {
  first = 0;
  force.start();
}, 6000);  

Variable "first":

var first = 1;

  if(first) {
    var k = e.alpha;
  }
  else{
    var k = 10 * e.alpha;
  }

Screenshot after first pass:

After second pass:

I'll try to improve the example, this is a little bit "dirty" development prototype, but I don't have time right now, maybe tomorrow.

EDIT: NOTE: I just noticed that actually the data is constant, and, however, the layout differs from simulation to simulation. This doesn't have to be that way. It can be much more deterministic. I'll try to fix that too tomorrow. I'll also do better chaining layouts with "end" event.

Answer 2

The force layout algorithm implemented in D3 doesn't really allow you to do that. It doesn't try to minimise the number of links that cross -- there are other force-directed layout implementations (such as Fruchterman-Reingold) that do explicitly do this, but they're not implemented in D3.

So the short answer is that while you may be achieve a result that's suitable for a particular case, to do this in general, you would have to choose an alternative force layout implementation. There is a Fruchterman-Reingold implementation for sigma.js if you can use other graphing libraries.