Algorithm to Enumerate paths to end of tree???
Author Message
Algorithm to Enumerate paths to end of tree???

Suppose  I have a simple  "level 3" tree that looks like the following:
(best viewed with fixed pitch font)

A
/ \
B   C
/ \ / \
D   E   F

I want an APL algorithm that will enumerate all of the paths that lead
from the root "A" to the end nodes D, E, and F; that is it should
generate

the single way to get to D (path=ABD)
the two ways to get to E   (paths=ABE and ACE)
The single way to get to F (path=ACF)

The algorithm should generate all of the paths for a tree of any level
(i.e. a "level 4" tree would have as its terminal nodes "G,H,I,J", and we
wish to generate ALL paths from the root "A" to EACH of the terminal
nodes "G H I J"; a "level 5" would have as its terminal nodes
"K,L,M,N,O", and we wish to generate ALL the paths from the root "A" to
EACH of the terminal nodes "K L M N O", etc. I may have to go to level
100)

I know that Pascals triangle will give me the NUMBER of paths that reach
any terminal node, however I am interested in enumerating EACH path. (I
realize the sum of the hundredth  row of Pascals triangle implies an
awfully big number of paths for a level 100 tree, so maybe Ill settle
for a level 50 or 60, but I only have to compute this once and store it)

If the problem is made easier by using a different naming scheme for the
nodes (Perhaps numeric labels i.e. root =1, level 3 = 4,5,6 ??) please
feel free to do so. The representation is not very important, (although
the language is, I dont know any J), the key is to completely enumerate
all the possible paths.

Thanks for taking the time
Regards
Tony

Fri, 31 Dec 1999 03:00:00 GMT
Algorithm to Enumerate paths to end of tree???

Quote:

> Suppose  I have a simple  "level 3" tree that looks like the following:
> (best viewed with fixed pitch font)

>                       A
>                      / \
>                     B   C
>                    / \ / \
>                   D   E   F

> I want an APL algorithm that will enumerate all of the paths that lead
> from the root "A" to the end nodes D, E, and F; that is it should
> generate

> the single way to get to D (path=ABD)
> the two ways to get to E   (paths=ABE and ACE)
> The single way to get to F (path=ACF)

> The algorithm should generate all of the paths for a tree of any level

There are 2*N paths in the DAG (not a tree!) of this family with 1+N
levels.  Each
path can be specified as one of the length-N vectors

PathArray{<-}{first} ({jot}.,)/N{rho}{enclose}'LR'

indicating wheteher the left or right branch is taken.

It is convenient to the present purpose to ravel and mix and convert to
numeric

PathMat{<-}'R'={disclose}[1],PathArray   {nb} still origin 0

Where you are at each levelis given [in origin 0] by the number of R's
on the path
(+\PathMat) offset to the first node at the level.  For N+1 levels, the
vector of offsets is +\{iota}N+1, also in origin 0.  The labeling of a
path is then (using integers, of which there are many)

({iota}.5 {x} N {x} N+1)[+\PathMat+({rho}PathMat){rho}1+{iota}N]

Well, something close to this, anyway.  And there -are- esier ways to
generate the matrix
PathMat; this way just seems to match the problem structure ...

// m

Sat, 01 Jan 2000 03:00:00 GMT
Algorithm to Enumerate paths to end of tree???

Tony Corso writes on Monday, July 14:

Quote:
> Suppose  I have a simple  "level 3" tree that looks like the following:
> (best viewed with fixed pitch font)

>                       A
>                      / \
>                     B   C
>                    / \ / \
>                   D   E   F

> I want an APL algorithm that will enumerate all of the paths that lead
> from the root "A" to the end nodes D, E, and F; that is it should
> generate

> the single way to get to D (path=ABD)
> the two ways to get to E   (paths=ABE and ACE)
> The single way to get to F (path=ACF)

> The algorithm should generate all of the paths for a tree of any level
> (i.e. a "level 4" tree would have as its terminal nodes "G,H,I,J", and we
> wish to generate ALL paths from the root "A" to EACH of the terminal
> nodes "G H I J"; a "level 5" would have as its terminal nodes
> "K,L,M,N,O", and we wish to generate ALL the paths from the root "A" to
> EACH of the terminal nodes "K L M N O", etc. I may have to go to level
> 100)

