Есть ли эффективный способ добавить узел в Digraph, не вызывая цикл в сети x? - PullRequest
1 голос
/ 30 апреля 2019

Я рассматриваю использование 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)

Есть ли лучший способ сделать это?

1 Ответ

1 голос
/ 06 мая 2019

Ваш код наиболее оптимален для networkx в случае читабельности и потребления памяти.Обратите внимание, что многие проблемы (особенно в теории графов) компенсируются между временем и потреблением памяти.

В вашем случае вы не можете знать, создаст ли новый фронт цикл, поэтому вам придется пересчитатьпредайте узлы и проверяйте их (поэтому я рекомендую вам использовать ваш код).Но если у вас плотный график и большинство новых ребер неверны, вам придется повторно пересчитывать предков.Но вы можете предварительно рассчитать предков каждого узла и сохранить их в формате наборов: d = {n: nx.ancestors(DAG, n) for n in DAG} Сложность поиска будет O(1), но каждое добавление ребер приведет к пересчету предков многих узлов.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...