Skip to main content
 首页 » 编程设计

python之有没有一种有效的方法可以在不引起 networkx 循环的情况下将节点添加到有向图中

2024年11月24日12zhwl

我正在考虑使用 networkx 创建和维护 Directed Acyclic Graph(DAG) .

检查添加边是否会导致有向图不再是 DAG 的首选方法是什么?

示例图:

import networkx as nx 
 
 
G = nx.DiGraph() 
G.add_edges_from([(1,2), (1,3), (2,4)]) # no cycles so far 

我们得到:

>>> G 
1 2 3 
2 4 
3 
4 
 
 
>>> nx.is_directed_acyclic_graph(G) 
True 

当我们向图中添加一个循环时:

G.add_edge(4,1) # now we have a cycle 

我们得到:

>>> G 
1 2 3 
2 4 
3 
4 1 
 
 
>>> nx.is_directed_acyclic_graph(G) 
False 

我应该如何检查新边是否会导致循环?到目前为止我想出的最好的是:

def add_dependency(G, n1, n2): 
    if n2 in nx.ancestors(G, n1): 
        print('this will create a cycle') 
    else: 
        print(f"add {n2} as edge of {n1}") 
        G.add_edge(n1, n2) 

有更好的方法吗?

请您参考如下方法:

在可读性和内存消耗方面,您的代码最适合 networkx。请注意,许多问题(尤其是图论中的问题)都在时间和内存消耗之间进行权衡。

在您的情况下,您不知道新边是否会创建一个循环,因此您必须重新计算节点内祖先并检查它们(因此我建议您使用您的代码)。但是如果你有密集的图并且大多数新边都不正确,你将不得不反复重新计算祖先。但是您可以预先计算每个节点的祖先并将它们存储在集合的字典中:d = {n: nx.ancestors(DAG, n) for n in DAG} 搜索复杂度将是 O(1) 但每次添加边都会导致许多节点祖先重新计算。