使用 Graphviz dot 处理后如何获得节点的排名？

Question

我使用 dot 来渲染图表，效果很好。

现在我需要以某种方式获得点分配给每个节点的排名，有办法做到吗？

例如来自这个 .dot 文件：

digraph D {
    Ivan -> Herbert [label="15,16"];
    Ivan -> Diego [label="23", color="slategray"];
    Roberto -> Herbert [label="17,18"];
    Roberto -> Ivan [label="19,20"];
    Diego -> Roberto [label="21", color="slategray", style=dashed, color=red, constraint=false]
    {rank=max;}
}

我想获得以下信息：

rank of "Roberto" is 1
rank of "Ivan" is 2
rank of "Diego" is 3
rank of "Herbert" is 3

其中节点的等级是其在图形渲染中的深度，即顶部节点的等级为1，其子节点的等级为2，依此类推。

请注意，我的图表通常比较复杂，并且总是包含循环，并且向用户显示视觉布局，因此“自己动手”方法不适用，因为每个节点的排名需要与点渲染相同。

我目前正在使用 python，但我可以使用任何其他工具来实现此目的。

Answer 1

我确信有一种更有效的算法，但是您可以通过networkx首先获取所有“根”节点（即没有“内”边的节点），然后对每个节点的图执行 BFS 来实现此目的，随时定义排名。

我不知道它是否与 DOT 定义的完全相同，但它确实构建了准确的拓扑排名。

代码：

from collections import defaultdict
import networkx as nx

graph = nx.drawing.nx_agraph.read_dot('graph.dot')
roots = []
ranks = defaultdict(int)
for node in graph.nodes:
    if not list(graph.predecessors(node)):
        roots.append(node)
        ranks[node] = 1

for root in roots:
    for (head, tail) in nx.bfs_edges(graph, root):
        ranks[tail] = max(ranks[tail], ranks[head] + 1)

print(ranks)

输出：

defaultdict(<class 'int'>, {'a': 1, 'e': 1, 'b': 2, 'c': 3, 'd': 3})