convert cyclic to acyclic graph

Question

I want to convert a cyclic graph into an acyclic graph. Is there an pseudocode that can do this? I did try to search but most of them returned where mathematical based on markov chain or research articles.

I want to write a program to do it and any directions will be useful. for example consider this below graph.

A->B
B->C
C->A

I saw a solution in an MIT lecture but the lecture skimmed over it with reference to something taught earlier and couldn't catch it. In short it kind of replicates the nodes in layers in a way that the end graph denotes a DAG but conveys the same path information.

[See 46:59]

https://www.youtube.com/watch?v=OQ5jsbhAv_M Edit: There is an explanation of turning cyclic graphs into dags in this MIT recitation at 36:57 https://youtu.be/IFrvgSvZA0I

Se also Wikipedia : cycle and forest Edit:

I want to apply dynamic programming over a problem which is a cyclic graph e.g) say shortest path problem Delta(S,D) where S-> Source node and D->Destination node. Since DP over cyclic graph is infinite algorithm, we first need to convert the cyclic graph into acyclic graph and then apply the dynamic programming technique over it.

Answer 1

I believe you pointed out the wrong video, here it is (46:59): https://www.youtube.com/watch?v=OQ5jsbhAv_M

The idea exposed here, is to make several copies of the graph and to arrange them into layers. Each one represents the state of the graph at a given time, and for every edge traversed you go down by one layer. I did not find pseudo-code for this, but the way of doing this is detailed here: https://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-cyclic-graphs-acyclic