NetworkX find root_node for a particular node in a directed graph

Question

Suppose I have a directed graph G in Network X such that:

G has multiple trees in it
Every node N in G has exactly 1 or 0 parent's.

For a particular node N1, I want to find the root node of the tree it resides in (its ancestor that has a degree of 0). Is there an easy way to do this in network x?

I looked at: Getting the root (head) of a DiGraph in networkx (Python) But there are multiple root nodes in my graph. Just only one root node that happens to be in the same tree as N1.

Have you thought of just looking at its parent, then it's parent's parent etc until it stops? - i.e., do a depth first search (or breadth-first or any other variety) following edges in reverse until it stops? The last node must be it. — Joel, Apr 08 '16 at 00:39

Joel · Accepted Answer · 2017-11-09T01:13:03.863

edit Nov 2017 note that this was written before networkx 2.0 was released. There is a migration guide for updating 1.x code into 2.0 code (and in particular making it compatible for both)

Here's a simple recursive algorithm. It assumes there is at most a single parent. If something doesn't have a parent, it's the root. Otherwise, it returns the root of its parent.

def find_root(G,node):
    if G.predecessors(node):  #True if there is a predecessor, False otherwise
        root = find_root(G,G.predecessors(node)[0])
    else:
        root = node
    return root

If the graph is a directed acyclic graph, this will still find a root, though it might not be the only root, or even the only root ancestor of a given node.

score 4 · Answer 2 · answered Nov 08 '17 at 22:48

I took the liberty of updating @Joel's script. His original post did not work for me.

def find_root(G,child):
    parent = list(G.predecessors(child))
    if len(parent) == 0:
        print(f"found root: {child}")
        return child
    else:  
        return find_root(G, parent[0])

Here's a test:

G = nx.DiGraph(data = [('glu', 'skin'), ('glu', 'bmi'), ('glu', 'bp'), ('glu', 'age'), ('npreg', 'glu')])
test = find_root(G, "age")
age
glu
npreg
found root: npreg

score 1 · Answer 3 · answered Nov 03 '22 at 19:16

1

Networkx - 2.5.1

The root/leaf node can be found using the edges.

for node_id in graph.nodes:
    if len(graph.in_edges(node_id)) == 0:
        print("root node")
    if len(graph.out_edges(node_id)) == 0:
        print("leaf node")

answered Nov 03 '22 at 19:16

mrtpk

1,398
4
18
38

score 0 · Answer 4 · answered Nov 24 '22 at 23:58

In case of multiple roots, we can do something like this:

def find_multiple_roots(G, nodes):
    list_roots = []
    for node in nodes:
        predecessors = list(G.predecessors(node))
        if len(predecessors)>0:
            for predecessor in predecessors:
                list_roots.extend(find_root(G, [predecessor]))
        else:
            list_roots.append(node)
            
    return list_roots

Usage:

# node need to be passed as a list
find_multiple_roots(G, [node])

Warning: This recursive function can explode pretty quick (the number of recursive functions called could be exponentially proportional to the number of nodes exist between the current node and the root), so use it with care.

NetworkX find root_node for a particular node in a directed graph

4 Answers4