3

I'm looking at using networkx to create and maintain a Directed Acyclic Graph(DAG).

What is the preferred way to check if adding an edge will cause the DiGraph to no longer be a DAG?

for an example graph:

import networkx as nx


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

we get:

>>> G
1 2 3
2 4
3
4


>>> nx.is_directed_acyclic_graph(G)
True

when we add a cycle to the graph:

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

we get:

>>> G
1 2 3
2 4
3
4 1


>>> nx.is_directed_acyclic_graph(G)
False

How should I check if a new edge will cause a cycle? The best I've come up with so far has been something like:

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)

Is there a better way to do this?

Grant Williams
  • 1,469
  • 1
  • 12
  • 24
  • 1
    See this answer. Seems like you should just add the edge then check if it is still a DAG. If not, delete the edge you just added. https://stackoverflow.com/questions/20246417/how-to-detect-if-adding-an-edge-to-a-directed-graph-results-in-a-cycle – scomes Apr 30 '19 at 19:52

1 Answers1

1

Your code is the most optimal for networkx in case of readability and memory consumption. Note, that many problems (especially in graph theory) are trading off between time and memory consumption.

In your case, you can't know if the new edge will create a cycle so you have to recalculate in-node ancestors and check them (so I recommend you to use your code). But if you have dense graph and most new edges are incorrect, you will have to recalculate ancestors repeatedly. But you can to pre-calculate each node's ancestors and store them in the dict of sets: d = {n: nx.ancestors(DAG, n) for n in DAG} The search complexity will be O(1) but each edge addition will cause many nodes ancestors recalculation.

vurmux
  • 9,420
  • 3
  • 25
  • 45