Skip to main content
 首页 » 编程设计

python之如何使用节点列表作为输入在有向图中找到连接的组件

2024年11月01日14kenshinobiy

我有一个有向图 G,它是在 Python 中使用 networkX 创建的。每条边都是双向的。我有一个特定的节点列表,我试图在这些节点中找到连接的组件。下面我创建了一个示例数据集(我正在处理的实际图表要大得多)。

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

请您参考如下方法:

您需要在由您的节点子集导出的子图中找到连通分量(弱或强,这并不重要,因为您的所有边都是双向的)。

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