Is there an efficient way to add a node to a Digraph without causing a cycle in networkx?

Question

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?

Answer 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.