How to find all node's ancestors in NetworkX?

Question

I have a large DiGraph that consists of dependent jobs. For example, for the graph a>b>c, job c can run only once job b is completed. I tried to find a function that gets all c's upstream jobs (that is (a, b)). I used DiGraph.predecessors, but it only returns job b.

Is there a function that will list all c's upstream jobs?

How can I draw the dependency diagram for a leaf node (like job c)?

I have read the documentation but couldn't find the answer.

Answer 1

Using predecessors will only return the nodes with a direct edge to the input node. Finding all node's ancestors can be done as follows:

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()

What we do is simply running DFS from the input node on the reversed directed graph, and then reverse the result again to get the edges in their original direction.

The last three lines are for drawing the result.

Answer 2

It may seem strange, but this function is called ancestors :)

nx.ancestors(G, your_node)