# Implement a graph in Python

Question : Build a graph in python, given its edge representation.

from collections import defaultdict

graph = { '1' : ['2' ,'4','5'],
'2' : ['3'] ,
'3' : ['5'] ,
'4' : ['2']
}

def generate_edges(graph):
edges = []

for node in graph:
for next_node in graph[node]:
#if edge exist than append
edges.append((node,next_node))
return edges

def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path

for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath:
return newpath
return None

print generate_edges(graph)

print find_path(graph, '1','5')


How can i improve this code?

find_path is very inefficient. Consider the following example, where we try to find a short path (just one edge) in a graph with just eleven nodes:

>>> G = {i: list(range(10)) for i in range(10)}
>>> G[0].append(10)
>>> find_path(G, 0, 10)
[0, 10]


How long does this take?

>>> from timeit import timeit
>>> timeit(lambda:find_path(G, 0, 10), number=1)
1.3475657280068845


It really shouldn't take more than a second to find a path with a single edge in such a small graph. So why does it take so long?

The way that find_path works is that it generates all simple paths (paths with no repeated nodes) in depth-first order. However, in general there can be exponentially many simple paths in a graph. I constructed the graph G so that it looks like this:

The depth-first search starts by finding the path 0–1–2–3–4–5–6–7–8–9 but then it reaches a dead end:

So the search backtracks a couple of steps and then finds the path 0–1–2–3–4–5–6–7–9–8, but again it reaches a dead end:

You can see that the search will have to visit every path starting with 0 and visiting all of 1 to 9, before it will consider the path 0–10. But there are $9! = 362,880$ such paths.

To avoid this exponential runtime, you'll have to use a different approach, for example Dijkstra's algorithm.