Getting the root (head) of a DiGraph in networkx (Python)

If by having “one root element” you mean your directed graph is a rooted tree, then the root will be the only node with zero in-degree.

You can find that node in linear time (in the number of nodes) with:

In [1]: import networkx as nx

In [2]: G=nx.balanced_tree(2,3,create_using=nx.DiGraph()) # tree rooted at 0

In [3]: [n for n,d in G.in_degree() if d==0] 
Out[3]: [0]

Or you could use a topological sort (root is first item):

In [4]: nx.topological_sort(G)
Out[4]: [0, 1, 3, 8, 7, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]

Alternatively it might be faster to start with a given (random) node and follow the predecessors until you find a node with no predecessors.

Leave a Comment