Skip to content

Instantly share code, notes, and snippets.

@BinRoot
Created January 27, 2013 21:21
Show Gist options
  • Save BinRoot/4650588 to your computer and use it in GitHub Desktop.
Save BinRoot/4650588 to your computer and use it in GitHub Desktop.
class IntersectionFound(Exception):
def __init__(self, user_id):
self.user_id = user_id
def get_friends(user_id):
"""Returns a set of ids representing the friends of the given user."""
def update_shortest_path(shortest_paths, user_id, to_user_id, via_user_id, distance):
"""Update the shortest path for one user."""
if shortest_paths.has_key(user_id):
shortest_path = shortest_paths[user_id]
else:
shortest_path = shortest_paths[user_id] = {}
if not shortest_path.has_key(to_user_id):
shortest_path[to_user_id] = via_user_id
return shortest_path
def process_user(shortest_paths, user_id, to_user_id, distance):
friend_ids = get_friends(user_id)
for friend_id in list(friend_ids):
if shortest_paths.has_key(friend_id):
friend_ids.remove(friend_id)
else:
shortest_path = update_shortest_path(shortest_paths, friend_id, to_user_id, user_id, distance)
if len(shortest_path) > 1:
raise IntersectionFound(friend_id)
return friend_ids
def process_users(shortest_paths, user_ids, to_user_id, distance):
next_user_ids = set()
for user_id in user_ids:
next_user_ids.update(process_user)
return next_user_ids
def get_shortest_path(user_id_a, user_id_b):
"""Return a list describing the shortest path between two users in the friendship graph."""
shortest_paths = {}
to_process_a = set((user_id_a))
to_process_b = set((user_id_b))
from itertools import chain
from collections import defaultdict
# since the python stdlib doesn't provide linked lists (that I recall), but
# we want them for O(1) prepend
class LinkedList(object):
def __init__(value, next_cell):
self.value = value
self.next_cell = next_cell
def __iter__(self):
return LinkedListIterator(self)
class LinkedListIterator(object):
def __iter__(self, current_cell):
self.current_cell = current_cell
def __iter__(self):
return self
def next(self):
if self.current_cell:
value = self.current_cell.value
self.current_cell = self.current_cell.next_cell
return value
else:
raise StopIteration()
def get_friends(user_id):
"""Returns a set of ids representing the friends of a given user."""
# ...
def process_users(shortest_paths, user_ids, origin_id, path_found):
next_user_ids = set()
for user_id in user_ids:
friend_ids = get_friends(user_id)
for friend_id in friend_ids:
paths_from_friend = shortest_paths[friend_id]
if not paths_from_friend.has_key(origin_id):
next_user_ids.add(friend_id)
path_to_origin = shortest_paths[user_id][origin_id]
paths_from_friend[origin_id] = LinkedList(friend_id,
path_to_origin)
if len(paths_from_friend) > 1:
for other_id in paths_from_friend.iterkeys():
if other_id == origin_id:
continue
path_to_other = shortest_paths[friend_id][other_id]
path = list(chain(reversed(path_to_origin),
path_to_other))
path_found(path)
return next_user_ids
class PathFound(Exception):
def __init__(self, path):
super(PathFound, self).__init__()
self.path = path
def get_shortest_path(user_id_a, user_id_b):
"""Return a list describing the shortest path between two users in the friendship graph."""
if user_id_a == user_id_b:
return [user_id_a]
origin_ids = (user_id_a, user_id_b)
shortest_paths = defaultdict(dict)
current_layers = {}
for origin_id in origin_ids:
shortest_paths[origin_id][origin_id] = LinkedList(origin_id, None)
current_layers[origin_id] = set((origin_id,))
def terminate_with_path(path):
if path[0] == user_id_b:
path = list(reversed(path))
raise PathFound(path)
try:
while len(current_layers) > 0:
next_layers = {}
for origin_id in origin_ids:
next_layer = process_users(shortest_paths,
current_layers[origin_id],
origin_id,
terminate_with_path)
if len(next_layer) > 0:
next_layers[origin_id] = next_layer
current_layers = next_layers
except PathFound, e:
return e.path
else:
return None
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment