我想在 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/