python - 如何使用 Python 创建 DAG（用于基于依赖项的任务执行。）

Question

我正在尝试用 python 编写一个程序，它将使用并行和/或串行执行尽可能高效地执行以下任务。这些任务对它们中的每一个都有依赖关系，并且为了执行任务，必须执行其所有依赖关系。

IE。只有在之前执行过任务 B、C、D 时，才能执行任务 A。我们还可以看到任务 C、H、J 没有依赖关系，因此它们可以并行执行。

我意识到它可以在有向无环图的帮助下完成，但我不确定如何使用以下列表创建 DAG。非常感谢任何帮助。谢谢！！

"A" : ["B", "C", "D"],
"B" : ["E"],
"C" : [],
"D" : ["C", "F"],
"E" : ["H"],
"F" : ["B", "C"],
"G" : ["H", "C"],
"H" : [],
"I" : ["H", "C", "F"],
"J" : []

标签： pythonmatplotlibnetworkxgraph-theorydirected-acyclic-graphs

Answer 1

这称为“拓扑排序”。有几个 Python 模块可以做到这一点，包括https://pypi.org/project/toposort/。请注意，Linux 包含一个可以执行此操作的命令行工具tsort，无需编程。