在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

由于之前的答案是针对无向图的，因此由于转换为无向图，我们将丢失方向的重要信息。我遇到了同样的问题，最后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似乎被列出来破坏了？！上面的方式反而是稳定的。

Answer 3

截至2018年，以上答案已弃用（链接至docs）。建议您使用：

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

要么

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