Algorithm to Enumerate paths to end of tree???
Author 
Message 
Tony Cor #1 / 5

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 


Mike Ken #2 / 5

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 lengthN 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 


Roger Hu #3 / 5

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 nlevel DAG, is exactly generating all nbit binary numbers. p.s. I doubt that you'd be able to store all the paths of even a 50level DAG!

Sat, 01 Jan 2000 03:00:00 GMT 


Randy MacDona #4 / 5

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 


Randy MacDona #5 / 5

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 


