I have a directed acyclic graph G. I want to generate some data structure which would tell me which new given edges (u,v) would be allowed while keeping the graph acyclic.

For example, given the graph G ([A,B,C,D]) on the left, I want to generate the graph G_ ([A_,B_,C_,D_]) on the right, which contains all single new edges which would be allowed:

Of course, the graph G_ is itself cyclic, but each individual edge in G_ could be added to G alone without making G cyclic. Each time a new edge is added to G, I will recompute G_. Duplicate edges are allowed in G.

My first approach is the following:

1. Generate the transitive closure of the graph

2. Transpose the transitive closure. Let’s call this G_t

3. For each vertex u, get a list of its adjacent vertices in G_t. This list of vertices essentially tells me all the vs for which (u,v) would cause a cycle. Let’s call this list u_

4. Perform a difference of all vertices minus u_. The result is a list of all vs for which (u,v) is allowed.

I’m wondering if a) this is the best method and b) if this method/resulting graph already has a given name or is already known and encompassed in a single algorithm.

For context, the graph is likely to have between 10-100 vertices.