使用dagre-d3或colajs在d3js中的流程图 [英] flowcharts in d3js using dagre-d3 or colajs
问题描述
看到非常复杂的
正如所建议的那样，我尝试使用
或多或少我对这个确定最佳渲染的实际问题感兴趣，如何通过算法实现。
这个想法是利用渲染节点的顺序很重要的事实，这样你就可以改变顺序并找到产生最佳结果的顺序。最简单的方法是测试边缘形成的线条的布线框是否发生碰撞。这里我假设边界的开始和结束对于边界框的估计是足够好的。
边缘应该首先保存到列表中
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）;
返回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）{
// - >测试与其他节点的冲突...
boxes.forEach（function（b）{
if （a == b）返回;
//测试是否在
之外if（（a.right< b.left）||
（a.left> b.right）| |
（a.top> b.bottom）||
（a.bottom< b.top））{
//测试是否在
内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）;
休息;
}
if（typeof（best_result）==undefined）{
best_result = collisionCnt;
} else {
if（collisionCnt< best_result）{
optimalArray = list.slice（）;
best_result = collisionCnt;
}
}
在测试期间至少使用简单的图表进行算法所需1-5轮来计算边缘的最佳顺序，所以看起来它至少如果图表不是太大就可以很好地工作。
After seeing the quite complex TCP state diagram example of dagre-d3, I figured it would be able to resolve diagrams of similar complexity. In the following diagram, this clearly isn't the case. If the two marked nodes were swapped, all crossings would be resolved.
Another interesting thing is that how good the graph is solved seems to depend on the order I set the edges in.
The following code
g.setEdge("148570019_1100", "148570020_1100", { label: "" });
g.setEdge("148570019_1100", "148570021_1100", { label: "" });
g.setEdge("148570019_1100", "148570010_1100", { label: "" });
doesn't give the same results as this:
g.setEdge("148570019_1100", "148570010_1100", { label: "" });
g.setEdge("148570019_1100", "148570020_1100", { label: "" });
g.setEdge("148570019_1100", "148570021_1100", { label: "" });
See these two examples:
As suggested, I tried to use cola.js instead, and this is what the same graph looks like:
As you see, colajs is better at crossing reduction, but the layout isn't nearly as structured and clear as dagre's. I use the following settings for colajs:
cola.d3adaptor()
.avoidOverlaps(true)
.convergenceThreshold(1e-3)
.symmetricDiffLinkLengths(20)
.flowLayout('x', 150)
.size([width, height])
.nodes(nodes)
.links(edges)
.constraints(constraints)
.jaccardLinkLengths(300);
Is it possible to configure colajs in a way that makes it look more structured, similar to dagre? And is dagre simply not able to solve something like this, or is it possible to configure it in a way it is?
Here is one solution to the problem: http://jsfiddle.net/5u9mzfse/
More or less I was just interested of this actual problem of determining the optimal rendering, how to achieve that algorithmically.
The idea is to make use of the fact that the order of the rendered nodes matter, so you could shuffle the order and find the order which creates best results. The easiest way to do that is to test if the bouning boxes of the lines which the edges form do collide. Here I assume that the edges start and end is good enough estimate for the bounding box.
The edges should be first saved into list
var edgeList = [["10007154_1100","148570017_1100",{"label":""}, ...]
Then
- Shuffle the list
- Render nodes
- Calculate the bounding boxes of the edges from the output
- Calculate how many bounding boxes overlap
- If the collision count is zero render the output, otherwise continue until max_cnt iterations have been run and select the best so far
The bounding boxes of the edges from the rendered output can be found using something like this:
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;
}
The you just calculate if the boxes collide, I figured something like this give approximately correct results:
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++;
}
})
})
Then you know how many edges are crossing each other with this set of edges.
Then after each round check that if this is the best array we have so far, or if there are no collisions exit immediately;
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;
}
}
During testing at least with a simple graph the algorithm required 1-5 rounds to calculate the optimal order of edges so it looks like it might work quite well at least if the diagram is not too large.
这篇关于使用dagre-d3或colajs在d3js中的流程图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
