获取包含一定数量节点的networkx子图

Question

我有一个networkx DiGraph，我想提取包含一定数量节点的子图。例如，有向图是0-1-2-3-4-5.我想获得包含3个节点的所有子图。结果应为: 0-1-2，1-2-3，2-3-4，3-4-5.我怎么能这么做？

Answer 1

我不完全确定我是否理解正确:你的例子意味着你只想要连通子图？在有向图中，有不止一种连通性(弱和强)。所以你得决定你要找的是哪个。

这样做可能会奏效：

import networkx as nx
from itertools import combinations

# The graph in your example (as I understand it)
G = nx.DiGraph((i, i+1) for i in range(5))

num_of_nodes = 3 # Number of nodes in the subgraphs (here 3, as in your example)
subgraphs = [] # List for collecting the required subgraphs
for nodes in combinations(G.nodes, num_of_nodes):
    G_sub = G.subgraph(nodes) # Create subgraph induced by nodes
    # Check for weak connectivity
    if nx.is_weakly_connected(G_sub):
        subgraphs.append(G_sub)

combinations(G.nodes, num_of_nodes)迭代num_of_nodes的所有唯一组合--来自G的多个节点。

所选的子图正是您所提到的：

print([H.nodes for H in subgraphs])
print([H.edges for H in subgraphs])

显示

[NodeView((0, 1, 2)), NodeView((1, 2, 3)), NodeView((2, 3, 4)), NodeView((3, 4, 5))]
[OutEdgeView([(0, 1), (1, 2)]), OutEdgeView([(1, 2), (2, 3)]), OutEdgeView([(2, 3), (3, 4)]), OutEdgeView([(3, 4), (4, 5)])]

如果你的图是

G = nx.DiGraph([(i, i+1) for i in range(5)] + [(i+1, i) for i in range(5)])

你在寻找强大的连通性，所以你必须使用

...
    # Check for strong connectivity
    if nx.is_strongly_connected(G_sub):
        ...

(通常的警告：G.subgraph()只提供一个视图。)