13

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

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

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

例子

我试图澄清我在这个例子中的意思。

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

交流电
广告
文学学士
CB
D B

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

D ---> B
^ / ^
| / |
| / |
| 大号 |
A ---> C

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

4

2 回答 2

19

这是被称为最小反馈顶点集的 NP-hard（和 APX-hard）问题。Demetrescu 和 Finocchi (pdf, Combinatorial Algorithms for Feedback Problems in Directed Graphs (2003)”)的近似算法在没有长简单循环的情况下在实践中运行良好，正如我对您的应用程序所期望的那样。

于 2012-05-15T20:18:06.753 回答
3

以下是如何在 Python 中执行此操作：

from collections import defaultdict

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    for h, t in dependency_pairs:
        num_heads[t] += 1
        tails[h].append(t)

    ordered = [h for h in tails if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.iteritems() if heads]
    return ordered, cyclic

def is_toposorted(ordered, dependency_pairs):
    '''Return True if all dependencies have been honored.
       Raise KeyError for missing tasks.
    '''
    rank = {t: i for i, t in enumerate(ordered)}
    return all(rank[h] < rank[t] for h, t in dependency_pairs)

print topological_sort('aa'.split())
ordered, cyclic = topological_sort('ah bg cf ch di ed fb fg hd he ib'.split())
print ordered, cyclic
print is_toposorted(ordered, 'ah bg cf ch di ed fb fg hd he ib'.split())
print topological_sort('ah bg cf ch di ed fb fg hd he ib ba xx'.split())

运行时间与边（依赖对）的数量成线性比例。

该算法是围绕一个名为 num_heads 的查找表组织的，该表保持对前辈的数量（传入箭头）进行计数。在ah bg cf ch di ed fb fg hd he ib示例中，计数为：

node  number of incoming edges
----  ------------------------
 a       0
 b       2
 c       0
 d       2
 e       1
 f       1  
 g       2
 h       2
 i       1

该算法通过“访问”没有前任的节点来工作。例如，节点a并且c没有传入边，因此首先访问它们。

访问意味着节点被输出并从图中移除。当一个节点被访问时，我们循环它的后继节点并将它们的传入计数减一。

例如，在访问节点a时，我们去它的后继节点h将其传入计数减一（这样h 2就变成了h 1.

同样，当访问节点时c，我们循环遍历它的后继者f和h，将它们的计数减一（这样f 1变成f 0和h 1变成h 0）。

节点不再有传入边，因此我们重复输出它们并从图中删除它们的过程，直到所有节点都被访问过f。h在示例中，访问顺序（拓扑排序为）：

a c f h e d i b g

如果 num_heads 曾经到达没有节点且没有传入边的状态，则意味着存在无法进行拓扑排序的循环并且算法退出。

于 2012-05-15T19:59:13.397 回答