algorithm - 具有最少违反边数的循环图的拓扑排序

Question

我正在寻找一种方法来对包含循环的给定有向未加权图执行拓扑排序。结果不仅应包含顶点的顺序，还应包含给定顺序所违反的边集。这组边应该是最小的。

由于我的输入图可能很大，我不能使用指数时间算法。如果不可能在多项式时间内计算出最优解，那么对于给定问题，什么样的启发式方法是合理的？

Answer 1

Eades、Lin 和 Smyth为反馈弧集问题提出了一种快速有效的启发式方法。原始文章位于付费墙后面，但可从此处获得免费副本。

有一种拓扑排序算法，它通过选择没有传入弧的顶点、在图上递归减去顶点并将该顶点添加到顺序来构建顶点顺序。（我正在递归地描述该算法，但您不必那样实现它。） Eades-Lin-Smyth 算法还查找没有输出弧的顶点并附加它们。当然，所有顶点都可能具有传入和传出弧。在这种情况下，选择传入和传出之间差异最大的顶点。毫无疑问，这里有试验的空间。

具有可证明的最坏情况行为的算法基于线性规划和图形切割。这些很简洁，但保证并不理想（log^2 n 或 log n log log n 是所需弧的倍数），我怀疑有效的实现将是一个相当大的项目。

Answer 2

受 Arnauds 答案和其他有趣的拓扑排序算法的启发，我创建了cyclic-toposort项目并将其发布在 github 上。cyclic_toposort完全符合您的要求，因为它可以快速对有向循环图进行排序，从而提供最少数量的违规边。如果需要，它还可以选择提供位于同一拓扑级别（因此可以同时激活）的最大节点分组。

如果问题仍然与您相关，那么如果您查看我的项目并让我知道您的想法，我会很高兴！

这个项目对我自己的神经网络拓扑研究很有用，所以无论如何我都必须创建这样的东西。我这么晚才回答你的问题，以防其他人偶然发现这个线程来寻找同样的问题。