Implement a graph in Python

Question

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?

Answer 1

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.