ruby-on-rails - 反转有向无环图 (DAG) 中的关系以避免循环关系

Question

问题

在 directed acyclic graph (DAG) 中, 是否总是通过反转要添加的关系来防止由添加关系引起的循环传递关系？

例子:

• 现有关系:A -> B , B -> C ，由此传递关系 A -> C , 所以它可以被视为 A -> B -> C
• 要添加的关系:C -> A这会导致 A -> B -> C -> A并且是循环的
• 想法:反转要添加到C <- A的关系这将导致 A -> B -> C <- A因此仍然是非循环的

这里给出的例子当然很简单，所以我很想知道这种方法是否适用于所有场景。

背景

要对实体之间的定向关系(例如“跟随”、“先行”、“父”、“子”)建模，OpenProject应用程序将其关系信息存储在 directed acyclic graph (DAG) 中.实体/节点具有日期信息并且可以由用户重新安排。如果用户更改日期值，则可能需要自动重新安排其他实体，例如当前任转移到 future 两天后，其继任者也需要转移。

因为大多数关系都用于调度，并且正是由于这个原因它是一个无环图，所以循环被阻止了。它们会导致无限的调度循环。

虽然从语义的角度来看，大多数关系也有方向，但也有一般的“关联”关系，对用户来说是无向的，只是传达存在某种关系。由于其性质，DAG 中存在的“关联”关系的方向方面对于前端用户是不可见的。

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

这个问题有几个可能的解决方案，最简单的可能是在 DAG 内的方向对这种关系的用户来说无关紧要的情况下简单地反转关系。

Answer 1

您的解决方案似乎有效。边 C -> A 和 A -> C 不能同时导致循环。

证明:

如果添加 C -> A 会导致循环，则已经存在路径 A ↝ C。如果添加 A -> C 会导致循环，则已经存在路径 C ↝ A。如果以上两种情况都为真，那么组合这两条路径将提供一个已经存在的循环，因此初始图将不是 DAG。