在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]

- LittleBobbyTables

---

我认为你可以使用weakly_connected_component_subgraphs，如果可以的话，这是一个重复的问题：https://dev59.com/qHbZa4cB1Zd3GeqPGoW7 - EdChum

还相关的内容：https://dev59.com/iGYr5IYBdhLWcg3wJ3CU。这取决于你如何定义子图。 - EdChum

Answer 1

截至2018年，上述答案已被废弃 (文档链接)。建议使用以下内容：

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

或者

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

- Simon

---

你使用列表生成器而不是列表推导式有什么原因吗？ - errenmike1806

Answer 2

如果图的部分是真正不相交的（就像您的小例子一样），那么请考虑使用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()的文档有点简略。

- Bonlenfum

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，因此无论出于什么原因，似乎都会被销毁。以上方法是稳定的。

- Sauer

---

似乎在2.8版本中nx.weakly_connected_component_subgraphs不再维护。我猜它被weakly_connected_components替代了，它返回一个generator。假设weakly_connected_component_subgraphs也返回一个generator，你可以定义h = list(nx.weakly_connected_component_subgraphs(G))并且不需要使用for循环。 - Ian Thompson