18

The -depth primary to find causes it to perform a depth-first search.

However, the default sequence is not a breadth-first search.

The default sequence could be informally described as a "depth-first traversal that handles nodes when they are first encountered rather than doing so during backtracking."

I have an actual need for breadth first search. How can I make find behave in this way?


For illustration, with the following setup:

$ mkdir -p alpha/{bravo,charlie,delta}
$ touch alpha/charlie/{alpha,beta,gamma,phi}

find has the following default behavior:

$ find alpha
alpha
alpha/charlie
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma
alpha/delta
alpha/bravo

and with -depth, it performs as follows:

$ find alpha -depth
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma
alpha/charlie
alpha/delta
alpha/bravo
alpha

However, what I want is the following (fictitious) option:

$ find alpha -bfs
alpha
alpha/charlie
alpha/delta
alpha/bravo
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma

In other words I need find to process/report on all files/dirs at a given depth before proceeding further.

How can I do this?

  • Not with find (at least, not with only find). Do you want only to list the files, or do you want to use other primaries? – Gilles 'SO- stop being evil' Apr 29 '16 at 0:41
  • @Gilles, actually I realized that -bfs wouldn't be quite what I need...I have a simple script that generates an index to a large GitLab project, suitable for inclusion in the GitLab Wiki. It makes the headers hierarchically based on directory names. It works great, except that in the example file structure above it would put delta under the charlie subheader, instead of under the parent alpha header. – Wildcard Apr 29 '16 at 0:47
  • Another odd thing is that my find output is sorted alphabetically. No idea why.... – Wildcard Apr 29 '16 at 0:47
  • Still, I think -bfs could come in handy, even if it doesn't perfectly fit this use case. – Wildcard Apr 29 '16 at 0:48
  • 2
    I implemented such a tool: bfs. It's not 100% feature-compatible with GNU find yet, but it's getting there. – Tavian Barnes Aug 12 '16 at 22:44
6

You can do it with just shell wildcards. Build up a pattern with progressively more directory levels.

pattern='*'
set -- $pattern
while [ $# -ne 1 ] || [ "$1" != "$pattern" ]; do
  for file; do
    …
  done
  pattern="$pattern/*"
  set -- $pattern
done

This misses dot files. Use FIGNORE='.?(.)' in ksh, shopt -s dotglob in bash, or setopt glob_dots in zsh to include them.

Caveats:

  • This will blow up memory if there are a lot of files.
  • This traverses symbolic links to directories recursively.

If you want to choose the order or directories and non-directories, and performance isn't critical, you can make two passes and test [ -d "$file" ] on each pass.

| improve this answer | |
  • @Wildcard Yes, I did. – Gilles 'SO- stop being evil' Apr 29 '16 at 1:04
  • 1
    Nice! One more almost trivial caveat: It will fail to process a file that is the lone file in a directory if the file is literally named *. :) – Wildcard Apr 29 '16 at 1:07
  • @Wildcard Oh, yes, I forgot to mention that. Use bash or zsh with nullglob and use (($#)) as the loop condition to avoid this edge case. – Gilles 'SO- stop being evil' Apr 29 '16 at 1:09
5

# cat ./bfind

#!/bin/bash
i=0
while results=$(find "$@" -mindepth $i -maxdepth $i) && [[ -n $results ]]; do
  echo "$results"
  ((i++))
done

This works by increasing the depth of find and repeating, I think it may repeat results, but could be filtered easily

| improve this answer | |
  • Sorry I did not know about the formatting mechanism. Anyway, actually it does not repeat I think because it cuts off anything less than mindepth – user239175 Jul 5 '17 at 5:18
3

You can pipe your find into a sort that sorts primarily by the number of / characters in the pathname. For example,

find alpha |
awk '{n=gsub("/","/",$0);printf "%04d/%s\n",n,$0}' |
sort -t/ |
sed 's|[^/]*/||'

This uses awk to prefix the pathname with the number of slashes, and sed to remove this prefix at the end.

Actually, as you probably want the contents of directory alpha/charlie+ to be listed after alpha/charlie, you need to say sort -t/ -k1,1 -k2,2 -k3,3 -k4,4 upto the desired depth.

| improve this answer | |
0

Another answer not based on 'find' but on bash - use the "length of parent directory" first, then sort by alpha.

The answer doesn't quite match as your results have "charlie, bravo, delta" but I wondered if it should be "bravo, charlie, delta" in alpha order.

paths_breadth_first() {
  while IFS= read -r line; do
    dirn=${line%/*}         ## dirname(line)
    echo ${#dirn},$line     ## len(dirn),line
  done | sort -n | cut -d ',' -f 2-
}

That produces

  $ cat /tmp/yy | paths_breadth_first 
  alpha
  alpha/bravo
  alpha/charlie
  alpha/delta
  alpha/charlie/alpha
  alpha/charlie/beta
  alpha/charlie/gamma
  alpha/charlie/phi
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.