如何将一个未连接的networkx图拆分为多个相互不相交且相互连接的图？

Question

我有一个networkx.Graph对象，表示一个graph，其nodes表示英语单词，其edges位于两个Wnode之间意味着这些节点表示的两个单词在其synsets（即非空的intersection）之间至少有一个共享的cognitive synonym。我希望这对某些人来说是有趣或有用的背景知识，但我的问题是一个更广泛适用的问题，涉及到图、networkx和Python

这个图的许多induced subgraphs（边诱导，或顶点诱导）都是edge disjoint and vertex disjoint，我想把这些子图分成它们自己的networkx.Graph对象，这样它们是相互连接和不相交的。可能我只是对networkx文档使用了错误的搜索词，但是I didn't see anything promising related to "disjoint"。下面是图中一小部分的一些示例

我在search results中查找了[networkx] disjoint关于堆栈溢出的内容，但没有看到我要查找的内容。例如，one result talked about getting the induced subgraph when there's already have an edge set to induce from。或者another post talked about trying to draw two disjoint graphs，但这是假设你已经拥有了它们。与我问题的图论方面有关，但与networkx方面无关，显然有such a thing as a flood fill algorithm that might address the part of my question

现在，作为一个最简单的工作示例，让我们创建一个小的随机图，但确保它是断开的

import networkx as nx

g = nx.fast_gnp_random_graph(10, 0.3)

while nx.is_connected(g):
    g = nx.fast_gnp_random_graph(10, 0.3)

此时，我们有一个图g。我想到的是下面这样的东西，我占据了一个相互不相交的图表列表。我不仅需要在循环节点时添加更多的图，还需要在运行时更新图。我认为诱导图的并集可能会起作用，但是nx.disjoint_union_all和nx.union会通过重新标记（我不希望这样）强制图是不相交的，或者期望图已经是不相交的

graphs = []

for node in g.nodes(): # same 'g' we made above
    if graphs:
        pass
    else:
        graphs.append(g.subgraph([i for i in g.neighbors(node)] +\
                                 [node]).copy())

如何将未连接的networkx图拆分为多个相互不相交的连接图？

Answer 1

您似乎正在寻找连接的组件。
考虑下面的图表。

components = [g.subgraph(c).copy() for c in nx.connected_components(g)]
for idx,g in enumerate(components,start=1):
    print(f"Component {idx}: Nodes: {g.nodes()} Edges: {g.edges()}")

输出：

Component 1: Nodes: [0, 1, 2, 5, 6, 7, 8, 9] Edges: [(0, 2), (0, 6), (1, 2), (1, 5), (1, 7), (1, 8), (2, 5), (5, 7), (6, 8), (7, 9), (8, 9)]
Component 2: Nodes: [3, 4] Edges: [(3, 4)]