How do I guarantee that a DAG stays acyclic after insertion of a node?

Question

I have a DAG storing the relation between certain objects in my application. When this structure is updated by adding a new vertex below an existing one (i. e., implicitly creating a new edge into the new vertex) and then (at any later time) a new edge from there to other vertices, I want to ensure that the graph stays a DAG, i. e. that my code does not create cycles.

Do I have to add a cycle detection to each inserting and connecting operation, or are there rules that I can follow on insertion which will guarantee that I'm not producing cycles?

One approach that I can think of is to store the topological level of each node and only allow new edges that point to higher levels (further away from the source nodes). However, it seems that this will actually rob me of a lot of the flexibility I was hoping to achieve by using a DAG instead of a set of ordinary trees.

Answer 1

You could also store reverse links and just check that the terminus node of the edge being added does not appear in any of the parent nodes of the origin node. This would be faster than doing a full cycle detection. Essentially this would be a shortest path algorithm on the reverse links, which for a DAG ought to be a linear operation.

As @Markus says, though, if you aren't creating links both to and from the new node to existing nodes, you shouldn't be able to create a cycle by introducing a new node to the graph.