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  
 
 [ 5 post ] 

 Relevant Pages 

1. Shortest Path algorithm needed

2. Shortest Path algorithm in APL

3. text along a path - algorithm?

4. Is Verification a dead-end technical career path?

5. Dijkstra's shortest path algorithm?

6. Dijkstra's Shortest Path algorithm

7. Need a shortest path algorithm

8. Critical Path Algorithm

9. path TRACING algorithm

10. Help with short path algorithm

11. Dijkstras shortest path algorithm

12. Path algorithm for undirected graph

 

 
Powered by phpBB® Forum Software