algorithm - 保持图形没有循环或菱形

我想在hibernate/sql中维护一个没有循环或菱形的有向图（即：一个简单的多对多自关联）。
我所说的“无菱形”是指从任何节点到任何其他节点的“路径”都不超过一条。我相信这两条规则意味着每个节点都可以被看作是两棵树的根，一棵树往一个方向走，另一棵树往另一个方向走。
有没有一个著名的算法来解决这个问题？这个问题可以归结为：“假设这个图目前是格式良好的，如果我在A和B之间画一个弧，这会产生一个循环还是一个菱形？”？

最佳答案

如果只添加边而不删除边，则认为可以通过使图形也具有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)

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

关于algorithm - 保持图形没有循环或菱形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10670907/