Lazy Traversal of Directed Graphs (Python recipe) by Vincent Kraeutler

ActiveState Code (http://code.activestate.com/recipes/498247/)

def graphWalker(node, getChildren, toEvaluate, backPack = None):
    """
    A generator that (lazily, recursively) applies an operation to a directed graph structure.
    
    @param node the graph node where we start
    @param getChildren a callable f such that f(node) returns the child nodes of node
    @param toEvaluate a callable g such that the result rr for a node is rr = g(node, backPack)[0]
    @param backPack a partial result that is carried along and may change as the graph is traversed. 
            g(node, backPack)[1] is passed on to the child nodes.
    @returns an iterator over the results of applying toEvaluate to every node in the tree
    
    @see walkTest() for an example.
    """
    rr = toEvaluate(node, backPack)
    yield rr[0]
    for child in getChildren(node):
        for result in graphWalker(child, getChildren, toEvaluate, rr[1]):
            yield result



"""

SAMPLE (TEST) CODE FOLLOWS:

"""

import os
import stat
       
def walkTest(root = os.getcwd(), recursionLimit = 3):
    """
    A walk that prints all the relative path of all files in a file system rooted 
    at the current directory with respect to that directory. Goes no deeper than
    recursionLimit.
    """
    
    def te(node, rl):
        root, visitedNodes, name = node[:3]
        if rl < 0: raise StopIteration
        return (
                os.sep.join(visitedNodes + [name])[1:],
                rl - 1
                )
    
    def absPath(node):
        return os.sep.join(
                               [node[0]] + node[1] + [node[2]]
                               )
    
    def isdir(path):
        """
        @param path the absolute (?) path of the file
        """
        return stat.S_ISDIR(os.stat(
                                    path
                                    )[stat.ST_MODE])
        
    def gc(node):
        
        root, visitedNodes, name, depth = node
        
        ab = absPath(node)
        if not isdir(ab): return []
        

        return [
                (
                 root,
                 visitedNodes + [name],
                 cc,
                 depth + 1
                 )
                for cc in
                os.listdir(ab)]

    return graphWalker((root, [], "", 0), gc, te, recursionLimit)

if __name__ == "__main__":
    for rr in walkTest():
        print rr