After reading this code, I see two issues.
First, this line:
p=. 1 1 $ y
should be
p=. ,. y
The original supported multiple start nodes, and I do not yet see any
simplicity advantages to considering only a single starting node. We
already need to deal with multiple paths, so why not allow that right
from the start?
But this is a problem for me:
from =. {:"1 p NB. anodes of current path-ends
here, you assume that paths do not branch, and I explicitly want to
allow branches.
You could probably do something with
to=. p { g
nto=. +/"1 to >_1
p=. (+/"1 nto)#p
...
but hypothetically speaking I could get similar performance
characteristics by using a sparse array for the graph?
Thanks,
--
Raul
On Thu, Feb 14, 2013 at 7:40 PM, Mike Day <[email protected]> wrote:
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
