Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
39 lines (31 sloc) 1.14 KB
## Social Networks
GRAPH = {}
def make_link(Graph, node1, node2):
if node1 not in Graph:
Graph[node1] = {}
(Graph[node1])[node2] = 1
if node2 not in Graph:
Graph[node2] = {}
(Graph[node2])[node1] = 1
return Graph
social = [('Jill','New York'),('Jill','Toronto'), \
('Jill','London'),('Jack','France'), \
('Jack','New York'), ('John','Berlin'), \
('John','London'),('Jacob','New York'), \
('Joan','Toronto'),]
for (x,y) in social: make_link(GRAPH, x, y)
def short_path(G, node1, node2):
""" Return the shortest path from node1 to node2"""
dist_from_start = {}
stackoverflow = [node1]
dist_from_start[node1] = [node1]
while len(stackoverflow) > 0:
current = stackoverflow[0]
del stackoverflow[0]
for neighbor in G[current].keys():
if neighbor not in dist_from_start:
dist_from_start[neighbor] = dist_from_start[current] + [neighbor]
if neighbor == node2: return dist_from_start[node2]
stackoverflow.append(neighbor)
return False
print short_path(GRAPH, 'Joan', 'John')