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
