# 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 -> b
b -> c
c -> d
d -> a


Or a for loop flattened out such as:

somemethod -> forloop start
forloop start -> forloop next
forloop next -> forloop result
forloop next -> forloop next // i+1
forloop next -> forloop end
forloop end -> forloop result
forloop result -> next method


Wondering how you can possibly remove the cycles from a graph like that.

• Didn't realize it was that simple. Was thinking maybe (for the for loop) you would specify a maximum bound and then do iteration1 -> iteration2 -> iteration3 ... iterationBound -> next method. Wondering if there's any tricks like that to turn things acyclic. For a-b-c-d-a, I can't think of anything other than what you're suggesting. – Lance Pollard Apr 10 '18 at 7:46
• Wondering if there is a field of research studying the example expansion: iteration1 -> iteration2 -> iteration3 ... iterationBound "expanding directed cycles into flat lists" – Lance Pollard Apr 10 '18 at 8:49