存在循环时的拓扑排序算法

Question

一些编程语言(如 haskell )允许模块之间的循环依赖。由于编译器在编译一个模块时需要知道所有导入模块的所有定义，如果一些模块相互导入或发生任何其他类型的循环，它通常需要做一些额外的工作。在这种情况下，编译器可能无法像没有导入周期的模块那样优化代码，因为导入的函数可能尚未被分析。通常只有一个循环模块必须以这种方式编译，因为二进制对象没有依赖性。我们称这样的模块为loop-breaker

特别是如果导入周期交错，知道在编译由数百个模块组成的大型项目时如何最大程度地减少循环中断器的数量是很有趣的。

是否有一种算法可以在给定一组依赖项的情况下输出最少数量的模块，这些模块需要被编译为循环断路器才能成功编译程序？

例子

我试图阐明我在这个例子中的意思。

考虑一个包含四个模块A、B、C 和D 的项目。这是这些模块之间的依赖关系列表，条目 X y 表示 y 依赖于 x:

A CA DB AC BD B

可视化为 ASCII 图的相同关系:

D ---> B^    / ^|   /  ||  /   || L    |A ---> C

此依赖关系图中有两个循环:ADB 和ACB。例如，要打破这些循环，可以将模块 C 和 D 编译为循环断路器。显然，这不是最好的方法。将 A 编译为循环断路器完全足以打破两个循环，您需要少编译一个模块作为循环断路器。

Answer 1

这是 NP 难(和 APX 难)问题，称为 minimum feedback vertex set .由于 Demetrescu and Finocchi (pdf, Combinatorial Algorithms for Feedback Problems in Directed Graphs (2003)") 的近似算法正如我对您的应用程序所期望的那样，当没有长的简单循环时，在实践中效果很好。