允许图并发遍历的算法

Question

在描述一组要处理的任务的有向无环图中，我需要找到可以并发处理的所有任务。该图没有环且非常小(~1000 个节点，~2000 个边)，性能不是主要问题。

具有预期结果的示例:

• [] 是一个组。在继续之前必须处理组中的所有任务
• [x & y]表示x和y可以并发处理(x和y并行)
• x -> y 表示 x 和 y 必须按顺序处理(x 在 y 之前)

1

a -> [b & c] -> c

2

[a & e] -> b -> c -> [d & f]

3

[ [a -> b] & [e -> f] ] -> [ [c -> d] & g ]

我不想实际执行图，而是构建一个尽可能并行的数据结构，同时保持顺序。我不太熟悉算法的术语和名称，所以我很难在网上找到类似的问题/解决方案。

Answer 1

从数学上讲，我会将这个问题定义为找到一个最小定义的 series-parallel partial order扩展给定的偏序。

我将从 transitively reducing 开始图形并重复应用两种启发式方法。

1. 如果x有一个依赖y，y有一个依赖x，将它们合并成一个新节点z = [x → y]。
2. 如果x和y有相同的依赖关系和被依赖关系，将它们合并成一个新节点z = [x & y]。

现在，如果输入已经是串并联的，那么结果将是一个节点。然而，一般来说，这将留下一个嵌入 N 形结构的图，如问题中最后一个示例中的 b → c、b → g、f → g。必须通过添加 b → f、c → f、c → g、f → b、f → c、g → c 中的一个或多个来解决此结构。但在不同的情况下，这一行为会反过来创造新的 N 型结构。没有明显的闭包概念，这就是为什么这个问题对我来说很难。

其中一些选择似乎比其他选择更糟糕。例如，c → f 强制序列 b → c → f → g，而 f → c 是唯一不增加关键路径长度的选择。

我想我会尝试的是，

1. 如果启发式 1 和 2 没有目标，当且仅当 x 和 y 具有共同依赖或共同依赖时，形成一个边 x--y 的图，计算该图的连通分量，然后 &-merge非单例的最小组件，然后是另一个传递归约。