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

Question

我正在考虑使用 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)

有更好的方法吗？

Answer 1

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

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