How do I recursively list all directories at a location, breadth-first?

Question

Breadth-first list is important, here. Also, limiting the depth searched would be nice.

$ find . -type d
/foo
/foo/subfoo
/foo/subfoo/subsub
/foo/subfoo/subsub/subsubsub
/bar
/bar/subbar

$ find . -type d -depth
/foo/subfoo/subsub/subsubsub
/foo/subfoo/subsub
/foo/subfoo
/foo
/bar/subbar
/bar

$ < what goes here? >
/foo
/bar
/foo/subfoo
/bar/subbar
/foo/subfoo/subsub
/foo/subfoo/subsub/subsubsub

I'd like to do this using a bash one-liner, if possible. If there were a javascript-shell, I'd imagine something like

bash("find . -type d").sort( function (x) x.findall(/\//g).length; )

Answer 1

I don't think I understand the question, but here are some stabs at it:

Does this question help?

Perhaps you are looking for the -depth option:

   -depth Process each directory's contents before the  directory  itself.
          The -delete action also implies -depth.

Or the -d option:

   -d     A synonym for -depth, for compatibility  with  FreeBSD,  NetBSD,
          MacOS X and OpenBSD.

(Both quotes are from the GNU documentation.)

Maybe if you explained a bit more the problem you are trying to solve...

Answer 2

Without the deserved ordering: find -maxdepth -type d

To get the deserved ordering, you have to do the recursion yourself, with this small shellscript:

#!/bin/bash
r () 
{
    let level=$3+1
    if [ $level -gt $4 ]; then return 0; fi
    cd "$1"
    for d in *; do
        if [ -d "$d" ]; then
      echo $2/$d
        fi;
    done
    for d in *; do
        if [ -d "$d" ]; then
            (r "$d" "$2/$d" $level $4)
        fi;
    done
}
r "$1" "$1" 0 "$2"

Then you can call this script with parameters base directory and depth.

Answer 3

I don't think you could do it using built-in utilities, since when traversing a directory hierarchy you almost always want a depth-first search, either top-down or bottom-up. Here's a Python script that will give you a breadth-first search:

import os, sys

rootdir = sys.argv[1]
queue = [rootdir]

while queue:
    file = queue.pop(0)
    print(file)
    if os.path.isdir(file):
        queue.extend(os.path.join(file,x) for x in os.listdir(file))

Edit:

1. Using os.path-module instead of os.stat-function and stat-module.
2. Using list.pop and list.extend instead of del and += operators.

Answer 4

I tried to find a way to do this with find but it doesn't appear to have anything like a -breadth option. Short of writing a patch for it, try the following shell incantation (for bash):

LIST="$(find . -mindepth 1 -maxdepth 1 -type d)";
while test -n "$LIST"; do
    for F in $LIST; do
        echo $F;
        test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)";
    done;
    LIST=$NLIST;
    NLIST="";
done

I sort of stumbled upon this accidentally so I don't know if it works in general (I was testing it only on the specific directory structure you were asking about)

If you want to limit the depth, put a counter variable in the outer loop, like so (I'm also adding comments to this one):

# initialize the list of subdirectories being processed
LIST="$(find . -mindepth 1 -maxdepth 1 -type d)";
# initialize the depth counter to 0
let i=0;
# as long as there are more subdirectories to process and we haven't hit the max depth
while test "$i" -lt 2 -a -n "$LIST"; do
    # increment the depth counter
    let i++;
    # for each subdirectory in the current list
    for F in $LIST; do
        # print it
        echo $F;
        # double-check that it is indeed a directory, and if so
        # append its contents to the list for the next level
        test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)";
    done;
    # set the current list equal to the next level's list
    LIST=$NLIST;
    # clear the next level's list
    NLIST="";
done

(replace the 2 in -lt 2 with the depth)

Basically this implements the standard breadth-first search algorithm using $LIST and $NLIST as a queue of directory names. Here's the latter approach as a one-liner for easy copy-and-paste:

LIST="$(find . -mindepth 1 -maxdepth 1 -type d)"; let i=0; while test "$i" -lt 2 -a -n "$LIST"; do let i++; for F in $LIST; do echo $F; test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)"; done; LIST=$NLIST; NLIST=""; done

Answer 5

If you want to do it using standard tools, the following pipeline should work:

find . -type d | perl -lne 'print tr:/::, " $_"' | sort -n | cut -d' ' -f2

That is,

1. find and print all the directories here in depth first order
2. count the number of slashes in each directory and prepend it to the path
3. sort by depth (i.e., number of slashes)
4. extract just the path.

To limit the depth found, add the -maxdepth argument to the find command.

If you want the directories listed in the same order that find output them, use "sort -n -s" instead of "sort -n"; the "-s" flag stabilizes the sort (i.e., preserves input order among items that compare equally).

Answer 6

Here's a possible way, using find. I've not thoroughly tested it, so user beware...

depth=0
output=$(find . -mindepth $depth -maxdepth $depth -type d | sort); 
until [[ ${#output} -eq 0 ]]; do 
  echo "$output"
  let depth=$depth+1
  output=$(find . -mindepth $depth -maxdepth $depth -type d | sort)
done

Answer 7

Something like this:

find . -type d | 
  perl -lne'push @_, $_;
    print join $/,
      sort { 
        length $a <=> length $b || 
       $a cmp $b 
        } @_ if eof'