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, -- Raul On Wed, Feb 13, 2013 at 2:23 PM, Raul Miller <[email protected]> wrote: > I described this poorly: > > A "path" implies a linear sequence, but all that's really required > here is that the nodes be connected. > > So for any one path, there's a frontier which is all of the nodes > adjacent to any node in that path which has not yet been visited on > that path. This frontier is dependent on the path, and not on the > graph - each path will have a different frontier. That said, once > each path has been extended independently there will be some number of > duplicates that need to be eliminated. > > For example, if you have a path AB and you extend it to include C and > you have a path AC and extend it to include B this is just one path > (ABC). > > -- > Raul > > On Wed, Feb 13, 2013 at 2:13 PM, Devon McCormick <[email protected]> wrote: >> Is there anything wrong with just walking the graph and setting each node >> visited to 0 while keeping track of where we've been? Once our walk ends, >> start again on any remaining node until they're all gone. >> >> >> On Wed, Feb 13, 2013 at 8:29 AM, Raul Miller <[email protected]> wrote: >> >>> Let's say that we have a directed, cyclic graph: >>> >>> graph=: 2 > ?20 20 $ 10 >>> >>> And, let's say that we have a starting node: >>> >>> start=: 19 >>> >>> And let us define a visitable set as a unique collection of nodes >>> reachable from a starting node (in other words, a path connects them). >>> >>> How can we find the number of distinct visitable sets of a given size >>> with a given starting node in a cyclic graph? >>> >>> Is it worth adjusting the graph so that node 0 is not connected >>> (adding 1 to all node indices)? >>> >>> Thanks, >>> >>> -- >>> Raul >>> ---------------------------------------------------------------------- >>> For information about J forums see http://www.jsoftware.com/forums.htm >>> >> >> >> >> -- >> Devon McCormick, CFA >> ^me^ at acm. >> org is my >> preferred e-mail >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
