Как найти всех предков узла в NetworkX?

Question

У меня большой DiGraph, который состоит из зависимых заданий. Например, для графа a> b> c задание c может выполняться только после завершения задания b. Я попытался найти функцию, которая получает все задания вверх по течению (то есть (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 из узла ввода на обращенном ориентированном графе, а затем снова обращаем результат, чтобы получить ребра в их первоначальном направлении.

Последние три строки предназначены для рисования результата.