lars111 February 2016

Identify first node after source node having two neighbors in NetworkX DiGraph

I am implementing a DiGraph with NetworkX. The source is the red-node. I need to identify the first node starting at the red one that has two neighbors (in "flow-direction"). If I iterate over all nodes - it seems like ramdom. Would be great if someone could help!

enter image description here

Answers


Ulf Aslak February 2016

You can use the successors method. If your DiGraph instance is called G, and your red node has index 0 then you can take a breadth first search approach like this:

import networkx as nx

# Construct graph from example image, all edges pointing away from source
G = nx.DiGraph()
G.add_path([0,1,2,3,4])
G.add_path([1,5])
G.add_path([3,6])
G.add_path([2,7,8])

# Find first with 2 neighbors
neighbors = G.successors(0)
for n in neighbors:
    nneighbors = set(G.successors(n))
    if len(nneighbors) == 2:
        print "Found", n
        break
    neighbors.extend(nneighbors)

The neighbors method is interchangable with successors for a DiGraph in networkx. If you want to also count ingoing edges for each node, add G.predecessors(n) to the set of nneighbors when you count them, but remember to not include them in the set when you extend neighbors. The code would then be:

# Find first with 2 neighbors
neighbors = G.successors(0)
for n in neighbors:
    if len(G.predecessors(n)+G.successors(n)) == 2:
        print "Found", n
        break
    nneighbors = set(G.successors(n))
    neighbors.extend(nneighbors)

Post Status

Asked in February 2016
Viewed 2,845 times
Voted 5
Answered 1 times

Search




Leave an answer