问题
在有向无环图(DAG)中,由添加关系引起的循环传递关系是否总是通过反转要添加的关系来阻止?
示例:
- 现有关系:
A -> B
,B -> C
,由此得到传递关系A -> C
,因此可视为A -> B -> C
- 要添加的关系:
C -> A
,它将导致A -> B -> C -> A
并且是循环的 -
想法:反转要添加到
C <- A
的关系,这将导致A -> B -> C <- A
,因此仍然是非循环的
这里给出的例子当然很简单,所以我很想知道这种方法是否在所有情况下都可行。
背景
为了对实体之间的有向关系(例如"follow"、"before"、"parent"、"child")进行建模,OpenProject应用程序将其关系信息存储在有向无环图(DAG)中。实体/节点具有日期信息,可以由用户重新安排。如果用户更改日期值,则可能需要自动重新安排其他实体,例如,当前一个实体被移到未来两天时,其后一个实体也需要被移。
因为大多数关系都用于调度,而且正是因为这个原因,它是一个非循环图,所以可以防止循环。它们将导致无限的调度循环。
虽然从语义的角度来看,大多数关系也有方向,但也有通用的"关系到"关系,它对用户来说是无方向的,只是传达存在某种关系。由于其性质,DAG中存在的"相关"关系的方向方面对前端的用户不可见。
当用户试图创建"关联到"关系时,他目前可能会遇到警告循环关系的错误消息,这对用户来说是不可理解的,因为他对关系的感知是无方向的。
这个问题有几种可能的解决方案,最简单的可能是在这种情况下简单地反转关系,因为DAG内的方向对这种关系的用户来说并不重要。
您的解决方案似乎有效。边缘CCD_ 9和CCD_。
证明:
如果添加C -> A
将导致循环,则已经存在路径A ↝ C
。如果添加A -> C
将导致循环,则已经存在路径C ↝ A
。如果以上两种情况都成立,那么将两条路径组合将提供一个已经存在的循环,因此初始图将不是DAG。