拓扑排序，但要按一定类型进行分组。

Question

似乎这是一个常见的调度问题，但我没有看到解决方案，甚至不知道如何称呼这个问题。它类似于拓扑排序，但又不同......

假设有一些依赖关系，比如：

A -> B -> D -- that is, A must come before B, which must come before D
A -> C -> D

拓扑排序可能有多种解决方案：

    A, B, C, D
and A, C, B, D

两种方案都可行。

我需要一个算法，它返回这个结果：

(A) -> (B,C) -> (D)

那就是，先执行A，然后执行所有的B和C，然后才能执行D。所有的不确定性或无关紧要的事情都被分组在一起。

我认为像Topological Sort with Grouping这样的算法无法正确处理以下情况。

A -> B -> C -> D -> E
A - - - > M - - - > E

为此，算法应返回：

(A) -> (B, C, D, M) -> (E)

This

A -> B -> D -> F
A -> C -> E -> F

应该返回

(A) -> (B, D, C, E) -> (F)

虽然这个

A -> B -> D -> F
A -> C -> E -> F
     C -> D
     B -> E

应该返回

(A) -> (B, C) -> (D, E) -> (F)    

And this

A -> B -> D -> F
A -> C -> E -> F
A -> L -> M -> F
     C -> D
     C -> M
     B -> E
     B -> M
     L -> D
     L -> E

应该返回

(A) -> (B, C, L) -> (D, E, M) -> (F)    

这个问题有一个名字和常规解决方案吗？（并且在Topological Sort with Grouping发布的算法是否正确处理此问题？）

编辑以回答更多示例请求：

A->B->C
A->C 

应该返回

(A) -> (B) -> (C). That would be a straight topological sort.

And

A->B->D
A->C->D
A->D

应该返回

(A) -> (B, C) -> (D)

并且

A->B->C
A->C
A->D

应该返回

(A) -> (B,C,D)

- JPM

---

A->C 是预期的答案，因为它可以通过转换 A->B->C 来获得。 - ElKamina

抱歉打扰您，A->B->D、A->C->D、A->D 这几个怎么样？ - ElKamina

哦，真的吗！最后一个了！A->B->C，A->C，A->D。 - ElKamina

(A) -> (B,C,D) 不正确，对吧？因为 B -> C？ - ElKamina

将 A -> B -> C -> D -> E; A -> M -> E 解释为 (A) -> (B, C, D, M) -> (E)，我认为这种解释非常可疑。答案说“B、C和D的顺序不重要”，但数据表明“B必须在C之前，C必须在D之前”。 - Jonathan Leffler

Answer 1

让 G 成为图的传递闭包。让 G' 成为从 G 中去除方向并取补集的无向图。G' 的连通分量是您要寻找的集合。

- wye.bee

---

好的，现在我需要弄清那意味着什么。感谢你的提示！ - JPM

现在我明白了。现在我需要想办法在XSLT中编写它。谢谢wye-bee！ - JPM