I have a quite "common" need : making a directed graph (with one or several cycles) a directed acyclic graph (DAG).
But the way I want to achieve it is, I guess, way more specific : I would like to break cycles by duplicating nodes, and rerouting edges.
For exemple, for a graph with such a loop (
A > B > C > A) :
I would like to get a non-looping graph like this one :
So here :
- A new node
A'has been created (duplicated from
- The edge
C > Ahas been deleted, replaced by
C > A'
- Another edge
A' > Dis also created, to preserve "adjacency": it was possible to go from
Din the first graph, so I want this to be possible in the transformed graph too.
The case above may appear quite simple, but I am tryig to build an automated method to do that. I also have some cases with interwined cycles, which are way more complex to deal with. Finally, I aim to minimise the number of duplicated nodes. I usually work with graphs having less than 100 nodes.
The aim of all this is to be able to order nodes (using Kahn or DFS).
- In the exemple above,
A > B > C > A' > Dseems the most intuitive order.
A > D > B > C > A'would also be a valid order, but I think it is less intuitive.
This is also the reason for keeping the original
A > D arc, forcing the resulting order to be the first one mentionned above.
Any leads about how to do that ? Any existing methods or scripts (preferably python) ? During my research, I have never found any information about such a way to break cycles, maybe I have not searched enough, or maybe not in the good direction.
Note : this question has also been posted on StackOverflow [here]