Skip to main content
 首页 » 编程设计

python之用后续边替换 networkx 图中节点的有效方法

2024年11月24日9Renyi-Fan

我正在尝试用跟随边替换图中的节点。这意味着被替换/删除节点的每个前任节点将连接到被替换/删除节点的每个后继节点。

例如,考虑一个有 5 个节点的路径图,边 (0, 1), (1, 2), (2, 3), (3, 4),我希望用后续边替换节点 1 和 3((0,2) 用于节点 1)和((2,4) 用于节点 3)。最终图应具有边 (0, 2), (2, 4)。

请您参考如下方法:

Networkx 没有内置函数/算法,因此您应该手动进行。 Itertools模块将帮助您自动化边的构建以创建:

import itertools as it 
import networkx as nx 
 
 
G = nx.DiGraph() 
G.add_edges_from([ 
    (1,2), 
    (2,3), 
    (3,5), 
    (4,5), 
    (5,6), 
    (5,7) 
]) 
 
nodes_to_delete = [2, 5] 
for node in nodes_to_delete: 
    G.add_edges_from( 
        it.product( 
            G.predecessors(node), 
            G.successors(node) 
        ) 
    ) 
    G.remove_node(node) 

因此 G.edges 将返回所需的边(1->2->3 移动到 1->3 和 3,4,6,7 成对连接):

OutEdgeView([(1, 3), (3, 6), (3, 7), (4, 6), (4, 7)])


P.S. 我怀疑 networkx 中是否存在更有效的方法。在 networkx 中,您应该检查每个节点的前任/后继节点,以便 O 复杂度无论如何都是相同的。