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

Question

在看到dagre-d3 相当复杂的TCP状态图示例之后,我认为它能够解析类似复杂性的图表.在下图中,显然不是这种情况.如果交换了两个标记的节点,则将解析所有交叉.

另一件有趣的事情是,图表的解决效果似乎取决于我设置边缘的顺序.

以下代码

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: "" });

看这两个例子:

• 完美的图形
• 乱糟糟的图

正如所建议的那样,我尝试使用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);

是否有可能以一种使其看起来更结构化的方式配置colajs,类似于dagre？并且dagre根本无法解决这样的问题,或者是否可以以某种方式配置它？

Answer 1

以下是该问题的一种解决方案:http://jsfiddle.net/5u9mzfse/

或多或少我只是对确定最佳渲染的实际问题感兴趣,如何在算法上实现.

我们的想法是利用渲染节点的顺序很重要的事实,这样你就可以改变顺序并找到创造最佳结果的顺序.最简单的方法是测试边缘形成的线条的布线框是否发生碰撞.这里我假设边缘开始和结束对边界框的估计是足够好的.

应首先将边缘保存到列表中

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

然后

1. 洗牌清单
2. 渲染节点
3. 从输出计算边的边界框
4. 计算边界框重叠的数量
5. 如果碰撞计数为零,则渲染输出,否则继续直到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轮来计算边缘的最佳顺序,因此看起来它至少在图表不是太大的情况下可能工作得很好.