Tushar Jain - 1 year ago 103
Python Question

# How to avoid maximum recursion depth in python with generators?

I'm finding the shortest path using BFS, I get this

`RecursionError: maximum recursion depth exceeded in comparison`
very quickly, any suggestion on how to avoid it using generators ? Or making it iterative is the only good option?

Code below:

``````def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))

def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None
``````

Usage example:

``````graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}

shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']
``````

Try this. It includes a visited set. I also modified the variable name 'next' to 'node' as it is a built in function

``````def bfs_paths(graph, start, goal):
visited = set()
queue = [(start, [start])]
while queue:
vertex, path = queue.pop(0)
for node in graph[vertex]:
if node in visited:
continue
elif node == goal:
yield path + [node]
else:
queue.append((node, path + [node]))

def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download