CODEWITHSUNDEEP
python-3.xgraphnetworkxgraph-theory
Satrio Adi Prabowo
Satrio Adi Prabowo

Reputation: 600

Find root of each node in graph using NetworkX

How to get root for each node in graph using NetworkX?

This is the sample of my graph:

enter image description here

Expected result:

Node 4 has root: 0

Node 2 has root: 0

Node 1 has root: 0

Node 0 has root: 0

Node 3 has root: 8

Node 5 has root: 8

Node 8 has root: 8

I created a while loop to get the root of the node and it worked well unless it is very slow.

Is there any efficient way to do this for a big network?

Upvotes: 1

Views: 945

Answers (1)

yatu
yatu

Reputation: 88236

Assuming you have a single root node per component, you can start by finding all root nodes in the graph, by checking which of the nodes have a degree of 0. Once identified, iterate over the nx.weakly_connected_components, and find which root node belongs to it:

roots = {n for n,d in G.in_degree() if d==0}
d = {}
for comp in nx.weakly_connected_components(G):
    comp_root = next(root for root in roots if root in comp)
    d.update(dict.fromkeys(comp, comp_root))  

print(d)
{0: 0, 1: 0, 2: 0, 4: 0, 8: 8, 3: 8, 5: 8}

Upvotes: 1

Related Questions