python – poset的高效增量实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – poset的高效增量实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5343字，纯文字阅读大概需要8分钟。

内容图文

我在SQLAlchemy方面实现了一个具有Partially Ordered Set数学特性的结构,我需要能够一次添加和删除一个边.

在我目前的最佳设计中,我使用了两个邻接列表,一个是赋值列表(大约是Hass图中的边缘),因为我需要保留哪些节点对被显式设置为有序,另一个邻接列表是传递关闭第一个,这样我就可以有效地查询一个节点是否相对于另一个节点进行了排序.现在,每次在赋值邻接列表中添加或删除边时,我都会重新计算传递闭包.

它看起来像这样：

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表达重新计算的祖先操作,那将会容易得多.

解决方法:

好吧,我去解决了我自己的问题.它的原始部分是将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)

内容总结

以上是互联网集市为您收集整理的python – poset的高效增量实现全部内容，希望文章能够帮你解决python – poset的高效增量实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端