Use this if you are using igraph from R
feedback_arc_set {igraph} | R Documentation |
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"))
graph |
The input graph |
weights |
Potential edge weights. If the graph has an edge
attribute called ‘ |
algo |
Specifies the algorithm to use. “ |
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).
An edge sequence (by default, but see the return.vs.es
option
of igraph_options
) containing the feedback arc set.
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)
feedback_arc_set(g, algo="approx")