我使用SQLAlchemy實現了一個具有Partially Ordered Set的數學特性的結構,其中我需要能夠一次添加和刪除一條邊。我使用兩個鄰接列表,一個是賦值列表(Hass圖中的近似邊),因爲我需要保留哪些對明確設置爲有序,而另一個鄰接list是第一個的傳遞閉包,所以我可以高效地查詢一個節點是否相對於另一個節點進行排序。現在,每當向分配鄰接列表中添加或刪除邊緣時,我都會重新計算傳遞閉包。poset的高效增量實現
它看起來是這樣的:
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來表達重新計算的祖先操作,那將會容易得多。