python – poset的高效增量实现

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',ForeignKey('nodes.id'),primary_key=True),Column('successor',primary_key=True))

path_table = Table('paths',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)