poset的高效增量实现

Question

我使用SQLAlchemy实现了一个具有Partially Ordered Set的数学特性的结构，其中我需要能够一次添加和删除一条边。我使用两个邻接列表，一个是赋值列表（Hass图中的近似边），因为我需要保留哪些对明确设置为有序，而另一个邻接list是第一个的传递闭包，所以我可以高效地查询一个节点是否相对于另一个节点进行排序。现在，每当向分配邻接列表中添加或删除边缘时，我都会重新计算传递闭包。

它看起来是这样的：

assignment = Table('assignment', metadata, 
    Column('parent', Integer, ForeignKey('node.id')), 
    Column('child', Integer, ForeignKey('node.id'))) 

closure = Table('closure', metadata, 
    Column('ancestor', Integer, ForeignKey('node.id')), 
    Column('descendent', Integer, ForeignKey('node.id'))) 

class Node(Base): 
    __tablename__ = 'node' 
    id = Column(Integer, primary_key=True) 

    parents = relationship(Node, secondary=assignment, 
     backref='children', 
     primaryjoin=id == assignment.c.parent, 
     secondaryjoin=id == assignment.c.child) 

    ancestors = relationship(Node, secondary=closure, 
     backref='descendents', 
     primaryjoin=id == closure.c.ancestor, 
     secondaryjoin=id == closure.c.descendent, 
     viewonly=True) 

    @classmethod 
    def recompute_ancestry(cls.conn): 
     conn.execute(closure.delete()) 
     adjacent_values = conn.execute(assignment.select()).fetchall() 
     conn.execute(closure.insert(), floyd_warshall(adjacent_values)) 

其中floyd_warshall()是同一个名字的算法的实现。

这导致我有两个问题。首先，它似乎不是非常有效，但我不确定我可以使用什么样的算法。

第二个是更大约具有显式调用Node.recompute_ancestry()每一个分配发生时的实用性，并且仅后的分配被冲入会话，并用适当的连接。如果我想查看ORM中反映的更改，我必须再次清空会话。我认为，如果我能够用orm来表达重新计算的祖先操作，那将会容易得多。

Answer 1

好吧，我去并解决了我自己的问题。其原始部分是将Floyd-Warshall算法应用于父节点的祖先的后代与子节点的后代的祖先的交点，但是仅将输出应用于联合父母的祖先和孩子的后代。我花了很多时间在上面，我最终发布了on my blog的流程，但这里是代码。

from sqlalchemy import * 
from sqlalchemy.orm import * 
from sqlalchemy.ext.declarative import declarative_base 

Base = declarative_base() 

association_table = Table('edges', Base.metadata, 
    Column('predecessor', Integer, 
      ForeignKey('nodes.id'), primary_key=True), 
    Column('successor', Integer, 
      ForeignKey('nodes.id'), primary_key=True)) 

path_table = Table('paths', Base.metadata, 
    Column('predecessor', Integer, 
      ForeignKey('nodes.id'), primary_key=True), 
    Column('successor', Integer, 
      ForeignKey('nodes.id'), primary_key=True)) 

class Node(Base): 
    __tablename__ = 'nodes' 
    id = Column(Integer, primary_key=True) 
    # extra columns 

    def __repr__(self): 
     return '<Node #%r>' % (self.id,) 

    successors = relationship('Node', backref='predecessors', 
     secondary=association_table, 
     primaryjoin=id == association_table.c.predecessor, 
     secondaryjoin=id == association_table.c.successor) 

    before = relationship('Node', backref='after', 
     secondary=path_table, 
     primaryjoin=id == path_table.c.predecessor, 
     secondaryjoin=id == path_table.c.successor) 

    def __lt__(self, other): 
     return other in self.before 

    def add_successor(self, other): 
     if other in self.successors: 
      return 
     self.successors.append(other) 
     self.before.append(other) 
     for descendent in other.before: 
      if descendent not in self.before: 
       self.before.append(descendent) 
     for ancestor in self.after: 
      if ancestor not in other.after: 
       other.after.append(ancestor) 

    def del_successor(self, other): 
     if not self < other: 
      # nodes are not connected, do nothing! 
      return 
     if not other in self.successors: 
      # nodes aren't adjacent, but this *could* 
      # be a warning... 
      return 

     self.successors.remove(other) 

     # we buld up a set of nodes that will be affected by the removal 
     # we just did. 
     ancestors = set(other.after) 
     descendents = set(self.before) 

     # we also need to build up a list of nodes that will determine 
     # where the paths may be. basically, we're looking for every 
     # node that is both before some node in the descendents and 
     # ALSO after the ancestors. Such nodes might not be comparable 
     # to self or other, but may still be part of a path between 
     # the nodes in ancestors and the nodes in descendents. 
     ancestors_descendents = set() 
     for ancestor in ancestors: 
      ancestors_descendents.add(ancestor) 
      for descendent in ancestor.before: 
       ancestors_descendents.add(descendent) 

     descendents_ancestors = set() 
     for descendent in descendents: 
      descendents_ancestors.add(descendent) 
      for ancestor in descendent.after: 
       descendents_ancestors.add(ancestor) 
     search_set = ancestors_descendents & descendents_ancestors 

     known_good = set() # This is the 'paths' from the 
          # original algorithm. 

     # as before, we need to initialize it with the paths we 
     # know are good. this is just the successor edges in 
     # the search set. 
     for predecessor in search_set: 
      for successor in search_set: 
       if successor in predecessor.successors: 
        known_good.add((predecessor, successor)) 

     # We now can work our way through floyd_warshall to resolve 
     # all adjacencies: 
     for ancestor in ancestors: 
      for descendent in descendents: 
       if (ancestor, descendent) in known_good: 
        # already got this one, so we don't need to look for an 
        # intermediate. 
        continue 
       for intermediate in search_set: 
        if (ancestor, intermediate) in known_good \ 
          and (intermediate, descendent) in known_good: 
         known_good.add((ancestor, descendent)) 
         break # don't need to look any further for an 
           # intermediate, we can move on to the next 
           # descendent. 


     # sift through the bad nodes and update the links 
     for ancestor in ancestors: 
      for descendent in descendents: 
       if descendent in ancestor.before \ 
         and (ancestor, descendent) not in known_good: 
        ancestor.before.remove(descendent) 

Answer 2

更新关闭您插入，并在ORM方面这样做：在纯SQL

def add_assignment(parent, child): 
"""And parent-child relationship between two nodes""" 
    parent.descendants += child.descendants + [child] 
    child.ancestors += parent.ancestors + [parent] 
    parent.children += child 

如果您需要删除的任务，这是速度快：

def del_assignment(parent, child): 
    parent.children.remove(child) 
    head = [parent.id] + [node.id for node in parent.ancestors] 
    tail = [child.id] + [node.id for node in child.descendants] 
    session.flush() 
    session.execute(closure.delete(), and_(
      closure.c.ancestor.in_(head), 
      closure.c.descendant.in_(tail))) 
    session.expire_all()