D3.js强制有向图,通过使边缘相互排斥来减少边缘交叉

Question

所以我有一个页面已经绘制了一个力导向图,就像这里显示的那样.

这很好.我从这里使用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力的工作方式,我似乎无法找到任何说这可能的东西......

Answer 1

不幸的是,你的问题的答案不存在.

D3中没有内置机制可以排斥边缘或最小化边缘交叉.你会认为在边缘实施收费并不难,但我们就是这样.

此外,似乎没有任何机制可以减少边缘交叉.我查看了几十个可视化库和布局算法,但没有一个涉及减少通用无向图上的边缘交叉.

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

部分原因是布局图表很难.特别是,尽量减少边缘交叉是NP难度的,所以我怀疑大多数布局设计师都遇到了这个问题,几次撞到键盘,并放弃了.

如果有人为此想出一个好的图书馆,请为我们其他人发布:)

Answer 2

可能比试图强行击退边缘更容易的事情是绕过节点,直到系统中的交叉线数量较低.

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

从具有最少连接数的节点开始并向下摆动.

如果您尝试将边缘用作节点,我怀疑您将获得相同的空间锁定问题.解决方案是确定哪里有边缘交叉点以及它们是否可以解决.您可能会发现无法解决许多边缘交叉问题

可视化的更侧向方法是使其动画化,使得它一次仅显示节点和连接的子集.或者使边缘透明,直到用户将鼠标焦点放在节点上,相关边缘变得更加明显.