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

Question

I'm trying to use networkx to do some graph representation in a project, and I'm not sure how to do a few things that should be simple. I created a directed graph with a bunch of nodes and edges, such that there is only one root element in this graph. Now, what I'd like to do is start at the root, and then iterate through the children of each element and extract some information from them. How do I get the root element of this DiGraph?

So it would be something like this:

#This is NOT real code, just pseudopython to convey the general intent of what I'd like to do

    root = myDiGraph.root()
    for child in root.children():
        iterateThroughChildren(child)

def iterateThroughChildren(parent):
    if parent.hasNoChildren(): return
    for child in parent.children():
        //do something
        //
        iterateThroughChildren(child)

I didn't see anything in the documentation that suggested an easy way to retrieve the root of a DiGraph -- am I supposed to infer this manually? :O I tried getting iter(myDiGraph) with the hope that it would iterate starting at the root, but the order seems to be random... :\

Help will be appreciated, thanks!

Errancy

In my uninformed opinion, a graph does not necessarily have a root, hence there is no function to find it. – Splashboard

Answer 1

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.

Rite

I tried the topological sort and that worked. Speed isn't a major concern for this operation so I might just stick with that, but if it does become a concern I'll look into your third option – Errancy

I tried, but got error 'DiGraph' object has no attribute 'in_degree'. Did networkx deprecate or modify the in_degree() ? Could you post which version of networkx you are using? – Paternoster

in_degree() works for me using a DiGraph. I'm using networkx version 2.2. – Mortar

Answer 2

You could try this to get the root node of the graph:

root_node = [x for x in G.nodes() if G.out_degree(x)>1 and G.in_degree(x)==0]

Nanette