class NoPathFoundError(Exception):
pass
def findShortestPath(src, tgt):
shortest_paths_from_src = {} # id -> []
shortest_paths_from_tgt = {} # id -> []
scheduled_visits_from_src = [] # distance, k, wr_obj, path
scheduled_visits_from_tgt = [] # distance, k, wr_obj, path
FROM_SRC = (scheduled_visits_from_src, shortest_paths_from_src)
FROM_TGT = (scheduled_visits_from_tgt, shortest_paths_from_tgt)
k = [0] # forces fifo in priority queues
def _schedule_visit((visit_queue, shortest_paths), obj, path):
k[0] += 1
shortest_paths[id(obj)] = path
heapq.heappush(visit_queue, (len(path), k[0], obj, path))
def _pop_visit(visit_queue):
_, _, obj, path = heapq.heappop(visit_queue)
return obj, path
def _do_visit((visit_queue, shortest_paths), other_shortest_paths, traverse, order, other_order):
obj, path = _pop_visit(visit_queue)
new_path = path + [obj]
if id(obj) in other_shortest_paths:
return order(new_path + other_order(other_shortest_paths[id(obj)]))
del obj
for r in (r for r in traverse(new_path[-1]) if
r is not new_path and (id(r) not in shortest_paths)):
_schedule_visit((visit_queue, shortest_paths), r, new_path)
_schedule_visit(FROM_SRC, src, [])
_schedule_visit(FROM_TGT, tgt, [])
i = 0
REFERRERS_OVER_REFERENTS_COST_RATIO = 5 # technically, this changes linearly with object count
while scheduled_visits_from_src and scheduled_visits_from_tgt:
i += 1
forward = lambda ls: ls
backward = lambda ls: list(reversed(ls))
rv = _do_visit(FROM_SRC, shortest_paths_from_tgt, gc.get_referents, forward, backward)
if rv is not None:
return rv
# get_referrers is much slower than get_referents, so only use
# it every so often. why use it at all? in large object
# graphs, you don't want to traverse every reachable object
# just to discover that the target is unreachable. walking
# backwards from the target is a faster way to know that the
# target is unreachable.
if i % REFERRERS_OVER_REFERENTS_COST_RATIO == 0:
rv = _do_visit(FROM_TGT, shortest_paths_from_src, gc.get_referrers, backward, backward)
if rv is not None:
return rv
raise NoPathFoundError