Cycles.Fashwo
Adaptation of the FASH algorithm of Eades and Lin (1995) to handle edge weights and obligatory arcs. The algorithm tries to minimize the total weight of the returned feedback arc set. Obligatory arcs are respected and never returned in the feedback arc set, an exception is raised if the obligatory arcs form a cycle. The adapted algorithm is hereby called FASHWO: “feedback arc set heuristic + weights and obligations”.
For a graph G and any one of its feedback arc sets F, the graph G - F is obviously acyclic. If F is minimal, i.e., adding any of its edges to G - F would introduce a cycle, then reversing, rather than removing, the feedback arcs also gives an ayclic graph, G - F + F^R
. In fact, Eades and Lin define the feedback arc set as "a set of arcs whose reversal makes G acyclic".
module GB : sig ... end
exception Stuck of GB.G.vertex list
Raised if cycles remain and all the remaining vertexes are obligatory. The argument gives the list of remaining vertexes.
Return a minimal set of arcs whose removal or reversal would make the given graph acyclic.
By minimal, we mean that each arc in the returned list must be removed or reversed, i.e., none are superfluous. Since a heuristic is used, the returned list may not be a minimum feedback arc set. Finding the minimum feedback arc set, dually, the maximum acyclic subgraph is NP-hard for general graphs.