I'll have to take some time to read your code (there's a lot of it). But perhaps this can illustrate why I initially called them "paths" (though they can branch):
Here's a numeric representation of the connection graph. First column is index, second column represents what that node connects to: (,.~ <"0@i.&#) <@I. graph +--+----------+ |0 |13 | +--+----------+ |1 |9 10 | +--+----------+ |2 |17 | +--+----------+ |3 |13 16 | +--+----------+ |4 |8 9 12 | +--+----------+ |5 |6 14 | +--+----------+ |6 |1 4 8 | +--+----------+ |7 |6 14 19 | +--+----------+ |8 |3 | +--+----------+ |9 |6 | +--+----------+ |10|14 | +--+----------+ |11|0 10 | +--+----------+ |12|14 15 | +--+----------+ |13|10 19 | +--+----------+ |14|13 19 | +--+----------+ |15|12 14 | +--+----------+ |16|5 14 | +--+----------+ |17|4 13 15 19| +--+----------+ |18|10 13 | +--+----------+ |19|0 8 12 18 | +--+----------+ Here's successively longer "paths" on this graph, starting from from node 0: I. 1 graph wrap 0 0 I. 2 graph wrap 0 0 13 I. 3 graph wrap 0 0 10 13 0 13 19 I. 4 graph wrap 0 0 10 13 14 0 10 13 19 0 8 13 19 0 12 13 19 0 13 18 19 In other words, even though I do not actually care about what order the nodes have been visited, I know that every potentially branching path with N nodes can be reached from some "path" with N-1 nodes by visiting one additional unconnected node from a node that was connected on the N-1 "path". Alternatively, if you want to think about potentially branching path's "length" there's N-1 connections used in a path with N nodes. Does this help think about the problem? And, I appreciate you for taking the time, despite my failures to be adequately descriptive. 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
