さて、私は行って、自分の問題の解決策を考え出しました。その大まかな部分は、親ノードの祖先の子孫と子ノードの子孫の祖先の交点にFloyd-Warshallアルゴリズムを適用することですが、出力を親の祖先の和集合にのみ適用します。子供の子孫。私はそれに多くの時間を費やし、ブログにプロセスを投稿することになりましたが、ここにコードがあります。
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)