python - 寻找独立集的算法

Question

亲们，我有个问题。我正在用 python 编写一个脚本，它由几个模块组成。有些模块依赖于其他模块，因此只有在依赖模块成功运行后才能运行它们。因此，每个模块都派生自基类模块并覆盖名为 DEPENDENCIES 的列表，该列表是运行此模块之前要满足的依赖项列表。有一个模块需要在所有其他模块之前运行。目前我正在做这样的事情。

modules_to_run.append(a)
modules_to_run.append(b)
modules_to_run.append(c)
.....
.....     
modules_to_run.append(z)


# Very simplistically just run the Analysis modules sequentially in
# an order that respects their dependencies
foundOne = True
while foundOne and len(modules_to_run) > 0:
    foundOne = False
    for module in modules_to_run:
        if len(module.DEPENDENCIES) == 0:
            foundOne = True
            print_log("Executing module %s..." % module.__name__, log)
            try:
                module().execute()
                modules_to_run.remove(module)
                for module2 in modules_to_run:
                    try:
                        module2.DEPENDENCIES.remove(module)
                    except:
                        #module may not be in module2's DEPENDENCIES
                        pass
            except Exception as e:
                print_log("ERROR: %s did not run to completion" % module.__name__, log)
                modules_to_run.remove(module)
                print_log(e, log)

for module in modules_to_run:
    name = module.__name__
    print_log("ERROR: %s has unmet dependencies and could not be run:" % name, log)
    print_log(module.DEPENDENCIES, log)

现在我看到一些模块执行时间很长，脚本 tun 时间太长。所以我想让它成为多线程，这样独立的模块可以同时运行，从而节省时间。所以我想要一个解决方案，在每次迭代之后，我将重新计算“n”个独立模块(其中“n”是最大线程数，通常是 2 个开始)并并行执行它们并等待它们在下一次迭代之前完成.我不太了解算法，所以我被困住了。你们能不能帮我找到一个算法，在每次迭代后找到最大 'n' 组独立模块，这些模块之间没有任何依赖关系。

Answer 1

我发布了 topological sorting 的描述最近in a question about make -j .机缘巧合!来自维基百科文章:

The canonical application of topological sorting (topological order) is in scheduling a sequence of jobs or tasks; topological sorting algorithms were first studied in the early 1960s in the context of the PERT technique for scheduling in project management (Jarnagin 1960). The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes to dry). Then, a topological sort gives an order in which to perform the jobs.

粗略的轮廓:

1. 构建依赖关系图。
2. 找到 n 个没有依赖关系的模块。这些现在可以并行执行。
3. 从图中删除这些模块。
4. 重复第 2 步直到完成。

阅读这些链接以获得更详细的描述。