walking a graph: BFS - DFS

Licence CC BY-NC-ND, Thierry Parmentelat

depth-first or breadth-first¶

given a non-valued directed graph G, and a start vertex V, there are 2 famous algorithms to walk the graph from V

depth-first (DF) browsing, and
breadth-first (BF) browsing

intuitively, considering for example from the following tree

import graphviz

tree = graphviz.Digraph(engine='dot')
tree.edge('v', 'v1')
tree.edge('v1', 'v11')
tree.edge('v1', 'v12')
tree.edge('v11', 'v111')
tree.edge('v11', 'v112')
tree.edge('v12', 'v121')
tree.edge('v12', 'v122')
tree.edge('v', 'v2')
tree.edge('v2', 'v21')
tree.edge('v2', 'v22')
tree.edge('v21', 'v211')
tree.edge('v21', 'v212')
tree.edge('v22', 'v221')
tree.edge('v22', 'v222')

tree

these 2 algorithms would yield the nodes in the following orders

DF browsing from v would scan (the newlines are only cosmetic)

v v1 v11 v111 v112
v12 v121 v122
v2 v21 v211 v212
v22 v221 v222

BF browsing from v would scan (ditto)

v
v1 v2
v11 v12 v21 v22
v111 v112 v121 v122 v211 v212 v221 v222

objectives¶

we want to write a generator that implements these 2 browsing policies from a graph and vertex.
of course, only the nodes reachable from the entry vertex will be browsed by this method

algorithms¶

the 2 algorithms used to perform these scans are, interestingly, very close to one another
in both cases we need a STORAGE object, where we can store() things and retrieve() them later on

FIFO / FILO¶

Let us consider the following 2 storage implementations:

Fifo implements a first-in-first-out policy
Filo does the exact opposite and has a first-in-last-out policy

Exercise: you may wish to factorize both into a single class...

But let’s get to it:

from collections import deque

class Fifo:
    def __init__(self):
        self.line = deque()
    def store(self, item):
        self.line.append(item)
    def retrieve(self):
        if self.line:
            return self.line.popleft()
    def __len__(self):
        return len(self.line)

from collections import deque

class Filo:
    def __init__(self):
        self.line = deque()
    def store(self, item):
        self.line.append(item)
    def retrieve(self):
        if self.line:
            return self.line.pop()
    def __len__(self):
        return len(self.line)

# let's check it does what we want

fifo = Fifo()
for i in range(1, 4):
    fifo.store(i)
while fifo:
    print(f"retrieve → {fifo.retrieve()}")

retrieve → 1
retrieve → 2
retrieve → 3

# same here

filo = Filo()
for i in range(1, 4):
    filo.store(i)
while filo:
    print(f"retrieve → {filo.retrieve()}")

retrieve → 3
retrieve → 2
retrieve → 1

def scan(start, storage):
    """
    performs a scan of all the vertices reachable from start vertex

    in an order that is DF or BF, depending on the
    storage policy (fifo or filo)

    assumptions:

    * vertices reachable from a vertex are
      stored in a 'neighbours' attribute

    * storage should have store() and retrieve() methods
      and be testable for emptiness (if storage: ...)
    * also it should be empty when entering the scan
    """

    storage.store(start)
    # keep track of what we've seen
    scanned = set()

    while storage:
        current = storage.retrieve()
        # skip vertices already seen
        if current in scanned:
            continue
        yield current
        scanned.add(current)
        for neighbour in current.neighbours:
            storage.store(neighbour)

class Vertex:
    def __init__(self, name):
        self.name = name
        self.neighbours = set()

    def __repr__(self):
        return self.name

    def add_neighbour(self, other):
        self.neighbours.add(other)

# rebuild sample graph
def tree_vertex(name, depth):
    if depth == 0:
        return Vertex(name)
    elif depth > 0:
        result = Vertex(name)
        result.add_neighbour(tree_vertex(name+'1', depth-1))
        result.add_neighbour(tree_vertex(name+'2', depth-1))
        return result

g = tree_vertex('v', 3)
g

v

FILO = DF - depth first¶

FIFO = BF - breadth first¶

for vertex in scan(g, Filo()):
    print(vertex)

v
v1
v12
v122
v121
v11
v112
v111
v2
v22
v221
v222
v21
v211
v212

for vertex in scan(g, Fifo()):
    print(vertex)

v
v2
v1
v21
v22
v11
v12
v212
v211
v222
v221
v111
v112
v121
v122

applications¶

being a generator, we can combine it with all the itertools and the like

import itertools

for example, if we need to print every other vertex in a DF scan

df_scan = scan(g, Filo())

for v in itertools.islice(df_scan, 0, None, 2):
    print(v)

v
v12
v121
v112
v2
v221
v21
v212

# notice that df_scan is now exhausted !

for v in itertools.islice(df_scan, 0, None, 2):
    print(v)

or skip the first 3..

# but we can easily create a new one !
df_scan = scan(g, Filo())

for v in itertools.islice(df_scan, 3, None):
    print(v)

v122
v121
v11
v112
v111
v2
v22
v221
v222
v21
v211
v212

howtos

visu: DNA Walking

howtos

gestion de sous-processus