I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.)
Normally, when attempting to add an edge to a DAG that would cause a cycle, you instead detect the situation and abort. I'm seeking an algorithm that will instead attempt to add the new edge anyway, modifying the graph such that it still represents the same tree, potentially partially decompressing parts of the graph in order to avoid the cycle.
Does an efficient algorithm to do this already exist? I have been unable to find one in a perfunctory literature search, though I am not aware of the proper terminology for this operation, if one exists.
In this example, we are adding the edge F->C, which creates a cycle. To break this cycle, we can split the E node into one version of E with C as a parent and one version of E with D as a parent (notated E'), similarly with F and C.
Slightly more complicated example
In this example we have several more cases. The offending edge from F to D is highlighted. But there are several paths through the graph, some involving nodes upstream from D, some involving nodes downstream from D, and potentially some not involving D at all.
This graph is a compressed version of this tree:
where the highlighted copies of F are where placing D as a child is permissible. As you can see, these three nodes correspond to the three ways of reaching F' in the previous figure.
Motivating use case
In the game of Go, there is, in certain rulesets, the idea of superko, which forbids repetition of a previous board state. Such positions are usually very rare in practice. In order to efficiently search the game tree, we would want to take into account transpositions of sets of moves which leave the board the same, which is why a graph structure is useful, but in situations where a superko is possible the history of the position is also important, not just the current situation. So while F->C would be a legal move normally, it is only a legal move in situations where C is not part of the node's history, i.e. we went through node D instead of node C. So we would need to consider the cases separately.
I am aware of the DAG cycle detection algorithm, and it seems like it might be easy to adapt this algorithm to perform this task, but I cannot seem to make it work. I am also aware that it is not always possible to split a graph in this manner to remove the cycle.