Я рассматриваю использование networkx для создания и поддержки Направленного ациклического графа (DAG) .
Какой предпочтительный способ проверить, приведет ли добавление ребра к тому, что DiGraph больше не будет 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)
Есть ли лучший способ сделать это?