Python Forum
A generic breadth first traversal function
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
A generic breadth first traversal function
#1
The function breadth_first() defined below generates the nodes of a directed graph in breadth first order. Repeated nodes are ignored: only the first occurrence is generated.

from collections import deque
from itertools import chain
from more_itertools import unique_everseen

__version__ = '2019.07.07.1'

def consume(d, start, neighbors):
    yield (start,)
    while d:
        yield neighbors(d.popleft())


def breadth_first(start, neighbors):
    """Generates nodes of a directed graph in level order.
     
    Arguments:
        * start     : an arbitrary initial element (any hashable object)
        * neighbors : a function such that neighbors(item) is a sequence
                    of the item's neighbors in the graph.
                    
    Returns:
        A sequence of nodes in level order. Duplicate nodes are ignored:
        only the first occurrence is generated.
    """
    d = deque()
    for item in unique_everseen(
            chain.from_iterable(consume(d, start, neighbors))):
        yield item
        d.append(item)

if __name__ == '__main__':
    D = {
        1: [2, 3, 4],
        2: [5, 6],
        4: [7, 8],
        5: [9, 10, 4],
        7: [11, 12],
    }
    for x in breadth_first(1, lambda n: D.get(n, ())):
        print(x, end=' ')
    print()
Output:
1 2 3 4 5 6 7 8 9 10 11 12
Edit: A small improvement of version 2019.07.07 is to postpone the call to neighbors() as much as possible.
Reply
#2
Just for historical reference I add link to Guido van Rossum essay Python Patterns—Implementing Graphs
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#3
ah more_itertools is pretty neat
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  general tree traversal cwilson1 2 4,979 Jun-19-2018, 03:46 PM
Last Post: cwilson1

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020