D3.js directed graph, reduces edge intersections, causing edges to repel each other

Question

So, I have a page that draws a force pattern, for example, shown here .

And it works great. I am using JS from here , with a few settings, to expand the nodes a bit.

These are more or less the only differences:

d3.json("force.json", function(json) { var force = d3.layout.force() .gravity(0.1) .charge(-2000) .linkDistance(1) .linkStrength(0.1) .nodes(json.nodes) .links(json.links) .size([w, h]) .start(); 

Where a reduction in bond strength seems to make links more like springs, it therefore becomes similar to the commonly used Fruchterman and Reingold techniques. This works quite well, but only for fairly small graphs. With large graphs, the number of transitions is simply growing - as one would expect, but the solution that it lands on is usually far from optimal. I am not looking for a way to get the best solution, I know that it is very difficult. I just would like for him to have a rude addition that is trying to fix the lines from each other, as well as the nodes.

Is there a way to add repulsion between links as well as between nodes? I am not familiar with how the power of D3 works, and I cannot find anything that is possible ...

Answer 1

Unfortunately, the answer to your question does not exist.

D3 does not have a built-in mechanism that pushes edges or minimizes edge intersections. You might think that it would be difficult to realize a charge on the verge, but we are here.

In addition, there is no mechanism anywhere that reduces the intersection of the ribs as a whole. I looked at dozens of visualization libraries and layout algorithms, and none of them are associated with a decrease in border crossings on a common undirected graph.

There are a number of algorithms that work well for planar graphs or two-level graphs or other simplifications. dagre works well in theory for two-level graphs, although a complete lack of documentation makes it almost impossible to work.

This is partly due to the fact that the layout of the graphs is tough . In particular, minimizing the intersections of NP-hard edges, so I suspect that most layout designers were struck by this problem, hit their head on the keyboard several times and gave up.

If anyone has a good library for this, please post it to the rest of us :)

Answer 2

Something that might be easier than trying to flip the edges strongly is to sway the nodes around until the number of intersection lines in the system is lower.

http://en.wikipedia.org/wiki/Simulated_annealing

Start with the nodes with the least number of connections and go on.

If you try to use edges as nodes, I suspect that you just get the same problems with spatial locking. The solution is to find out where there are intersections of the ribs, and if they can be resolved. You may find that it is not possible to resolve many edge crossings

A more lateral approach to visualization is to animate it so that it only displays a subset of nodes and connections at a time. Or make the edges transparent until the user focuses on the node, which indicates that the connected edges are becoming more visible.

Answer 3

I followed the example of Force Editor, and I saw that the charge and linkDistance solve the problem.

  ... .charge(-200) .linkDistance(50) ... 

Screenshot:

Answer 4

I "solved" the problem with this:

 nodes[0].x = width / 2; nodes[0].y = 100; nodes[0].fixed = true; force.on("tick", function(e) { var kx = .4 * e.alpha, ky = 1.4 * e.alpha; links.forEach(function(d, i) { d.target.x += (d.source.x - d.target.x) * kx; d.target.y += (d.source.y + 80 - d.target.y) * ky; }); [...] } 

http://mbostock.imtqy.com/d3/talk/20110921/parent-foci.html

This is not exactly what we wanted, but better than before. Importend is that you define the “root” - Node and fix it.

 nodes[0].fixed = true; 

It looks more like a tree, but clearer.