javascript - 使用dagre-d3或colajs的d3js中的流程图

在看到dagre-d3相当复杂的TCP state diagram example之后，我认为它能够解析相似复杂度的图表。
在下图中，显然不是这种情况。如果交换了两个标记节点，则所有交叉点都将得到解决。

另一个有趣的事情是，图形的求解效果似乎取决于我设置边的顺序。

以下代码

g.setEdge("148570019_1100", "148570020_1100", { label: "" });
g.setEdge("148570019_1100", "148570021_1100", { label: "" });
g.setEdge("148570019_1100", "148570010_1100", { label: "" });

给出的结果与此不同:

g.setEdge("148570019_1100", "148570010_1100", { label: "" });
g.setEdge("148570019_1100", "148570020_1100", { label: "" });
g.setEdge("148570019_1100", "148570021_1100", { label: "" });

请参阅以下两个示例:

perfect graph

messed up graph

如建议的那样，我尝试改用cola.js，这是同一张图的样子:

如您所见，colajs在减少交叉方面更胜一筹，但是布局却不像dagre那样结构清晰。我对colajs使用以下设置:

cola.d3adaptor()
      .avoidOverlaps(true)
      .convergenceThreshold(1e-3)
      .symmetricDiffLinkLengths(20)
      .flowLayout('x', 150)
      .size([width, height])
      .nodes(nodes)
      .links(edges)
      .constraints(constraints)
      .jaccardLinkLengths(300);

是否可以以类似于dagre的方式使colajs看起来更有条理地进行配置？ dagre只是不能解决类似问题，还是可以按原样配置它？

最佳答案

这是解决该问题的一种方法:http://jsfiddle.net/5u9mzfse/

或多或少，我只是对确定最佳渲染的实际问题，如何通过算法实现这一问题感兴趣。

这个想法是利用渲染节点的顺序很重要的事实，因此您可以调整顺序并找到产生最佳结果的顺序。最简单的方法是测试边缘形成的线条的弯曲框是否发生碰撞。在这里，我假设边缘的起点和终点对边界框的估计足够好。

边缘应首先保存到列表中

var edgeList = [["10007154_1100","148570017_1100",{"label":""}, ...]

然后

随机播放列表

渲染节点

从输出

计算边缘的边界框

计算有多少边界框与

重叠

如果冲突计数为零，则输出，否则继续直到 max_cnt 迭代已运行，然后选择到目前为止最好的

可以使用以下方法找到来自渲染输出的边缘的边界框:

  var nn = svg.select(".edgePaths");
  var paths = nn[0][0];
  var fc = paths.firstChild;
  var boxes = [];
  while(fc) {
     var path = fc.firstChild.getAttribute("d");
     var coords = path.split(/,|L/).map(function(c) {
         var n = c;
         if((c[0]=="M" || c[0]=="L")) n = c.substring(1);
         return parseFloat(n);
     })
     boxes.push({ left : coords[0], top : coords[1],
            right : coords[coords.length-2],
            bottom : coords[coords.length-1]});
     fc = fc.nextSibling;
  }

您只是计算这些盒子是否发生碰撞，所以我发现类似这样的结果可以得出大致正确的结果:

  var collisionCnt = 0;
  boxes.forEach( function(a) {
         // --> test for collisions against other nodes...
         boxes.forEach(function(b) {
             if(a==b) return;
             // test if outside
             if ( (a.right  < b.left) ||
                  (a.left   > b.right) ||
                  (a.top    > b.bottom) ||
                  (a.bottom < b.top) ) {

                  // test if inside
                  if(a.left >= b.left  && a.left <=b.right
                  || a.right >= b.left  && a.right <=b.right) {
                     if(a.top <= b.top && a.top >= b.bottom) {
                        collisionCnt++;
                     }
                     if(a.bottom <= b.top && a.bottom >= b.bottom) {
                        collisionCnt++;
                     }
                  }
             } else {
                collisionCnt++;
             }
         })
      })

然后，您知道有多少条边与此组边相交。

然后在每个回合之后检查这是否是我们到目前为止拥有的最好的数组，或者是否没有冲突立即退出；

if(collisionCnt==0) {
     optimalArray = list.slice();
     console.log("Iteration cnt ", iter_cnt);
     break;
 }
 if(typeof(best_result) == "undefined") {
    best_result = collisionCnt;
 } else {
    if(collisionCnt < best_result) {
        optimalArray = list.slice();
        best_result = collisionCnt;
    }
 }

在测试过程中，至少使用一个简单的图形，该算法需要1-5个回合才能计算出边缘的最佳顺序，因此至少在该图不太大的情况下，它看起来可能工作得很好。