D3.js强制有向图，通过使边相互排斥来减少边交叉 [英] D3.js force directed graph, reduce edge crossings by making edges repel each other

问题描述

因此，我已经有一个页面绘制了一个强制定向图，如此处所示。 p>

而且工作正常。我使用这里的JS，并进行了一些调整以分散

这些或多或少是唯一的区别：

  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（）; 
  

如果减少链接强度似乎会使链接更像弹簧，因此它与 Fruchterman& Reingold 类似技术经常使用，这种方法运行得相当好，但只适用于相当小的图表，如果图表较大，交叉点的数量会增加 - 正如人们所期望的那样，通常情况下远不是最优的。我不是在寻找一种获得最佳解决方案的方法，我知道这非常困难。我只是希望它有一些粗略的添加，试图强制拆分线以及节点。

有没有办法在在链接中，还是在节点之间？我不熟悉D3 force的工作方式，而且我似乎无法找到任何说这可能的东西...

解决方案

不幸的是，您的问题的答案不存在。 D3中没有内置的机制来排斥边缘或减少边缘交叉。你会认为在边缘实现收费并不难，但我们现在就是这样。

此外，似乎没有任何机制<强大>任何地方，通常可以减少边缘交叉。我已经浏览了几十种可视化库和布局算法，并且他们都没有处理减少通用无向图上的边交叉。

有许多算法适用于平面图或2级图或其他简化。 dagre 在理论上适用于2级图表，尽管完全缺乏文档使其几乎不可能使用。

部分原因是布置图表难以。尤其是，最小化边缘交叉是NP难题，所以我怀疑大多数布局设计师都会遇到这个问题，他们的头撞在键盘上几次，然后放弃。

如果有人为此提供了一个好的图书馆，请发布给我们其他人：）

So i have a page already which draws a force directed graph, like the one shown here.

And that works fine. I'm using the JS from here, with a few tweaks to spread out the nodes slightly nicer.

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 reducing the link strength seems to make the links more like springs, so it becomes similar to the Fruchterman & Reingold technique often used. This works reasonably well, but only for fairly small graphs. With larger graphs the number of crossings just goes up - as one would expect, but the solution it lands on is normally far from optimal. I'm not looking for a method to get the optimal solution, I know that's very difficult. I would just like it to have some crude addition that tries to force the lines apart as well as the nodes.

Is there a way to add a repulsion between in links, as well as between the nodes? I'm not familiar with the way D3 force works, and i can't seem to find anything that says this is possible...

解决方案

Unfortunately, the answer to your question does not exist.

There is no built-in mechanism in D3 that repels edges or minimizes edge crossings. You would think it wouldn't be that hard to implement a charge on an edge, but here we are.

Furthermore, there doesn't seem to be any mechanism anywhere that reduces edge crossings in general. I've looked through dozens of visualization libraries and layout algorithms, and none of them deal with reducing edge crossings on a generic undirected graph.

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

Part of the reason for this is that laying out graphs is hard. In particular, minimizing edge crossings is NP-hard, so I suspect that most layout designers hit that problem, bang their head against the keyboard a few times, and give up.

If anyone does come up with a good library for this, please publish it for the rest of us :)

这篇关于D3.js强制有向图，通过使边相互排斥来减少边交叉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！