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

问题描述

所以我已经有一个页面可以绘制力有向图，就像此处所示.>

而且效果很好.我正在使用 此处 中的 JS，并进行了一些调整以展开节点稍微好一点.

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

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

降低链接强度似乎使链接更像弹簧，所以它变得类似于 Fruchterman &经常使用 Reingold 技术.这相当有效，但仅适用于相当小的图形.对于较大的图形，交叉的数量只会增加——正如人们所期望的那样，但它所得到的解决方案通常远非最佳.我不是在寻找获得最佳解决方案的方法，我知道这非常困难.我只是希望它有一些粗略的添加，试图将线条和节点分开.

有没有办法在链接之间以及节点之间添加排斥力?我不熟悉 D3 力的工作方式，我似乎找不到任何东西说这是可能的...

解决方案

很遗憾，您的问题的答案不存在.

D3 中没有排斥边缘或最小化边缘交叉的内置机制.您可能会认为在边缘实施收费并不难，但我们来了.

此外，似乎没有任何机制任何地方可以减少一般的边缘交叉.我浏览了数十个可视化库和布局算法，但没有一个涉及减少通用无向图上的边交叉.

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

部分原因是布局图表困难.特别是，最小化边缘交叉是 NP-hard 问题，所以我怀疑大多数布局设计师遇到了这个问题，用头撞到键盘几次，然后放弃了.

如果有人为此想出了一个好的库，请为我们其他人发布它:)

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屋！