R igraph 手册页

feedback_arc_set {igraph}

R 文档

在图中查找反馈弧集

描述

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

用法

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

参数

图	输入图
权重	潜在的边权重。如果图具有名为“weight”的边属性，并且此参数为 NULL，则自动使用边属性。反馈弧集问题的目标是找到总权重最小的反馈弧集。
算法	指定要使用的算法。“exact_ip” 使用精确整数规划算法解决反馈弧集问题，该算法保证移除的边的总权重尽可能小。“approx_eades” 使用来自 Eades、Lin 和 Smyth 的快速（线性时间）近似算法。“exact” 是 “exact_ip” 的别名，而 “approx” 是 “approx_eades” 的别名。

详细信息

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

值

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

参考

Peter Eades, Xuemin Lin 和 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")

---