shortestpath.py

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))

shortestpath2.py

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