Modifying list while iterating during Breadth-first search

Question

I am writing a function for implementing breadth-first search over a no. of nodes in a directed graph. The nodes are all numbers from 1-100. This is my implementation:

def BFS(start= 1, adj_dict= None):
    level= {}
    current= [start]
    visible= []
    lno= 0
    step= 0
    for ele in current:
        if ele not in level:
            level[ele]= lno 
            visible.extend(adj_dict[ele])
        current.remove(ele)
        if current==[]:
            current= visible[:]
            visible= []
            lno+=1
    return level

This did not work correctly and stored only the start key in adj_dict. I ran the debugger and saw that the code exited for loop after first iteration.

Upon searching a little about the cause of this, I found this question- https://stackoverflow.com/questions/1207406/remove-items-from-a-list-while-iterating on SO. This was the cause of error. The answers to that question suggest that I create a new list somehow, either using list comprehension or using slicing but none of them will help in my case.

So, I thought of nesting the for loop inside a while loop to achieve the desired result. This is how it looks now:

while current:
    for ele in current:
        if ele not in level:
            level[ele]= lno 
            visible.extend(adj_dict[ele])
        current.remove(ele)
        if current==[]:
            current= visible[:]
            visible= []
            lno+=1

This works now. What I want to ask is this a correct way to achieve the effect or am I just getting lucky and the code can break easily? Also is this the pythonic way?

Answer 1

I do not know what is considered pythonic, but when doing a BFS, it is preferable to use a while loop. Also, you can use the queue (or Queue in Python 2.7) module for more intuitive operations:

from queue import Queue

def BFS(start=1, adj_dict=None):
    queue = Queue()
    already_seen = set()
    level = {}

    # this is our "seed" at starting level = 0
    queue.put_nowait((start, 0))

    while not queue.empty():
        # get the topmost element of the queue 
        curr_node, curr_level = queue.get_nowait()

        # make sure not to process element more than once
        if curr_node not in already_seen:
            already_seen.add(curr_node)
            level[curr_node] = curr_level

            # add all of the current node's neighbors to the queue
            for neighbor_node in adj_dict[curr_node]:
                queue.put_nowait((neighbor_node, curr_level + 1))
    return level

Answer 2

You should not change a structure you are iterating over (for ...). The (hidden) controls of iterating can't efficiently take account of any possible modification you do. That should be true for almost any language.

BTW: IF you need some kind of recursion (-> DFS): it is not that bad in python related to timing but has its limitation by the recusion limit. Using queues you can possibly resolve this. Here 'collections.deque' is preferable over 'queue.Queue' for this kind of task cause of their timings. The latter one is ment for inter thread communication, so there is some overhead in it.

def BFS(start, graph, level=0):
    """ do a BFS returning list of (node, level) sorted by levels

        :start:    starting node
        :graph:    dict  node: neighbors
        :level:    level to start at: (0 | 1)
    """
    seen, done = set(start), [(start, level)]
    nextnodes = graph[start]   # neighbours seen by next step

    while nextnodes:
        nodes, nextnodes, level = nextnodes, [], level + 1
        for n in nodes:
            if n not in seen:
                done.append((n, level))
                nextnodes.extend(graph[n])
                seen.add(n)
    return done

May be you can gain some speed by using higher leveled python functionalities instead of stepping thru node by node, like:

lookat = set(nodes) - seen
nextnodes = sum((graph[n] for n in lookat), [])
seen = seen.union(lookat)