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

Question

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

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

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

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

Answer 1

这可能看起来很奇怪，但这个函数被称为祖先:)

nx.ancestors(G, your_node)

Answer 2

使用前辈只会将具有直接边的节点返回到输入节点。可以按如下方式查找所有节点的祖先：

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 ，然后再次反转结果以获得原始方向上的边。

最后三行用于绘制结果。