Skip to content

Instantly share code, notes, and snippets.

@pythonicrubyist
Created July 1, 2019 20:17
Show Gist options
  • Save pythonicrubyist/f3f51119e51ea58298fbaad91ebbe925 to your computer and use it in GitHub Desktop.
Save pythonicrubyist/f3f51119e51ea58298fbaad91ebbe925 to your computer and use it in GitHub Desktop.
data = [('SFO', 'HKO'), ('YYZ', 'SFO'), ('YUL', 'YYZ'), ('HKO', 'ORD')]
# extract nodes
nodes = list(set([val for s in data for val in s]))
# build a graph
graph = {}
for n in nodes:
graph[n] = []
paths = [path for path in data if n in path]
connections = list(set([val for s in paths for val in s]))
connections.remove(n)
graph[n] = connections
# function to be called recursively to find a path from a point to another.
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
new_path = find_path(graph, node, end, path)
if new_path: return new_path
return None
all_paths = []
for n in nodes:
path = find_path(graph=graph, start='SFO', end=n)
all_paths.append(path)
print(all_paths)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment