有向无环图（DAG）中的逆关系可避免循环关系

Question

题

在有向无环图（DAG）中，是否总是通过反转要添加的关系来防止由于添加关系而导致的循环传递关系？

例：

• 现有关系：A -> B，B -> C以及通过该传递关系A -> C，因此可以将其视为A -> B -> C
• 要添加的关系：C -> A这将导致A -> B -> C -> A循环
• 想法：将要添加的关系求反，C <- A这将导致A -> B -> C <- A并因此仍然是非循环的

这里给出的示例当然很简单，因此我想知道这种方法在所有情况下是否可行。

背景

为了建模实体之间的有向关系（例如，“跟随”，“先行”，“父”，“子”），OpenProject应用程序将其关系信息存储在有向非循环图（DAG）中。实体/节点具有日期信息，并且可以由用户重新安排。如果用户更改日期值，则可能需要自动重新安排其他实体的时间，例如，当将前任转移到未来两天时，还需要转移其后继者。

由于大多数关系都用于调度，因此正因为它是一个非循环图，所以避免了循环。它们将导致无限的调度循环。

尽管大多数关系也从语义的角度出发指明方向，但也存在通用的“相对于”关系，该关系相对于用户是无向的，只是传达存在某种关系的信息。由于其性质，前端中的用户看不到DAG中存在的“与...相关”关系的方向方面。

当用户尝试创建“相对于”关系时，他当前可能会遇到错误消息，警告循环关系，这对于用户来说是不可理解的，因为他对关系的理解是无向的。

有两种可能的方法可以解决该问题，最简单的方法是在这种情况下简单地逆转该关系，因为DAG内的方向对于这种关系对用户而言并不重要。

Answer 1

您的解决方案似乎有效。边缘C -> A和A -> C两者都不能引起循环。

证明：

如果添加C -> A会导致循环，则已经存在路径A ? C。如果添加A -> C会导致循环，则已经存在路径C ? A。如果以上两个条件均成立，则将两个路径组合起来将提供一个已经存在的循环，因此初始图形将不是DAG。