Odtnhj

Example directory tree:

 root
 /|
 / | 
 / | 
 A B C
 / 
 / 
 D E
 
 
 F
 
 
 G

os.walk() will traverse this directory tree using the depth-first search algorithm. For example, os.walk() will process this tree in this order: root, A, B, D, C, E, F, G. os.walk() doesn't seem to provide an option for a breadth-first search. If this option were available, it would process this tree in this order instead: root, A, B, C, D, E, F, G. In my application, I need to do the reverse search. However, os.walk(tree, topdown = False) yields: A, D, B, G, F, E, C, root. On the contrary, the breadth-first search in reverse would yield: G, F, E, D, C, B, A, root.

I've had to create my own solution which is below:

def reversewalk(path):
 dirlist = 
 for dirName, subdirList, fileList in os.walk(path, topdown=False):
 depth = dirName.count(os.path.sep)
 dirlist[os.path.abspath(dirName)] = (depth, dirName, subdirList, fileList)
 return sorted(dirlist.items(), key = lambda x : x[1], reverse = True)

My question is: Is there a "breadth-first" search option available in os.walk() or equivalent Python function? Follow up question is: If not, is there a better solution than the one I've presented?

The following code is from an ActiveState article I read:

#!/usr/bin/env python
import os

# -------------------------------------------
def breadthFirstFileScan( root ) :
 dirs = [root]
 # while we has dirs to scan
 while len(dirs) :
 nextDirs = 
 for parent in dirs :
 # scan each dir
 for f in os.listdir( parent ) :
 # if there is a dir, then save for next ittr
 # if it is a file then yield it (we'll return later)
 ff = os.path.join( parent, f )
 if os.path.isdir( ff ) :
 nextDirs.append( ff )
 else :
 yield ff
 # once we've done all the current dirs then
 # we set up the next itter as the child dirs 
 # from the current itter.
 dirs = nextDirs

# -------------------------------------------
# an example func that just outputs the files.
def walkbf( path ) :
 for f in breadthFirstFileScan( path ) :
 print f

# ============================================
# as a demo we'll just start from where we 
# were called from.
walkbf( os.getcwd() )

The following is just a bit more terse and more closely mimics os.walk()'s functionality. (It's interesting this works because of Python's implicit handling of lexicographic sorting of tuples.)

def rbf_walk(path):
 dirlist = ((dirpath.count(os.path.sep), dirpath, dirnames, filenames) for
 dirpath, dirnames, filenames in os.walk(path, topdown = False))
 for entry in sorted(dirlist, reverse = True):
 yield entry[1:]