Chapter 6, Breath-first search (From Grokking Algorithm)

seller.py

from collections import deque


def is_person_seller(person):
    return True if person.endswith('m') else False


def search(graph, start_point, search_function):
    search_queue = deque()
    search_queue.extend(graph[start_point])
    
    visited = []
    while search_queue:
        person = search_queue.popleft()
        if person in visited:
            continue
        else:
            visited.append(person)
        if search_function(person):
            return person
        else:
            search_queue += graph[person]
    return None


test_graph = {
    'me': ['you'],
    'you': [],
    'she': ['him'],
    'him': []
}
assert search(test_graph, 'me', is_person_seller) == None
assert search(test_graph, 'you', is_person_seller) == None
assert search(test_graph, 'she', is_person_seller) == 'him'
assert search(test_graph, 'him', is_person_seller) == None


graph = {}
graph['bob'] = ['anuj', 'peggy']
graph['you'] = ['alice', 'bob', 'claire']
graph['alice'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []


seller = search(graph, 'you', is_person_seller)
print("Seller is {}".format(seller if seller else "nobody"))
#Seller is thom

https://docs.python.org/2/library/collections.html#collections.deque

• Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.
• Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.
• Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.

Need to do more:

• Print shortest path. For example, in this case, You -> Claire -> Thom should be the answer.