CODEWITHSUNDEEP
pythongraph-theorynetworkx
mt88
mt88

Reputation: 3015

NetworkX find root_node for a particular node in a directed graph

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

  1. G has multiple trees in it
  2. 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.

Upvotes: 5

Views: 5176

Answers (4)

Ha Bom
Ha Bom

Reputation: 2917

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.

Upvotes: 0

mrtpk
mrtpk

Reputation: 1437

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

Upvotes: 1

Joel
Joel

Reputation: 23827

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.

Upvotes: 5

Jon
Jon

Reputation: 2567

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

Upvotes: 4

Related Questions