Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find end nodes (leaf nodes) in radial (tree) networkx graph

Given the following graph, is there a convenient way to get only the end nodes?

By end nodes I mean those to-nodes with one connecting edge. I think these are sometimes referred to as leaf nodes.

G=nx.DiGraph()
fromnodes=[0,1,1,1,1,1,2,3,4,5,5,5,7,8,9,10]
tonodes=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
for x,y in zip(fromnodes,tonodes):
    G.add_edge(x,y)
G.add_node(17)     # isolated node
nx.draw_shell(G)

enter image description here

In this example, it would be [6,11,12,13,14,15,16]

like image 634
atomh33ls Avatar asked Aug 11 '15 15:08

atomh33ls


1 Answers

To make sure the definition is clear: I am assuming you are looking for all nodes which have out-degree 0 and in-degree 1. This is what my calculations find.

I'm editing the original answer because networkx 2.0 does not have nodes_iter(). See the networkx migration guide in general for turning 1.x code into 2.0 code.

for networkx 2.0

if you want a list

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

If you'd rather have a generator

(x for x in G.nodes() if G.out_degree(x)==0 and G.in_degree(x)==1)

This also works in networkx 1.x, but is less efficient because G.nodes() creates a list in 1.x.

for networkx 1.x

if you want a list

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

If you'd rather have a generator

(x for x in G.nodes_iter() if G.out_degree(x)==0 and G.in_degree(x)==1)

and just a note - if you modify G while using the generator, the behavior is unlikely to be what you want.

like image 66
Joel Avatar answered Sep 17 '22 19:09

Joel