Graphviz使用BFS顺序绘制图形节点

Question

我有一个图形文件(.dot)，其中的节点具有深度和大小"属性"。我想使用graphviz来绘制这个图，将"深度"视为广度优先搜索的深度，将size属性视为节点的相对大小。

我尝试过使用twopi并将具有相同深度的所有节点设置在相同的秩上，但没有成功。关于我该如何做到这一点，有什么建议吗？

示例图：

strict digraph  {
root = 0;
ranksep = 5;
{rank=same; 
0
14754221888142813049
}
{rank=same; 
17110173155996056797 
8860119836345733269  
12488214955576990298 
5164430016200693425  
6534280015544966791  
16035081712171710670 
7728255721346380016  
3065692608114503807  
15537038826989012875 
15464545769657918305 
7964210557574239786  
17237485240931079100 
9667703542183627069  
9063621412962345275  
4956992700610885217  
703599774521196210   
}
0                    [label="A"];
14754221888142813049 [label="B"];
17110173155996056797 [label="C"];
8860119836345733269 [label="D"];
12488214955576990298 [label="E"];
5164430016200693425 [label="F"];
6534280015544966791 [label="G"];
16035081712171710670 [label="H"];
7728255721346380016 [label="I"];
3065692608114503807 [label="J"];
15537038826989012875 [label="K"];
15464545769657918305 [label="L"];
7964210557574239786 [label="M"];
17237485240931079100 [label="N"];
9667703542183627069 [label="O"];
9063621412962345275 [label="P"];
4956992700610885217 [label="Q"];
703599774521196210 [label="R"];
0                   -> 14754221888142813049
0                   -> 12488214955576990298
0                   -> 5164430016200693425 [weight=0, constraint=false];
0                   -> 15537038826989012875
0                   -> 7964210557574239786 
0                   -> 9667703542183627069 
0                   -> 17237485240931079100
5164430016200693425 -> 8860119836345733269 [weight=0, constraint=false];
8860119836345733269 -> 4956992700610885217 
8860119836345733269 -> 9063621412962345275 
8860119836345733269 -> 703599774521196210  
8860119836345733269 -> 17110173155996056797
8860119836345733269 -> 6534280015544966791 
8860119836345733269 -> 16035081712171710670
8860119836345733269 -> 7728255721346380016 
8860119836345733269 -> 3065692608114503807 
8860119836345733269 -> 15464545769657918305
}

Answer 1

您正试图捕获层次结构，因此希望使用点布局。默认情况下，如果你有一条边a->b，节点b将比节点a低1级。如果你有树，并确保深度为0的节点首先出现，你将在默认情况下获得你想要的布局。如果图形更复杂，则提到的边标准或循环中断可能会干扰您想要的内容。在这种情况下，需要使深度约束更加明确，并关闭其他边约束。有几种方法可以做到这一点。

假设您有以下图形，其中节点名称中的数字表示深度。

digraph {
0 -> a1
0 -> b1
a1 -> a2
a1 -> b2
b1 -> c2
b1 -> d2
a2 -> d2 
a2 -> b1 
}

获得所需内容的一个简单方法是执行BFS，并将不属于BFS树的任何边设置为constraint=false。

digraph {
0 -> a1
0 -> b1
a1 -> a2
a1 -> b2
b1 -> c2
b1 -> d2
a2 -> d2 [constraint=false]
a2 -> b1 [constraint=false]
}

或者，您可以使用rank=same来确保节点被放置在与其深度相对应的列中，再次关闭冲突的边。(这假设你至少有一条从深度0到底部的边链。如果没有，你可以引入一条不可见的伪节点链和满足这一点的边，并将每个伪节点添加到其秩=相同的子图中。｝

digraph {
0 -> a1
0 -> b1
a1 -> a2
a1 -> b2
b1 -> c2
b1 -> d2
a2 -> d2 [constraint=false]
a2 -> b1 [constraint=false]
{rank=same a1 b1}
{rank=same a2 b2 c2 d2}
}

这允许深度函数实际上不与BFS树绑定。

顺便说一句，twopi应该起作用，但布局是居中的，而不是自上而下的，因为它的级别是基于根节点的BFS。这假设您设置了根属性，并且考虑到了明确的BFS，通过设置weight=0来关闭非树边。

digraph {
root=0
0 -> a1
0 -> b1
a1 -> a2
a1 -> b2
b1 -> c2
b1 -> d2
a2 -> d2 [weight=0]
a2 -> b1 [weight=0]
}