Tushar Jain Tushar Jain - 7 days ago 6
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']

Answer

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)
        visited.add(vertex)
        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