在 DAG 中，如何找到路径会聚的顶点？
In a DAG, how to find vertices where paths converge?
我有一种有向无环图，有一些限制。
- 只有一个"entry"个顶点
- 可以有多个叶子顶点
- 一旦一条路径分裂，该路径下的任何东西都不能到达另一条路径（下面的一些例子会更清楚）
- 可以有任意数量的 "split" 个顶点。它们可以嵌套。
- 一个"split"顶点可以分割成任意数量的路径。下面的例子只显示了 2 个路径，但它可能更多。
我的挑战如下：对于每个 "split" 顶点（任何至少有 2 个出边的顶点），找到其路径重新连接的顶点 - 如果存在这样的顶点。解决方案应尽可能高效。
示例 A：
example a
在这个例子中，顶点A是一个"split"顶点，它的"reconnect vertex"是F.
示例 B：
example b
在这里，有两个分裂顶点：A和E。对于它们来说，顶点G是重新连接的顶点。
示例 C：
example c
现在分裂的顶点有A、D、E三个，对应的重连顶点为：
- A -> K
- D -> K
- E -> J
示例 D：
example d
这里我们再次有三个分裂顶点：A、D 和 E。但是这次，顶点 E 没有重新连接的顶点，因为其中一条路径提前终止。
听起来你想要的是：
- 将出度为 0 的每个顶点连接到单个 终端顶点
- 构造边反转图的dominator tree。链接的维基百科文章指出了执行此操作的几个算法。
- 分裂顶点的 "reconnect vertex" 是它在边反转图中的直接支配者，即它在该支配树中的父代。这在您的原始图中称为 "postdominator" 。如果它是您添加的终端顶点，那么它在您的原始图形中没有重新连接的顶点。
这是在编译器和程序分析中识别post-支配者的问题。这通常用于计算控制流图中的控制依赖性。 "Advanced Compiler Design and Implementation" 是关于这些主题的很好的参考。
如果图形没有循环，那么@matt-timmermans 建议的解决方案 (a) 将起作用。
如果图形有环，则解决方案 (a) 可以报告虚假的 post-支配者。在这种情况下，基于网络流的方法效果更好。使用此方法计算 this paper 中非终止敏感控制依赖性的算法。基本思路是
- 在每个拆分节点处，沿每个出边向图中注入一个唯一标记，并且
- 通过受此约束的图传播令牌：如果节点 n 可从拆分节点 m 到达，则到达节点 m 的令牌仅在节点 m 的所有令牌都已到达节点 n 时通过节点 n。
最后，节点npost-如果节点m的所有令牌都到达节点n，则节点n支配节点m。
我有一种有向无环图，有一些限制。
- 只有一个"entry"个顶点
- 可以有多个叶子顶点
- 一旦一条路径分裂，该路径下的任何东西都不能到达另一条路径（下面的一些例子会更清楚）
- 可以有任意数量的 "split" 个顶点。它们可以嵌套。
- 一个"split"顶点可以分割成任意数量的路径。下面的例子只显示了 2 个路径，但它可能更多。
我的挑战如下：对于每个 "split" 顶点（任何至少有 2 个出边的顶点），找到其路径重新连接的顶点 - 如果存在这样的顶点。解决方案应尽可能高效。
示例 A：
example a
在这个例子中，顶点A是一个"split"顶点，它的"reconnect vertex"是F.
示例 B：
example b
在这里，有两个分裂顶点：A和E。对于它们来说，顶点G是重新连接的顶点。
示例 C：
example c
现在分裂的顶点有A、D、E三个，对应的重连顶点为：
- A -> K
- D -> K
- E -> J
示例 D：
example d
这里我们再次有三个分裂顶点：A、D 和 E。但是这次，顶点 E 没有重新连接的顶点，因为其中一条路径提前终止。
听起来你想要的是：
- 将出度为 0 的每个顶点连接到单个 终端顶点
- 构造边反转图的dominator tree。链接的维基百科文章指出了执行此操作的几个算法。
- 分裂顶点的 "reconnect vertex" 是它在边反转图中的直接支配者，即它在该支配树中的父代。这在您的原始图中称为 "postdominator" 。如果它是您添加的终端顶点，那么它在您的原始图形中没有重新连接的顶点。
这是在编译器和程序分析中识别post-支配者的问题。这通常用于计算控制流图中的控制依赖性。 "Advanced Compiler Design and Implementation" 是关于这些主题的很好的参考。
如果图形没有循环，那么@matt-timmermans 建议的解决方案 (a) 将起作用。
如果图形有环，则解决方案 (a) 可以报告虚假的 post-支配者。在这种情况下，基于网络流的方法效果更好。使用此方法计算 this paper 中非终止敏感控制依赖性的算法。基本思路是
- 在每个拆分节点处，沿每个出边向图中注入一个唯一标记，并且
- 通过受此约束的图传播令牌：如果节点 n 可从拆分节点 m 到达，则到达节点 m 的令牌仅在节点 m 的所有令牌都已到达节点 n 时通过节点 n。
最后，节点npost-如果节点m的所有令牌都到达节点n，则节点n支配节点m。