7
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
0
2
$\begingroup$

You can always make a digraph acyclic by removing all edges. The goal in feedback arc set is to remove the minimum number of edges, or in the weighted case, to minimize the total weight of edges removed. In your case, you can make the graph acyclic by removing any of the edges.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Lance Pollard
    Commented Apr 10, 2018 at 7:46
  • $\begingroup$ Wondering if there is a field of research studying the example expansion: iteration1 -> iteration2 -> iteration3 ... iterationBound "expanding directed cycles into flat lists" $\endgroup$
    – Lance Pollard
    Commented Apr 10, 2018 at 8:49
  • $\begingroup$ It's usually called "loop unrolling". $\endgroup$
    – Yuval Filmus
    Commented Apr 10, 2018 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.