如果存在循环，则进行拓扑排序的算法 [英] Algorithm for topological sorting if cycles exist

问题描述

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

Some programming languages (like haskell) allow cyclic dependencies between modules. Since the compiler needs to know all definitions of all modules imported while compiling one module, it usually has to do some extra work if some modules import each other mutually or any other kind of cycle occurs. In that case, the compiler may not be able to optimize code as much as in modules that have no import cycles, since imported functions may have not yet been analyzed. Usually only one module of a cycle has to be compiled that way, as a binary object has no dependecies. Let's call such a module loop-breaker

特别是如果导入循环是交错的，那么有趣的是，如何最大程度地减少循环次数编译包含数百个模块的大型项目时会破坏-。

Especially if the import cycles are interleaved it is interesting to know, how to minimize the number of loop-breakers when compiling a big project composed of hundreds of modules.

是否存在一种算法，给定一组依赖项，输出的模块数量最少，需要编译为

Is there an algorithm that given a set of dependecies outputs a minimal number of modules that need to be compiled as loop-breakers to compile the program successfully?

我尝试弄清本示例中的含义。

I try to clarify what I mean in this example.

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

Consider a project with the four modules A, B, C and D. This is a list of dependencies between these modules, an entry X y means y depends on x:

A C
A D
B A
C B
D B

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

The same relation visualized as an ASCII-diagram:

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

此依存关系图中有两个循环： ADB 和 ACB 。为了打破这些循环，例如可以将模块 C 和 D 编译为循环中断器。显然，这不是最佳方法。将 A 编译为一个循环中断器完全可以打破两个循环，并且您需要将一个较少的模块编译为一个循环中断器。

There are two cycles in this dependency-graph: ADB and ACB. To break these cycles one could for instance compile modules C and D as loop-breakers. Obviously, this is not the best approach. Compiling A as a loop-breaker is completely sufficient to break both loops and you need to compile one less module as a loop-breaker.

推荐答案

这是被称为最小反馈顶点集。由于 Demetrescu和Finocchi（pdf，有向图反馈问题的组合算法（2003））在没有长的简单周期的情况下，在实践中效果很好，就像我期望的那样。

This is the NP-hard (and APX-hard) problem known as minimum feedback vertex set. An approximation algorithm due to Demetrescu and Finocchi (pdf, Combinatorial Algorithms for Feedback Problems in Directed Graphs (2003)") works well in practice when there are no long simple cycles, as I would expect for your application.

这篇关于如果存在循环，则进行拓扑排序的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！