• %u (29/29) Mar 12 2011 It seems to me that the SpanMode.breadth option when enumerating a
• spir (11/40) Mar 12 2011 You are right about depth / breadth.
• %u (7/7) Mar 12 2011 So apparently, it's incredibly hard (if not impossible) to have a true
• Stewart Gordon (9/15) Mar 18 2011 I agree. Basically:

%u <wfunction hotmail.com> writes:

It seems to me that the SpanMode.breadth option when enumerating a
directory does not actually do breadth-first search, but rather
performs a kind of depth-first "preorder" traversal.

In other words, to me, this is depth-first "postorder" traversal:

\A
\A\1
\A\1\x
\A\1\y
\A\2
\B
\B\1

whereas this is depth-first "preorder" traversal:

\A\1\x
\A\1\y
\A\1
\A\2
\A
\B\1
\B

and whereas **this** is a true breadth-first traversal:

\A
\B
\A\1
\A\2
\B\1
\A\1\x
\A\1\y


Is that correct, and so is "breadth" actually a misnomer? I found it
really confusing that it didn't work level-by-level.

spir <denis.spir gmail.com> writes:

On 03/12/2011 10:22 AM, %u wrote:
 It seems to me that the SpanMode.breadth option when enumerating a
 directory does not actually do breadth-first search, but rather
 performs a kind of depth-first "preorder" traversal.

 In other words, to me, this is depth-first "postorder" traversal:

 \A
 \A\1
 \A\1\x
 \A\1\y
 \A\2
 \B
 \B\1

 whereas this is depth-first "preorder" traversal:

 \A\1\x
 \A\1\y
 \A\1
 \A\2
 \A
 \B\1
 \B

 and whereas **this** is a true breadth-first traversal:

 \A
 \B
 \A\1
 \A\2
 \B\1
 \A\1\x
 \A\1\y


 Is that correct, and so is "breadth" actually a misnomer? I found it
 really confusing that it didn't work level-by-level.

You are right about depth / breadth.

(But I also have always found preorder/postorder misleading, or rather 
inversed. For me, the second one should be called postorder, since it postpones 
app on A after app on A's subnodes. A better, non-misleading, naming may be 
branch-first (case 1 above) vs children-first (case 2).)

Denis
-- 
_________________
vita es estrany
spir.wikidot.com

%u <wfunction hotmail.com> writes:

So apparently, it's incredibly hard (if not impossible) to have a true
breadth-first search that scales up reasonably well to, say, an entire
volume of data:
stackoverflow.com/questions/5281626/breadth-first-directory-traversal-
is-it-possible-with-olog-n-memory

I suggest we rename the option to something else and deprecate the
name?

Stewart Gordon <smjg_1998 yahoo.com> writes:

On 12/03/2011 09:31, spir wrote:
<snip>
 You are right about depth / breadth.

 (But I also have always found preorder/postorder misleading, or rather
inversed. For me,
 the second one should be called postorder, since it postpones app on A after
app on A's
 subnodes.

I agree.  Basically:
- Preorder means the processing of each node on entry to its subtree (before
visiting the 
children)
- Postorder means the processing of each node on exit from its subtree (after
visiting the 
children)

 A better, non-misleading, naming may be branch-first (case 1 above) vs
 children-first (case 2).)

"Branch-first" to me is equally misleading.  How about trunk-first and
leaves-first?

Stewart.