title: convert cyclic to acyclic graph
body: <p>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.</p>
  <p>I want to write a program to do it and any directions will be useful. for example consider this below graph.</p>
  <pre><code>A-&gt;B
  B-&gt;C
  C-&gt;A
  </code></pre>
  <p>I saw a solution in an <strong>MIT</strong> 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 <strong>DAG</strong> but conveys the same path information.</p>
  <p><strong>[See 46:59]</strong></p>
  <p><a href="https://www.youtube.com/watch?v=OQ5jsbhAv_M" rel="nofollow noreferrer">https://www.youtube.com/watch?v=OQ5jsbhAv_M</a>
  <em>Edit</em>:
  There is an explanation of turning cyclic graphs into dags in this MIT recitation at 36:57
  <a href="https://youtu.be/IFrvgSvZA0I" rel="nofollow noreferrer">https://youtu.be/IFrvgSvZA0I</a></p>
  <p>Se also Wikipedia : <a href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)" rel="nofollow noreferrer">cycle</a> and <a href="https://en.wikipedia.org/wiki/Tree_(graph_theory)#Forest" rel="nofollow noreferrer">forest</a>
  <strong>Edit:</strong></p>
  <p>I want to apply dynamic programming over a problem which is a cyclic graph <em>e.g)</em> say shortest path problem <code>Delta(S,D) where S-&gt; Source node and D-&gt;Destination node</code>. 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.</p>