在networkx中的图形对象中查找单独的图形

Question

我有一个巨大的图表数据集 - 让我们说它是这样的，但在更大的层面上：

1 -> 2
3 -> 4

1,2,3,4是节点，箭头是有向边。假设它们都在一个图形对象中：

import networkx as nx
G = nx.DiGraph()
G.add_nodes_from([1,2,3,4])
G.add_edge(1,2)
G.add_edge(3,4)

给定一个像这样的对象，它在图形中有两个迷你图形，我们如何拉出每个迷你图形？我觉得必须有这个词吗？我的最终结果如下：

for mini_graph in G:
    print mini_graph.nodes()

...
[1,2]
[3,4]

Answer 1

如果图形的各个部分是真正不相交的（根据你的小例子），那么考虑用connected_component_subgraphs()提取子图。

这仅适用于无向图，因此如果您使用有向图，则需要首先转换为无向图。

import networkx as nx
G = nx.DiGraph()
G.add_nodes_from([1,2,3,4])
G.add_edge(1,2)
G.add_edge(3,4)

# make an undirected copy of the digraph
UG = G.to_undirected()

# extract subgraphs
sub_graphs = nx.connected_component_subgraphs(UG)

for i, sg in enumerate(sub_graphs):
    print "subgraph {} has {} nodes".format(i, sg.number_of_nodes())
    print "\tNodes:", sg.nodes(data=True)
    print "\tEdges:", sg.edges()

产量：

subgraph 1 has 2 nodes
    Nodes: [(1, {}), (2, {})]
    Edges: [(1, 2)]
subgraph 1 has 2 nodes
    Nodes: [(3, {}), (4, {})]
    Edges: [(3, 4)]

并且您可以使用子图节点标签来操作初始图中的数据，

sg.nodes()[0] in G
>>>  True

阅读EdChum链接的答案，看来weakly_connected_component_subgraphs()在有向图上运行，但将其视为无向，因此保存副本可能至关重要。然而，关于这个和相关函数weakly_connected_components()的文档目前有点薄。

Answer 2

截至2018年，上述答案已被弃用（link to docs）。建议您使用：

(G.subgraph(c) for c in connected_components(G))

要么

(G.subgraph(c).copy() for c in connected_components(G))

Answer 3

由于之前的答案是针对无向图，我们将丢失方向的重要信息，因为转换为无向图。我有同样的问题，最后方法weakly_connected_components做到了。

>>> G = nx.DiGraph()
>>> G.add_nodes_from([1,2,3,4])
>>> G.add_edge(1,2)
>>> G.add_edge(3,4)
>>> list(nx.weakly_connected_components(G))
[{1, 2}, {3, 4}]

它适用于有向图，其性能非常不错。如果您想分割图形并继续计算（像我一样），那么您还可以使用以下方法构建上述结果的子图：

h = nx.weakly_connected_component_subgraphs(G)

j = []
for foo in h:
    j.append(foo)

（非常明确，以显示如何访问它）。无论出于何种原因，h似乎都会被列出来销毁？！以上方式是稳定的。