我正在考虑使用 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) 但每次添加边都会导致许多节点祖先重新计算。
