维护没有周期或钻石的图形

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) 

正如我所说，这只适用于如果你永远不会删除任何边缘。这样做需要为新分离的图段重建不相交集，这可能非常缓慢。如果你只会很少移除边缘（比你增加的次数要少很多倍），走这条路可能还是合理的。