如何使用节点列表作为输入，在有向图中找到连通分量？

Question

我有一个由Python中的networkX创建的有向图G，每条边都是双向的。我有一定的节点列表，并且我正在尝试找到这些节点之间的连通组件。下面我创建了一个示例数据集（我正在处理的实际图形要大得多）。

import networkx as nx
G = nx.DiGraph()
nodeList = range(1,10)

for i in range (0,len(nodeList)):
    G.add_node(nodeList[i])

o_nodes = [1,1,2,3,3,3,3,4,4,5,5,6,7,7,8,9,9,10]
d_nodes = [8,3,3,1,7,2,4,5,3,4,6,5,3,9,1,7,10,9]

for i in range(0, len(o_nodes)):
    G.add_edge(o_nodes[i], d_nodes[i])  
    
nx.draw(G, with_labels = True)

假设我有一个节点列表，selectNodeList = [1,2,5,6,7,8,9,10]，我需要找到这些节点之间的连通分量。因此，结果应该是像 [8,1], [7,9,10], [2], [5,6] 这样的东西。我希望得到最少的组件数量，以覆盖选择节点列表中的所有节点。

我尝试使用一个for循环和if nx.shortest_path_length(G, source = selectNodeList[i], target = selectNodeList[j]) == 1:，然后将结果附加到列表中，以获取每个节点的直接邻居，但是我不确定如何进一步获取邻居，以及如何创建可读的输出。

编辑：这是我在上面提到的代码。我不愿意添加它，因为它没有完全完成。我的思路是首先获取两个直接相邻的节点，然后搜索另一个节点，该节点也是其中一个节点的直接邻居，以此类推。但是，这样做不能输出完全没有连接的节点，并且会导致重复连接的节点列表（例如[1 8 1 8 1 8 5 6 5 6 ...]）。对我来说，一个问题是我不知道如何处理创建不同维度输出的问题，以及如何在不创建大量for循环的情况下解决问题。

connected = []
for i in range(0,34):
    for j in range (1,34):
        if nx.shortest_path_length(G, source = selectNodeList[i], target = selectNodeList[j]) == 1:
            connected.append(selectNodeList[i])
            connected.append(selectNodeList[j])
            for k in range(2,34):
                if nx.shortest_path_length(G, source = selectNodeList[j], target = selectNodeList[k]) == 1:
                    connected.append(selectNodeList[k])
                    for l in range (3,34):
                        if nx.shortest_path_length(G, source = selectNodeList[k], target = selectNodeList[l]) == 1:
                            connected.append(selectNodeList[l])
                            for m in range(4,34):
                                if nx.shortest_path_length(G, source = selectNodeList[l], target = selectNodeList[m]) == 1:
                                    connected.append(selectNodeList[m])

- Zasu

---

你当前的解决方案结果是什么样子？你能提供上一段描述的实际代码吗？ - wwii

使用现有函数：https://networkx.github.io/documentation/stable/reference/algorithms/component.html - Dan D.

@wwii 我已经添加了最后一部分的代码。@Dan D. nx.connected_components 不起作用，因为图是有向的。我已经尝试使用 nx.strongly_connected_components，但是结果是整个图的所有节点编号的列表，而不仅仅是节点列表中的节点编号。我不确定原因。 - Zasu

你能提供一个示例图，其中将图转换为无向图，然后计算连通分量会导致与你期望的输出不同的结果吗？ - Paul Brodersen

你想保留这个图为有向图(DiGraph)的原因是什么？由于“每条边都是双向的”，你可以很容易地将其转换为无向图(Graph)。 - ComplexGates

@ComplexGates 这个图是有向的，因为边缘是加权的，它们的权重取决于方向。@Paul Brodersen 我将图形转换为无向图，然后使用了 @Dan D. 之前提供的代码：connected= [list(c) for c in nx.connected_components(G)]，但这会导致列表中包含图形的所有节点编号。 - Zasu

Answer 1

你需要在由你的节点子集引发的子图中找到连接的组件（无论是弱还是强，都没有关系，因为你的所有边都是双向的）。

node_subset = [1,2,5,6,7,8,9,10]
[list(cc) for cc in nx.strongly_connected_components(G.subgraph(node_subset))]

[[8, 1], [2], [5, 6], [9, 10, 7]]

- ComplexGates