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

Question

我正在使用 NetworkX 实现有向图。源是红色节点。我需要确定从红色节点开始的第一个节点，它有两个邻居(在“流向”)。如果我遍历所有节点——它看起来像是随机的。如果有人可以提供帮助，那就太好了!

Answer 1

您可以使用successors 方法。如果您的 DiGraph 实例称为 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)

对于 networkx 中的有向图，neighbors 方法可与 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)