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

Question

问题

在有向无环图 (DAG)中，是否总是通过反转要添加的关系来防止由添加关系引起的循环传递关系？

例子：

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

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

背景

为了对实体之间的有向关系（例如，'follows'、'precedes'、'parent'、'child'）建模，OpenProject应用程序将其关系信息存储在有向无环图（DAG）中。实体/节点具有日期信息并且可以由用户重新安排。如果用户更改日期值，则可能需要自动重新安排其他实体，例如，当前任被转移到未来两天时，它的继任者也需要被转移。

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

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

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

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

标签： ruby-on-railsrubyalgorithmgraph-algorithm

Answer 1

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

证明：

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