Legend:
Library
Module
Module type
Parameter
Class
Class type
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".
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.