CODEWITHSUNDEEP
pythongraphbreadth-first-search
Craig
Craig

Reputation: 1985

Python BFS with collections

I came across a BFS code which involves collections and deques but I could not understand it much. I hope some of the pythonistas here can help a n00b out.

from collections import deque

def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])

Questions:

1) The |= operator seems to be related to bitwise operations - I have no idea how it relates to a BFS, any hints?

2) popleft() should return only one value from what I understand, so how is it returning parent and n here?

3) Is new the series of nodes visited? If I want the nodes, do I just keep appending them to a list?

Thanks in advance.

Craig

Upvotes: 0

Views: 1666

Answers (3)

phihag
phihag

Reputation: 287885

1)

x |= y sets x to the boolean OR of x and y. set overrides the operator to mean the set union. Basically, it's a fancy way of writing enqueued.update(new).

2)

The first element of queue is always a 2-tuple.

tpl = (a,b)
x,y = tpl

is a fancy way of writing

tpl = (a,b)
assert len(tpl) == 2
x = tpl[0]
y = tpl[0]

3)

new is just a temporary variable for - well - the new(unvisited) nodes. enqueued contains the result.

Upvotes: 0

Thomas Wouters
Thomas Wouters

Reputation: 133425

Just to answer your last question: the piece of code you have there is a generator, which means it yields nodes as it traverses the graph breadth-first. It doesn't do any actual searching, it just traverses the node for you. The way you use this piece of code is by iterating over the result, which will give you all nodes in turn (in breadth-first order):

for parent_node, node in bfs(my_graph):
    if node == needle:
        break

Or if you want, for example, a list of all nodes that match a particular condition:

nodes = [ node for parent_node, node in bfs(my_graph) if condition(node) ]

Upvotes: 1

pillmuncher
pillmuncher

Reputation: 10162

  1. a |= b for sets is the same as a = a.union(b).

  2. popleft() does indeed return only one element, which happens to be a 2-tuple, and therefore can be unpacked into two values.

  3. new is the set of not yet visited nodes.

Upvotes: 2

Related Questions