查找图中的反馈弧集

图的反馈弧集是边的子集，移除这些边会破坏图中的所有环。

用法

feedback_arc_set(graph, weights = NULL, algo = c("approx_eades", "exact_ip"))

参数

graph

输入图

weights

潜在的边权重。如果图有一个名为‘weight’的边属性，并且此参数为NULL，则会自动使用该边属性。反馈弧集问题的目标是找到具有最小总权重的反馈弧集。

algo

指定要使用的算法。“exact_ip”使用精确整数规划算法解决反馈弧集问题，该算法保证移除边的总权重尽可能小。“approx_eades”使用来自 Eades、Lin 和 Smyth 的快速（线性时间）近似算法。“exact”是“exact_ip”的别名，而“approx”是“approx_eades”的别名。

值

一个边序列（默认情况，但请参见igraph_options()的return.vs.es选项），其中包含反馈弧集。

详细信息

反馈弧集通常用于有向图。移除有向图的反馈弧集可确保剩余图是有向无环图 (DAG)。对于无向图，移除反馈弧集可确保剩余图是森林（即，每个连通分量都是一棵树）。

参考文献

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

参见

其他 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()

图环 feedback_vertex_set(), find_cycle(), girth(), has_eulerian_path(), is_acyclic(), is_dag(), simple_cycles()

C 库中的相关文档

feedback_arc_set().

示例

g <- sample_gnm(20, 40, directed = TRUE)
feedback_arc_set(g)
#> + 5/40 edges from ce9f241:
#> [1]  9-> 8 15-> 9 15->10 16-> 3 16->12
feedback_arc_set(g, algo = "approx_eades")
#> + 5/40 edges from ce9f241:
#> [1]  9-> 8 15-> 9 15->10 16-> 3 16->12