Finding a feedback arc set in a graphSource:
A feedback arc set of a graph is a subset of edges whose removal breaks all cycles in the graph.
feedback_arc_set(graph, weights = NULL, algo = c("approx_eades", "exact_ip"))
The input graph
Potential edge weights. If the graph has an edge attribute called ‘
weight’, and this argument is
NULL, then the edge attribute is used automatically. The goal of the feedback arc set problem is to find a feedback arc set with the smallest total weight.
Specifies the algorithm to use. “
exact_ip” solves the feedback arc set problem with an exact integer programming algorithm that guarantees that the total weight of the removed edges is as small as possible. “
approx_eades” uses a fast (linear-time) approximation algorithm from Eades, Lin and Smyth. “
exact” is an alias to “
exact_ip” while “
approx” is an alias to “
An edge sequence (by default, but see the
igraph_options()) containing the feedback arc set.
Feedback arc sets are typically used in directed graphs. The removal of a feedback arc set of a directed graph ensures that the remaining graph is a directed acyclic graph (DAG). For undirected graphs, the removal of a feedback arc set ensures that the remaining graph is a forest (i.e. every connected component is a tree).
Peter Eades, Xuemin Lin and W.F.Smyth: A fast and effective heuristic for the feedback arc set problem. Information Processing Letters 47:6, pp. 319-323, 1993
g <- sample_gnm(20, 40, directed = TRUE) feedback_arc_set(g) #> + 4/40 edges from a1baf8f: #>  6->19 8->13 14-> 8 16-> 3 feedback_arc_set(g, algo = "approx") #> + 4/40 edges from a1baf8f: #>  6->19 8->13 14-> 8 16-> 3