2

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

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

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

4

1 回答 1

0

如果您只添加边而不删除它们，则认为您可以通过使图形也具有不相交的集合语义来解决此问题。创建新边时，您首先要检查这两个节点是否已经不是同一集合的一部分。如果不是，您将创建链接并在集合上执行联合。

这是一些 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)

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

于 2012-05-20T07:18:37.643 回答