How to remove cycles from a directed graph I saw this from SO which led to Feedback Arc Set, which describes the problem nicely:


  In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG).


I am wondering how this is done. Given a graph such as this:

a -&gt; b
b -&gt; c
c -&gt; d
d -&gt; a


Or a for loop flattened out such as:

somemethod -&gt; forloop start
forloop start -&gt; forloop next
forloop next -&gt; forloop result
forloop next -&gt; forloop next // i+1
forloop next -&gt; forloop end
forloop end -&gt; forloop result
forloop result -&gt; next method


Wondering how you can possibly remove the cycles from a graph like that.
There is a paper "breaking cycles in noisy hierarchies" which talks about leveraging graph hierarchy to delete cycle edges to reduce a directed graph to a DAG. 

The reduced DAG will maintain the graph hierarchy of the original graph as much as possible. 

The corresponding code is available on Github: https://github.com/zhenv5/breaking_cycles_in_noisy_hierarchies