Abstracting algorithms (graph depth first search)

[Scott David Daniels]

Paul Moore wrote:

> ...I've been trying to work out a good way of encapsulating the
> standard depth first search algorithm in a library module ...
> However, this function *only* prints the vertices in preorder. To
> print in postorder, ... To put the results in a list, you need to
> pass the list as a parameter and change the print to append. To
> return the results as an iterator, you need to add "yield" ...
> And many graph algorithms make even more subtle changes to the basic
> DFS algorithm....
I'd say that preorder and postorder are distinct, and provide both
as iterators, leaving the user to figure out what to do per element.
Certainly your list operation becomes simple:

     from dfs import preorder, postorder

     somelist = list(preorder(graph, startnode))

     for node in postorder(graph, startnode):
         print node

The iterator encapsulates exactly the full tree walk; I'd count
preorder and postorder as slightly different algorithms, which
share code structure (we duplicate less than a dozen lines).

# $Id: dfs.py $

def preorder(graph, startnode):
     seen = {}
     def visit(node):
         yield node
         seen[node] = True
         for child in graph[node]:
             if child not in seen:
                 for result in visit(child):
                     yield result
     return visit(startnode)

def postorder(graph, startnode):
     seen = {}
     def visit(node):
         seen[node] = True
         for child in graph[node]:
             if child not in seen:
                 for result in visit(child):
                     yield result
         yield node
     return visit(startnode)


-Scott David Daniels
Scott.Daniels at Acm.Org