如果存在循环,则进行拓扑排序的算法

Question

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

特别是如果导入周期是交错的,那么在编译由数百个模块组成的大项目时,如何最大限度地减少环路断路器的数量是很有趣的.

是否有一个算法给出一组依赖性输出最少数量的模块需要编译为循环断路器才能成功编译程序？

例

我试着澄清我在这个例子中的含义.

考虑与四个模块项目A,B,C和D.这是这些模块之间的依赖关系列表,输入X y方式y取决于x:

A C
A D
B A
C B
D B

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

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

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

Answer 1

这是NP-hard(和APX-hard)问题,称为最小反馈顶点集.Demetrescu和Finocchi的一种近似算法(pdf,有向图中的反馈问题的组合算法(2003)")在没有长的简单周期的情况下在实践中很有效,正如我对您的应用所期望的那样.