!standard  A.18.10(5/3)                             13-05-09    AC95-00249/00
!class confirmation 13-05-09
!status received no action 13-05-09
!status received 13-04-13
!subject Trees
!summary

!appendix

From: John Barnes
Sent: Saturday, April 13, 2013   5:51 AM

Does anyone have a good definition of depth-order first as used for the tree
containers?

I thought maybe Knuth would describe it but he doesn't seem to.

***************************************************************

From: Tucker Taft
Sent: Saturday, April 13, 2013   6:58 PM

Wikipedia has the following entry on depth-first search:

   http://en.wikipedia.org/wiki/Depth-first_search

Not sure if this is what you are looking for...

***************************************************************

From: Jon S. Squire
Sent: Saturday, April 13, 2013   7:11 PM

It means start from root, follow first branch all the way through nodes to leaf
node, back up one node, follow second branch all the way to leaf node, keep
going on each node until all branches on that node followed, then back up one
node and keep repeating. Done when you get back to root and all root branches
have been followed.

Each node needs an index to next branch, typically initialized to zero. Index is
advanced as each branch from that node is followed. Obviously each node needs a
pointer to its parent, initialized when node is created. Every node can have any
number of branches, zero branches is a leaf node. Equality if index and number
of branches is the test to back up one node, go to parent.

***************************************************************

From: Randy Brukardt
Sent: Saturday, April 13, 2013  10:41 PM

I assume you're looking for a better explanation than the formal one in
A.18.10(5/3)? Is the Wikipedia Tucker pointed out enough?

***************************************************************

From: Robert Dewar
Sent: Sunday, April 14, 2013   3:35 AM

> It means start from root, follow first branch all the way through
> nodes to leaf node, back up one node, follow second branch all the way
> to leaf node, keep going on each node until all branches on that node
> followed, then back up one node and keep repeating.
> Done when you get back to root and all root branches have been
> followed.

I think it is more easily expressed recursively

   Visit: if non-null node then
            for each branch, visit (branch)

that's it, nothing more needs to be said.

> Each node needs an index to next branch, typically initialized to
> zero. Index is advanced as each branch from that node is followed.
> Obviously each node needs a pointer to its parent, initialized when
> node is created. Every node can have any number of branches, zero
> branches is a leaf node.
> Equality if index and number of branches is the test to back up one
> node, go to parent.

This paragraph is over-specific, yes, that's one way of implementing a DFS, but
a more familiar one is to use a recursive approach, which does not require
parent pointers, or a next-branch-index, since this data is implicitly held in
the local data of the recursion.

***************************************************************

From: John Barnes
Sent: Sunday, April 14, 2013   6:20 AM

>I assume you're looking for a better explanation than the formal one in
> A.18.10(5/3)? Is the Wikipedia Tucker pointed out enough?

Yes. Quite enough, thanks. Indeed more than enough.

Mind you I don't trust Wikipedia these days. I had terrible trouble with a student on my numbers course recently. He thought everything on the web was gospel but the wiki entry he found was misleading for the birthday problem.

***************************************************************

From: John Barnes
Sent: Sunday, April 14, 2013   6:12 AM

> It means start from root, follow first branch all the way
> through nodes to leaf node, back up one node,
> follow second branch all the way to leaf node,
> keep going on each node until all branches on that node followed,
> then back up one node and keep repeating.
> Done when you get back to root and all root branches have
> been followed.

Many thanks for that. It confirms what I thought luckily.

***************************************************************

From: Erhard Ploedereder
Sent: Monday, April 15, 2013   2:30 PM

> Does anyone have a good definition of depth-order first as used for
> the tree containers?

Actually, and you can read it up in Aho, Lam, Ullman, Principles of Compiler
Construction, a.k.a. the Dragonbook, there are (at least) three depth-first
orders, while there is only one depth-first traversal (up to order of children)
algorithm.

There is preorder (increment order number prior to visit to children), postorder
(increment after visit), and reverse postorder (decrement after visit). The last
one is important, since it is the topological order of acyclic graphs with all
kinds of nice properties for fast information flow along edges. (If one wants to
be pedantic, then postorder is the one and only, since it goes deep as quickly
as possible.)

So, really, A.18.10 (147/3) et al. are badly specified, even if it is very
plausible that these searches are meant to use the prefix order. (Interestingly,
they talk about "a depth-first order" not "the d-f o.")


***************************************************************

From: Randy Brukardt
Sent: Monday, April 15, 2013   2:42 PM

...
> So, really, A.18.10 (147/3) et al. are badly specified, even if it is
> very plausible that these searches are meant to use the prefix order.
> (Interestingly, they talk about "a depth-first order" not "the d-f
> o.")

Excuse me? A.18.10(5/3) defines what we (the Ada Standard) means by "depth-first
order", and as it doesn't rely on any other documents, that's the meaning in the
Standard. We wordsmithed that definition a lot, and it might not be perfect, but
certainly the places that use the term depend on the definition from the
standard, not what some other book might have defined. Whether we should have
used a different term is a different question, but it isn't particular relevant
as to whether the Standard is "well-specified".

***************************************************************

From: Jon S. Squire
Sent: Monday, April 15, 2013   3:39 PM

My algorithm, in too much detail, simpler if you like to write recursive
functions, only works for acyclic graphs.

***************************************************************

From: Erhard Ploedereder
Sent: Monday, April 15, 2013   4:11 PM

> ...
>> So, really, A.18.10 (147/3) et al. are badly specified, even if it is
>> very plausible that these searches are meant to use the prefix order.
>> (Interestingly, they talk about "a depth-first order" not "the d-f
>> o.")
>
> Excuse me? A.18.10(5/3) defines what we (the Ada Standard) means by
> "depth-first order", and as it doesn't rely on any other documents,
> that's the meaning in the Standard. We wordsmithed that definition a
> lot, and it might not be perfect, but certainly the places that use
> the term depend on the definition from the standard, not what some
> other book might have defined. Whether we should have used a different
> term is a different question, but it isn't particular relevant as to
> whether the Standard is "well-specified".

You are right. I did not see that paragraph.

***************************************************************