如何在Python中实现makefile风格的算法

Question

我正在用Python实现一个声学特征提取系统，我需要实现一个类似于makefile的算法，以确保特征提取系统中的所有模块按正确的顺序运行，并且不会重复任何特征提取的阶段。

这个特征提取系统的输入将是一个图，详细说明特征提取模块之间的链接，我想根据这个图来确定哪些函数在什么时候运行。

这样的系统的一个例子可能是：

            ,-> [B] -> [D] ----+
input --> [A]           ^      v
            `-> [C] ----+---> [E] --> output

而函数调用（假设每个模块X是一个形式为output = X(inputs)的函数）可能类似于：

a = A(input)
b = B(a)
c = C(a)
d = D(b,c)  # can't call D until both b and c are ready
output = E(d,c)   # can't call E until both c and d are ready

我已经将函数图加载为一个字典，每个字典条目的形式是(inputs, function)，像这样：

blocks = {'A' : (('input'), A),
          'B' : (('A'), B),
          'C' : (('A'), C),
          'D' : (('B','C'), D),
          'output' : (('D','C'), E)}

我现在对makefile算法到底是干什么的有些迷茫，也不知道该如何实现它。我的谷歌搜索似乎也没有太大帮助。如果有人能给我指个方向，推荐一个关于makefile算法的好讨论，那可能是个不错的开始。

Answer 1

blocks 实际上是一个用来表示（无环）依赖关系图的邻接表。简单来说，如果你想要按照正确的顺序来处理这些块，就可以进行一种叫做拓扑排序的操作。

Answer 2

如果你想了解很多编程语言里的代码，包括Python，可以看看这些Rosetta Code的链接：拓扑排序，还有拓扑排序/提取顶层项目。

Answer 3

拓扑排序