I am a novice to Comp Science topics. I have been struggling with reducing the memory use when performing a breadth-first search. For demonstration: Given a Directed Acyclical Graph (DAG) from Cormen et al. Find all unique paths from source (1) to sink (6). vertices: [1, 2, 3, 4, 5, 6] edges: [(1, 2), (1, 3), (2, 4), (3, 2), (3, 5), (4, 6), (5, 4), (5, 6)] Same information as an adjacency map (python dictionary): adj = {1:[2, 3], 2:[4], 3:[2, 5], 4:[6], 5:[4, 6]} In the code below, I save path as a list of edges. There are two things in the queue: the next edge to add to path, and the path so far. As the number of edges become 1800 or so, the memory requirement of this code becomes more than 500 MB. Queue has the largest memory use. Is there a way to do BFS with much lesser memory use? def BFS(adj): all_paths = [] for v in adj[1]: queue = deque() queue.append(((1, v),[])) while queue: (w, x), path = queue.pop() path.append((w, x)) if x not in adj.keys(): continue for y in adj[x]: if y == n: # reached sink # convert list of edges to final - a list of vertices path.append((x, y)) a = path[0][0] final = [a] for e in path: final.append(e[1]) if final not in all_paths: all_paths.append(final) continue elif (x, y) not in path: tmp = [i for i in path] queue.appendleft(((x,y), tmp)) return all_paths Continue reading...
