import sqlite3
import collections
import itertools
def bidirectional_BFS(connection, source, target):
"""
Returns all the shortest paths between 'source' and 'target'.
"""
source_queue = collections.deque((source,))
target_queue = collections.deque((target,))
source_visited = {source: 0} # Maps a node to it's distance from the source
target_visited = {target: 0} # Maps a node to it's distance from the target
# Keeps track all the ways to get to a given node
source_parent = collections.defaultdict(set)
target_parent = collections.defaultdict(set)
source_parent[source].add(None)
target_parent[target].add(None)
found_path = False
source_deapth = 0
target_deapth = 0
# The set of all intersections between the two searches
intersections = set()
while source_queue and target_queue:
if found_path and (source_visited[source_queue[0]] > source_deapth and target_visited[target_queue[0]] > target_deapth):
# We are done. All nodes at the current deapth has been explored
intersections = filter_intersections(source_visited, target_visited, intersections)
return construct_path(source_parent, target_parent, source, target, intersections)
if found_path and source_visited[source_queue[0]] > source_deapth:
# Found a path but the BFS from the target still has more nodes to explore
target_added, t_deapth = BFS_target(target_queue, target_visited, target_parent, connection)
intersections |= target_added & source_visited.keys()
elif found_path and target_visited[target_queue[0]] > target_deapth:
# Found a path but the BFS from the source still has more nodes to explore
source_added, s_deapth = BFS_source(source_queue, source_visited, source_parent, connection)
intersections |= source_added & target_visited.keys()
else:
source_added, s_deapth = BFS_source(source_queue, source_visited, source_parent, connection)
target_added, t_deapth = BFS_target(target_queue, target_visited, target_parent, connection)
intersections |= source_added & target_visited.keys()
intersections |= target_added & source_visited.keys()
if not found_path and intersections:
# We found a path so we look the search deapth to the current deapth
found_path = True
source_deapth = s_deapth
target_deapth = t_deapth
if found_path:
return construct_path(source_parent, target_parent, source, target, intersections)
else:
return None
def filter_intersections(source_visited, target_visited, intersections):
"""
Returns only the intersections where the combined distance from source
to the intersection and from target to the intersect are the smallest
"""
filterd = set()
shortest = float('inf')
for intersection in intersections:
if source_visited[intersection] + target_visited[intersection] < shortest:
shortest = source_visited[intersection] + target_visited[intersection]
filterd = {intersection}
elif source_visited[intersection] + target_visited[intersection] == shortest:
filterd.add(intersection)
return filterd
def construct_path(source_parent, target_parent, source, target, intersections):
"""
Constructs all paths and returns a list of list where each list is one path
"""
paths = set()
for intersection in intersections:
from_source_to_inter = construct_path_from_to(source_parent, source, intersection)
from_inter_to_target = construct_path_from_to(target_parent, target, intersection, reverse=True)
for path in itertools.product(from_source_to_inter, from_inter_to_target):
paths.add(tuple(path[0] + path[1][1:]))
return paths
def construct_path_from_to(source_parent, target, start, reverse=False):
"""
Constructs all paths between start and target recursivly. If reverse is true
then all the paths are reversed.
"""
if start == target:
return [[target]]
paths = []
for parent in source_parent[start]:
for path in construct_path_from_to(source_parent, target, parent, reverse):
if reverse:
path.insert(0, start)
else:
path.append(start)
paths.append(path)
return paths
def BFS_source(queue, visited, parent, connection):
"""
Runs one iteration of the BFS from source to the target and then returns
the edges explored during the iteration and the current deapth of the search
"""
current = queue.popleft()
added = set()
for (neighbor,) in connection.execute('SELECT edge_target FROM edges WHERE edge_from= ?;', (current,)):
if neighbor not in visited:
parent[neighbor].add(current)
visited[neighbor] = visited[current] + 1
queue.append(neighbor)
added.add(neighbor)
elif visited[current] + 1 == visited[neighbor]:
parent[neighbor].add(current)
return added, visited[current]
def BFS_target(queue, visited, parent, connection):
"""
Runs one iteration of the BFS from target to source and then returns
the edges explored during the iteration and the current deapth of the search
"""
current = queue.popleft()
added = set()
for (neighbor,) in connection.execute('SELECT edge_from FROM edges WHERE edge_target = ?;', (current,)):
if neighbornotneighbor not in visited:
parent[neighbor].add(current)
visited[neighbor] = visited[current] + 1
queue.append(neighbor)
added.add(neighbor)
elif visited[current] + 1 == visited[neighbor]:
parent[neighbor].add(current)
return added, visited[current]
