Yes: for me, since I was just interested in knowing the unique sets of visitable nodes with a population of N, I would treat 1 8 6 and 1 6 8 as equivalent (or, more precisely, in the context of your code: interchangeable), and I would treat a 7 7 path as visiting only a single node.
How does your code fair with large (sparsely connected) graphs and large visitable sets? Thanks, -- Raul On Fri, Feb 15, 2013 at 4:19 PM, km <[email protected]> wrote: > Raul, > > I have carefully ignored your later posts and may be on a different track > than you intended. Here is where I am. Path 1 8 6 means there is a directed > edge from 1 to 8 and a directed edge from 8 to 6 and is different from path > 1 6 8 if such a path exists. You can even have a one edge path 7 7 which > loops from 7 to 7. Notice my use of ^: Power in the last sentence of this > long post. > > Kip Murray > > ]graph=: 2 > ?. 10 10 $ 10 NB. Raul had 20 20 $ 10 > 0 0 0 0 0 0 1 0 1 0 > 0 0 0 0 1 0 0 1 1 0 > 1 0 1 0 0 1 0 0 0 0 > 0 0 0 0 0 1 0 0 0 0 > 1 0 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 1 0 > 0 1 0 0 0 0 0 1 0 0 > 0 0 0 0 0 0 1 0 0 0 > 0 0 0 0 0 0 0 0 0 0 > > NB. A 1 in row p column q indicates a directed edge from p to q > > edges =: [: I.&.> <"1 NB. utility > > edges graph > +---+-----+-----+-+-++-+---+-++ > |6 8|4 7 8|0 2 5|5|0||8|1 7|6|| > +---+-----+-----+-+-++-+---+-++ > > pairs =: i.@# ,.&.> edges NB. utility > > pairs graph > +---+---+---+---+---+--+---+---+---+--+ > |0 6|1 4|2 0|3 5|4 0| |6 8|7 1|8 6| | > |0 8|1 7|2 2| | | | |7 7| | | > | |1 8|2 5| | | | | | | | > +---+---+---+---+---+--+---+---+---+--+ > > open =: 3 : '> ,&.>/(-. (0, {: $ > 0 { y) -:"1 $&> y)#y' NB. utility > > ]twos =: open pairs graph NB. directed edges from 0 to 6, 0 to 8 and so on > 0 6 > 0 8 > 1 4 > 1 7 > 1 8 > 2 0 > 2 2 > 2 5 > 3 5 > 4 0 > 6 8 > 7 1 > 7 7 > 8 6 > > NB. no edge from 5 or 9, no edge to 3 or 9 > > NB. there is an edge from 7 to 7 (a one-edge loop) > > more =: 4 : '~. y ,"1 0 {:"1 (({:y) = {."1 x)# x' NB. x is an open table, > y is a table row > > next =: 3 : 'y&more &.> <"1 y' NB. y is table of paths, result is boxed > one longer paths > > countpaths =: 4 : '+/ y = {."1 x' NB. count paths in open x that begin > with y > > ]threes =: open next twos NB. paths from 0 to 6 to 8, from 0 to 8 to 6, > and so on > 0 6 8 > 0 8 6 > 1 4 0 > 1 7 1 > 1 7 7 > 1 8 6 > 2 0 6 > 2 0 8 > 2 2 0 > 2 2 2 > 2 2 5 > 4 0 6 > 4 0 8 > 6 8 6 > 7 1 4 > 7 1 7 > 7 1 8 > 7 7 1 > 7 7 7 > 8 6 8 > > threes countpaths 7 NB. five paths begin from 7 > > ]fours =: open next threes > 0 6 8 8 > 0 8 6 6 > 1 4 0 8 > 1 4 0 6 > 1 7 1 0 > 1 7 1 1 > 1 7 1 7 > 1 7 1 6 > 1 7 7 4 > 1 7 7 7 > 1 7 7 8 > 1 7 7 1 > 1 8 6 6 > 2 0 6 6 > 2 0 8 8 > 2 2 0 8 > 2 2 0 6 > 2 2 2 6 > 2 2 2 8 > 2 2 2 0 > 2 2 2 2 > 2 2 2 5 > 4 0 6 6 > 4 0 8 8 > 6 8 6 6 > 7 1 4 6 > 7 1 4 8 > 7 1 7 4 > 7 1 7 7 > 7 1 7 8 > 7 1 7 1 > 7 1 8 8 > 7 7 1 0 > 7 7 1 1 > 7 7 1 7 > 7 7 1 6 > 7 7 7 4 > 7 7 7 7 > 7 7 7 8 > 7 7 7 1 > 8 6 8 8 > > fours countpaths 7 NB. fifteen paths from 7 > > fours -: open@:next^:2 twos > 1 > > > Sent from my iPad > > > On Feb 13, 2013, at 7: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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