> I know that Pascal's triangle will give me the NUMBER of paths that reach
> any terminal node, however I am interested in enumerating EACH path. (I
> realize the sum of the hundredth  row of Pascal's triangle implies an
> awfully big number of paths for a level 100 tree, so maybe I'll settle
> for a level 50 or 60, but I only have to compute this once and store it)

> If the problem is made easier by using a different naming scheme for the
> nodes (Perhaps numeric labels i.e. root =1, level 3 = 4,5,6 ??) please
> feel free to do so. The representation is not very important, (although
> the language is, I don't know any J), the key is to completely enumerate
> all the possible paths.

Strictly speaking, the graph is a directed acyclic graph rather
than a tree.  Anyway,

At each point in a path, going down from the root, there are
exactly two choice -- left or right.  Let left be 0 and
right be 1.  The task of generating all paths in a n-level
DAG, is exactly generating all n-bit binary numbers.

p.s. I doubt that you'd be able to store all the paths of
even a 50-level DAG!

Sat, 01 Jan 2000 03:00:00 GMT
Algorithm to Enumerate paths to end of tree???

Quote:

>Suppose  I have a simple  "level 3" tree that looks like the following:
>(best viewed with fixed pitch font)

>                      A
>                     / \
>                    B   C
>                   / \ / \
>                  D   E   F

>I want an APL algorithm that will enumerate all of the paths that lead
>from the root "A" to the end nodes D, E, and F; that is it should
>generate

Is this a "pascal's triangle" tree or is it an arbitrary tree?

(I

Quote:
>realize the sum of the hundredth  row of Pascals triangle implies an
>awfully big number of paths for a level 100 tree, so maybe Ill settle
>for a level 50 or 60, but I only have to compute this once and store it)

Interesting, the storage requirements for a balanced tree like above
would be

',' format 50 * 2x ^ 50
56,294,995,342,131,200   NB. good luck...

Perhaps the _REAL_ problem would be worth stating.

Quote:
>If the problem is made easier by using a different naming scheme for the
>nodes (Perhaps numeric labels i.e. root =1, level 3 = 4,5,6 ??) please
>feel free to do so. The representation is not very important,

(although the language is, I dont know any J),

any APL will do?

Quote:
>the key is to completely enumerate  all the possible paths.

--
|\/| Randy A MacDonald       | Come to APL'97!!

BSc(Math) UNBF '83      | APL: If you can say it, it's done.

| Also http://www.godin.on.ca/randy
------------------------------------------------<-NTP>----{ gnat }-

Sat, 01 Jan 2000 03:00:00 GMT
Algorithm to Enumerate paths to end of tree???

Quote:

>>Suppose  I have a simple  "level 3" tree that looks like the following:
>>(best viewed with fixed pitch font)

>>                      A
>>                     / \
>>                    B   C
>>                   / \ / \
>>                  D   E   F

>>I want an APL algorithm that will enumerate all of the paths that lead
>>from the root "A" to the end nodes D, E, and F; that is it should
>>generate

Here is a function that, given a bit vector representation of a single
path to a point, (i.e. E = 0 0 1) will generate all others that go
to that point.

{del} r{is}next v;d
[1]
[2]    :if (v{iota}0)=1++/v
[3]      r{is}{reverse}v
[4]    :else
[5]      d{is}-1+(1 0{epsunderbar}{reverse}v){iota}1
[6]      r{is}(d{drop}v),{neg}1{rotate}d{take}(+/d{take}v)/1
[7]    :end
{del}

example:
next 0 0 0 1 1 1
0 0 1 0 1 1

When the function reaches the end of the possible items, it will
start back with the first in the list:

next 1 1 1 0 0 0
0 0 0 1 1 1

--
|\/| Randy A MacDonald       | Come to APL'97!!

BSc(Math) UNBF '83      | APL: If you can say it, it's done.

| Also http://www.godin.on.ca/randy
------------------------------------------------<-NTP>----{ gnat }-

Mon, 03 Jan 2000 03:00:00 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages