pythonbreadth-first-search

Reduce memory use for Breadth-First Search

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

The expected output:

[[1, 2, 4, 6], [1, 3, 5, 6], [1, 3, 2, 4, 6], [1, 3, 5, 4, 6]]
Solution

  • You could use set(), tuple() and generators:

    from collections import deque

def BFS(adj, n):
    all_paths = set()
    for v in adj[1]:
        queue = deque()
        queue.append((1, v, [(1, v)]))

        while queue:
            w, x, path = queue.pop()
            if x == n:
                all_paths.add(tuple([1] + [p[1] for p in path]))
                continue

            if x in adj:
                for y in adj[x]:
                    if y != w:
                        queue.appendleft((x, y, path + [(x, y)]))

    return (tuple(path) for path in all_paths)


print(list(BFS({1: [2, 3], 2: [4], 3: [2, 5], 4: [6], 5: [4, 6]}, 6)))

    Output:

    [(1, 3, 2, 4, 6), (1, 3, 5, 4, 6), (1, 2, 4, 6), (1, 3, 5, 6)]