algorithm - 如何去除分级有向无环图中的无效边？

Question

下图示例是有向无环图的一部分，即 layered并进行清理，以便仅保留连接连续层的边缘。

所以我需要的是消除形成“捷径”的边缘，即在非连续层之间跳跃的边缘。

以下注意事项适用:

1. 蓝色环分层是有效的，因为从 83140 开始到 29518 结束，两个分支都有相同数量 (3) 的中间节点，并且在开始和结束节点之间没有更长的路径；
2. 从 94347 开始到 107263 结束的绿色环有一条无效边(已经红叉)，因为左分支只包含一个中间节点，而右分支包含三个中间节点；此外，由于该分支的第一条边已经有效——我们知道它属于有效的蓝色环——可以知道哪条边是要划掉的右边——否则就不可能知道应该分配哪一层到节点 94030，所以它应该被删除；
3. 如果我们在考虑绿色圆环之后考虑粉红色圆环，我们知道下面的红色交叉边将被移除。
4. 但是如果我们只考虑黄色环，两个分支似乎都是正确的(它们包含相同数量的内部节点)，但实际上它们看起来正确只是因为它们包含对称错误(快捷方式跳跃两个分支上相同数量的节点)。如果我们在本地取这个环，至少有一个分支会在错误的层中结束，所以有必要使用更多的全局数据来避免这个错误。

我的问题是:

1. 这个问题的制定和可能的解决方案涉及哪些典型的概念和操作？
2. 有算法吗？

Answer 1

首先，topologically sort图表。

现在从排好序的数组开始，开始breadth first search并尝试找到每个节点的适当“深度”(即距根的距离)。由于一个节点可以有多个父节点，对于一个节点 x , depth[x]是所有它的 parent 的深度加一的最大值。我们初始化 depth对于所有节点为 -1 .

现在在bfs遍历中，当我们遇到一个节点p ，我们尝试更新它所有 child 的深度 c , 其中depth[c] = max(depth[c],depth[p]+1) .现在有两种方法可以检测有捷径的 child 。

• 如果depth[p]+1 < depth[c] , 表示 c有一个深度高于 p 的父级.所以edge p to c必须是捷径。
• 如果depth[p]+1 > depth[c]和 depth[c]!=-1 , 表示 c有一个深度低于 p 的父级.所以p是一个更好的 parent ，而另一个 parent 是c必须有一个快捷方式 p .

在这两种情况下，我们标记 c有问题。

现在我们的目标是针对每个“有问题的”节点 x ，我们检查它的所有父级，其深度应该是 depth[x]-1 .如果它们中的任何一个的深度低于该深度，则该深度具有 x 的快捷边需要删除。

由于图可以有多个根，我们应该有一个变量来标记visited节点，并对任何未访问的节点重复上述操作。

这将对黄环问题进行排序，因为在我们访问任何节点之前，它的所有前任节点都已被访问并正确排序。这是由拓扑排序确保的。

(注意:我们可以通过一次传递来完成此操作。我们可以为所有节点维护一个 parent 变量，并在发生情况 2 时删除旧父节点的边，而不是标记有问题的节点。情况 1 应该很明显)