python - 如何在NetworkX中找到所有节点的祖先？

Question

我有一个很大的 DiGraph，其中包含依赖作业。例如，对于图 a>b>c，作业 c 只能在作业 b 完成后运行。我试图找到一个函数来获取所有 c 的上游作业(即 (a, b))。我使用了 DiGraph.predecessors ，但它只返回作业 b。

是否有一个函数可以列出所有 c 的上游作业？

如何绘制叶节点(如作业 c)的依赖关系图？

我已阅读文档但找不到答案。

Answer 1

使用 predecessors 只会将具有直接边的节点返回到输入节点。查找所有节点的 ancestors 可以按如下方式完成:

import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()

# G is:
#      e-->f
#      ^
#      |
# a--->b-->c-->d
#

G.add_edges_from([('a', 'b'),('b', 'c'),('c', 'd'), ('b', 'e'), ('e', 'f')])
T = nx.dfs_tree(G.reverse(), source='f').reverse()     

# T is: a-->b-->e-->f

pos = nx.nx_pydot.pydot_layout(T, prog='dot')
nx.draw_networkx(T, pos=pos, arrows= True, with_labels=True)
plt.show()

我们所做的只是从 反转 有向图上的输入节点运行 DFS，然后再次反转结果以获得原始方向的边。

最后三行用于绘制结果。