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
“approx_eades”.
An edge sequence (by default, but see the return.vs.es option
of 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
Other structural.properties:
bfs(),
component_distribution(),
connect(),
constraint(),
coreness(),
degree(),
dfs(),
distance_table(),
edge_density(),
feedback_vertex_set(),
girth(),
is_acyclic(),
is_dag(),
is_matching(),
k_shortest_paths(),
knn(),
reciprocity(),
subcomponent(),
subgraph(),
topo_sort(),
transitivity(),
unfold_tree(),
which_multiple(),
which_mutual()
Graph cycles
feedback_vertex_set(),
find_cycle(),
girth(),
has_eulerian_path(),
is_acyclic(),
is_dag(),
simple_cycles()
g <- sample_gnm(20, 40, directed = TRUE)
feedback_arc_set(g)
#> + 5/40 edges from cd378b8:
#> [1] 9-> 8 15-> 9 15->10 16-> 3 16->12
feedback_arc_set(g, algo = "approx_eades")
#> + 5/40 edges from cd378b8:
#> [1] 9-> 8 15-> 9 15->10 16-> 3 16->12