javascript D3.js 强制有向图，通过使边相互排斥来减少边交叉
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12007141/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
D3.js force directed graph, reduce edge crossings by making edges repel each other
提问by will
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.
这工作正常。我正在使用这里的 JS ，并进行了一些调整以稍微更好地展开节点。
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 & Reingoldtechnique 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.
降低链接强度似乎使链接更像弹簧，因此它变得类似于经常使用的Fruchterman & Reingold技术。这相当有效，但仅适用于相当小的图形。对于较大的图形，交叉的数量只会增加——正如人们所期望的那样，但它所得到的解决方案通常远非最佳。我不是在寻找获得最佳解决方案的方法，我知道这非常困难。我只是希望它有一些粗略的添加，试图将线和节点分开。
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...
有没有办法在链接之间以及节点之间添加排斥？我不熟悉 D3 force 的工作方式，而且我似乎找不到任何说明这是可能的...
采纳答案by GreySage
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.
D3 中没有排斥边缘或最小化边缘交叉的内置机制。您可能会认为在边缘实施充电并不难，但我们就是这样。
Furthermore, there doesn't seem to be any mechanism anywherethat 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. dagreworks well in theory for 2-level graphs, although the utter lack of documentation makes it almost impossible to work with.
有许多算法适用于平面图、2 级图或其他简化。dagre在理论上适用于 2 级图，尽管完全缺乏文档使其几乎无法使用。
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.
部分原因是布局图表很困难。特别是，最小化边缘交叉是 NP-hard 问题，所以我怀疑大多数布局设计师遇到了这个问题，用头撞到键盘几次，然后放弃了。
If anyone does come up with a good library for this, please publish it for the rest of us :)
如果有人为此想出了一个好的库，请为我们其他人发布它:)
回答by VoronoiPotato
Something that might be easier than trying to forcefully repel the edges is to wiggle the nodes around until the amount of crossing lines in the system is lower.
比试图强行排斥边缘更容易的事情是摆动节点，直到系统中的交叉线数量减少。
http://en.wikipedia.org/wiki/Simulated_annealing
http://en.wikipedia.org/wiki/Simulated_annealing
Start with the nodes with the least amount of connections and wiggle down.
从连接最少的节点开始，然后向下摆动。
If you try and use the edges as nodes I suspect you're just going to get the same spatial locking problems. The solution is in figuring out where there are edge intersections and if they can be resolved. You might find that resolving many of the edge crossings is not possible
如果您尝试将边用作节点，我怀疑您只会遇到相同的空间锁定问题。解决方案是找出边缘交叉点的位置以及它们是否可以解决。您可能会发现无法解决许多边缘交叉问题
A more lateral approach to the visualization is to animate it such that it only shows a subset of the nodes and connections at a time. Or to make the edges transparent until the user places mouse focus over a node, which point the associated edges become more visible.
一种更横向的可视化方法是对其进行动画处理，使其一次仅显示节点和连接的一个子集。或者使边缘透明，直到用户将鼠标焦点放在节点上，该点相关的边缘变得更加可见。
回答by Ionic? Biz?u
I followed the Force Editor example and I saw that setting chargeand linkDistancevalues solves the problem.
我遵循了 Force Editor 示例，我看到设置charge和linkDistance值解决了问题。
...
.charge(-200)
.linkDistance(50)
...
Screenshot:
截屏：
回答by Baum
I have '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.github.io/d3/talk/20110921/parent-foci.html
http://mbostock.github.io/d3/talk/20110921/parent-foci.html
It's not exactly what we wanted but better as before. Importend is, that you define a "root"-Node and fixed it.
这不完全是我们想要的，但比以前更好。Importend 是，您定义一个“根”节点并修复它。
nodes[0].fixed = true;
It look like more as a tree but so it is clearer.
它看起来更像一棵树，但更清晰。
