Not very sophisticated, and the first verb (wrapa) below doesn't even
reproduce your answer for N=6 , but it might be a starting point for
further work. The second verb (wrapb) does work for N=6, but apparently
greatly overestimates the number for your larger 2000 node graph!
wrapa=: 1 : 0
:
g =. <: > >:@I.each <"1 m NB. unboxed list of bnodes for each
anode, with _1 as filler
p =. 1 1 $ y NB. initial path matrix
N =. x
while. N =.<: N do.
from =. {:"1 p NB. anodes of current path-ends
to =. from{g NB. bnodes for each anode
nto =. +/"1 to >_1 NB. count number of bnodes for each anode
p =. nto#p NB. expand rows of path matrix
p =. p,. _1 -.~,to NB. append new path-ends
p =. ~.p NB. remove repeats
p =. (#~ {:@$ = #@~."1) p NB. exclude paths with repeated nodes
end.
p
)
[w6=:I."1]6 graph wrap 0 NB. original
0 4 6 14 15 16
0 4 6 14 15 18
0 6 7 14 15 16
0 6 8 14 15 16
0 6 12 14 15 16
0 6 14 15 16 18
0 3 6 14 15 18
[w6a=:/:~ 6 graph wrapa 0 NB. new
0 14 15 6 16 7
0 14 15 6 16 8
0 14 15 6 16 12
0 14 15 6 18 3
w6 -. /:~"1 w6a NB. paths missed by new approach
0 4 6 14 15 16
0 4 6 14 15 18
0 6 14 15 16 18
I don't see how these are "paths", and so I'm probably missing
something that you require.
However, this verb does yield the same results for N=6; the paths seem
to be trees:
wrapb=: 1 : 0
:
g =. <: > >:@I.each <"1 m NB. unboxed list of bnodes for each
anode, with _1 as filler
p =. 1 1 $ y NB. initial path matrix
N =. x
while. N =.<: N do.
from =. p NB. all anodes of current paths
to =. from{g NB. bnodes for each anode
nto =. +/"1^:2 to >_1 NB. count number of bnodes for each anode
p =. nto#p NB. expand rows of path matrix
p =. /:~"1 p,. _1 -.~,to NB. append new bnodes and sort
p =. ~.p NB. remove repeats
p =. (#~ {:@$ = #@~."1) p NB. exclude paths with repeated nodes
end.
p
)
But now it produces too many "paths" in your larger example, albeit
pretty fast:
timer'#10 graph2 wrapb 0' NB. apparently 12 times too many "paths"
+--------+-----+
|0.868896|72258|
+--------+-----+
("timer" is a variant of ts which shows time in seconds and the result)
wrapa is quicker but presumably wronger!
timer'#10 graph2 wrapa 0' NB. apparently 10 times too few "paths"
+---------+---+
|0.0170898|556|
+---------+---+
Anyway, I should think some variation on one of these verbs might scale
better than the incidence matrix approach, and produce something like
the results you need!
Mike
On 13/02/2013 9:38 PM, Raul Miller wrote:
Since I messed up the description, I'll just pose an example solution
and ask for improvements.
graph=: 1= ?.20 20$10
start=: ,:0=i.#graph
gather=: 1 :'[: ~.@; <@u'
wrap=: 1 :0
:
graph=. m
start=. ,:(i.#graph) e. y
N=. x
paths=. (+./ .* # (+."1 =@i.@#))&graph"1 gather^:(N-1) start
(N=+/"1 paths)#paths
)
Here's a representation of the graph I'm using:
#.graph
64 1536 4 72 3200 8224 296960 8225 65536 8192 32 524800 48 513 65 160
16416 32849 576 526466
$#:#.graph
20 20
Here's a count of visitable sets of six nodes starting from node 0
#6 graph wrap 0
17
In other words, wrap is an adverb which takes a graph and derives a
verb to generate the distinct visitable sets of length x starting from
the list of nodes indexed by the right argument.
Now, let's say that we wanted to scale this up to deal with a couple
thousand nodes (but with similar connectivity):
graph2=: 1=?.2000 2000$1000
Here, the algorithm I implemented starts getting slow when I look for
paths of length 100 (it's just under 6000 paths).
#10 graph2 wrap 0
5945
ts '#10 graph2 wrap 0'
13.7496 4.34907e8
That's a bit slow. Now let's imagine that I'm interested in finding
this path count for paths of length 100, in a reasonable amount of
time (let's say "less than a minute" for the sake of argument). In
this case, I believe that my reference implementation can only serve
as an example.
Better?
Thanks,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
