sons=: (~. i. [EMAIL PROTECTED]) { a: ,~ (</. [EMAIL PROTECTED])
gen =: ([: <@~.@; >@[ { ])"0 1~
rc =: [EMAIL PROTECTED] ~.@,&.> ]
rtc =: gen^:_ @ rc @ sons
sd =: (>@] +/@:{ [)"_ 0
tsum=: 4 : 0
z=. x + t=. x sd d=. (sons y) -.&.> i.#y
while. +./0~:t do.
z=. z + t=. z sd d=. gen d
end.
)
"sons" computes the list of sons from the parents.
"rc" computes the reflexive closure. "gen" computes
the next generation of descendants from the current
generation. "rtc" computes the reflexive-transitive
closure.
"tsum" adopts and adapts the transitive closure logic.
It computes successive generations of descendants
(pronoun d) and adds their sums to the total.
p=: p: inv 1+i.100
n=: 100 [EMAIL PROTECTED] 25
(n treesum p) -: n tsum p
1
ts 'n treesum p'
0.000604717 34048
ts 'n tsum p'
0.00328381 56320
p=: p: inv 1+i.2e4
n=: 2e4 [EMAIL PROTECTED] 25
ts 'n tsum p'
301.378 1.27693e7
For small sets of nodes, the connection matrix approach
is more efficent. For large sets the situation changes.
In the last example, *:#n is 4e8 so the connection matrix
approach would require at least that much space.
----- Original Message -----
From: Raul Miller <[EMAIL PROTECTED]>
Date: Tuesday, March 11, 2008 12:57
Subject: [Jprogramming] tree sum and difference
To: Programming forum <[email protected]>
> So, let's say that I have a tree structure where 0
> is the parent of all other nodes
> parents=: p:inv 1+i.10
> and that I have some numbers associated with
> the nodes of this tree
> n=: ?.100+i.10
>
> I can produce a tree-wise sum, for example:
> connmat=:3 :'(e."0 1/ [:|:{&y^:a:)i.#y'
> treesum=: +/ .* |:@connmat
> parents,n,:n treesum parents
> 0 0 1 2 2
> 3 3 4 4 4
> 46 25 101 69 102 9 58 45 40 64
> 559 513 488 136 251 9 58 45 40 64
>
> I can also find the tree-wise difference, for example:
> treediff=: %. connmat
> 559 513 488 136 251 9 58 45 40 64 treediff parents
> 46 25 101 69 102 9 58 45 40 64
>
> However, it seems that there ought to be faster
> approaches for large trees (with hundreds or
> thousands of nodes).
>
> So, since some people like puzzles, can anyone
> come up with faster implementations for treesum
> and treediff, for large trees?
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
