algorithm - 维护没有循环或菱形的图形

Question

我想在 hibernate/sql 中维护一个没有循环或菱形的有向图(即:一个简单的多对多自关联)。

“无菱形”是指从任何节点到任何其他节点的“路径”不超过一条。我相信这两条规则意味着每个节点都可以被视为两棵树的根 - 一棵向一边走，一棵向另一棵走。

是否有一个众所周知的算法？问题归结为:“鉴于该图目前是良构的，如果我在 A 和 B 之间放置一条弧线，这会创建一个环还是一个菱形”？

Answer 1

如果您只添加边而不删除边，认为您可以通过让您的图表也有 disjoint set semantics 来解决这个问题。 .创建新边时，您首先要检查这两个节点是否不属于同一组。如果不是，您将创建链接并对集合执行联合。

这是一些 Python 代码，我希望这些代码足够接近伪代码，即使您不了解 Python 也能理解。

class Node:
    # constructor
    def __init__(self):
        self.setParent = None
        self.graphParents = []
        self.graphChildren = []

    # disjoint set operations
    def getSetRoot(self):
        if self.setParent == None:
            return self
        else:
            self.setParent = self.setParent.getSetRoot()
            return self.setParent

    def joinSet(self, other):
        other.getSetRoot().setParent = self.getSetRoot()

    # graph operation
    def addChild(self, child):
        if self.getSetRoot() == child.getSetRoot():
            raise ValueError("Cannot add child!")
        else:
            self.graphChildren.append(child)
            child.graphParents.append(self)
            self.joinSet(child)

正如我所提到的，这只有在您从不移除任何边的情况下才有效。这样做需要为新分离的图段重建不相交的集合，这可能会非常慢。如果您很少删除边(比添加的次数少很多倍)，那么走这条路可能仍然是合理的。