识别NetworkX中具有两个邻居的源节点之后的第一个节点DiGraph

Question

我正在使用NetworkX实现DiGraph。源是红色节点。我需要确定从具有两个邻居的红色节点（以“流向”）开始的第一个节点。如果我遍历所有节点 - 看起来像ramdom。如果有人能帮忙，会很棒！

Answer 1

可以使用successors方法。如果您有向图实例被称为G，和你的红节点具有索引0，那么你可以采取breadth first search的做法是这样的：

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) 

的neighbors方法是可以互换的，在networkx successors一个有向图。如果您还想计算每个节点的初始边缘，请在计数时将G.predecessors(n)添加到nneighbors集合中，但请记住在扩展neighbors时不要将它们包括在集合中。代码然后是：

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