A feedback arc set of a graph is a subset of edges whose removal breaks all cycles in the graph.
Usage
feedback_arc_set(graph, weights = NULL, algo = c("approx_eades", "exact_ip"))
Arguments
- graph
The input graph
- weights
Potential edge weights. If the graph has an edge attribute called ‘
weight
’, and this argument isNULL
, 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.- algo
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
”.
Value
An edge sequence (by default, but see the return.vs.es
option
of igraph_options()
) containing the feedback arc set.
Details
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).
References
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
See also
Other structural.properties:
bfs()
,
component_distribution()
,
connect()
,
constraint()
,
coreness()
,
degree()
,
dfs()
,
distance_table()
,
edge_density()
,
girth()
,
is_acyclic()
,
is_dag()
,
is_matching()
,
k_shortest_paths()
,
knn()
,
laplacian_matrix()
,
reciprocity()
,
subcomponent()
,
subgraph()
,
topo_sort()
,
transitivity()
,
unfold_tree()
,
which_multiple()
,
which_mutual()
Graph cycles
girth()
,
has_eulerian_path()
,
is_acyclic()
,
is_dag()
Examples
g <- sample_gnm(20, 40, directed = TRUE)
feedback_arc_set(g)
#> + 8/40 edges from fd23293:
#> [1] 2-> 9 4->10 7-> 5 7-> 8 7->15 11->18 12-> 1 12-> 9
feedback_arc_set(g, algo = "approx")
#> + 8/40 edges from fd23293:
#> [1] 2-> 9 4->10 7-> 5 7-> 8 7->15 11->18 12-> 1 12-> 9