Thank you, again. I have not yet had time to read through wrapb, but a quick glance suggests that the "too many paths (or 'trees', maybe )" issue could probably be resolved by sorting each "path" before determining uniqueness.
That said, I am more uncomfortable labelling these "visitable sets" with the word "trees" rather than "paths". A tree would imply, to me, that I've retained a particular connection structure, and all I care about is whether the node has been visited. Perhaps I should model this as "when a connection is used the reverse connection is also made available in the context of that path" - actually implementing that seems computationally inefficient, but it would resolve the conflict between this use of the word "path" and its use in other graph problems. Thanks, -- Raul On Fri, Feb 15, 2013 at 2:04 PM, Mike Day <[email protected]> wrote: > Thanks. I think my verb "wrapb" _is_ doing what you want, even though it > doesn't get your answer of 5945 tree-paths for > 10 graph2 wrap 0 > > I've just seen your later posting. > Sorry about 1 1$y - I agree, but had thought you only wanted a single > starting node. > > You then say > > " > > 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. > > " > Yes - that's your problem with my "wrapa", but I think "wrapb" does what > you want, where every node in every row is treated as a potential anode. > > You close with > > " > > but hypothetically speaking I could get similar performance > characteristics by using a sparse array for the graph? > > " > Maybe sparse matrices will perform similarly well/badly... Running wrap on > $.graph yields a non-sparse result! > > I'd drafted the following comments before your latest mail. > > I was getting the same answers (after appropriate re-labelling of the > different outputs) from your wrap and my wrapb for graph2 starting from node > 0 for N=2,3,4,5,6,7. > Thereafter (for N>7) I couldn't be bothered to wait for wrap to terminate! > > wrapb reports 72258 paths for N=10, origin = 0. > > HOWEVER - wrapb runs out of memory with my 32-bit OS for N=11, so N=100 > presents a considerable poser even for this method. > > The following verb (wrapc) is a bit leaner than wrapb but still encounters > memory problems at N=11! > > I expect some lines will wrap! > > wrapc=: 1 : 0 > : > g =. 0, > >:@I.each <"1 m NB. unboxed list of bnodes for each anode, > with 0 as filler, all offset by 1 > p =. 0,.,.y+1 NB. initial path matrix; prepended 0 helps > remove phantom zero bnodes > > N =. x > while. N =.<: N do. > to =. p-.~"1~."1 ,/"2 p{g NB. bnodes for each anode, excluding > those already in a row (part path) > nto =. +/"1 to>0 NB. count number of new bnodes for each > row > > p =. nto#p NB. expand rows of path matrix > p =. /:~"1 p,. 0-.~,to NB. append new bnodes and sort - MEMORY > PROBLEMS ARISE HERE! > > p =. ~.p NB. remove repeats > end. > <:}."1 p > ) > > These methods benefit from using a rectangular structure for the tree/paths. > Evidently there is a lot of redundancy and some memory improvement would > ensue from a tree-structure - eg 4 graph wrap 0 could collapse to something > like > 0 > + > 13 > --------- > 14 19 > + + > + ---------- > 10 8 10 12 18 > > but the processing would be quite a bit more complicated... > > Even my wrapa, which yields non-branching paths, runs out of steam around > N=20, even after a bit of tweaking which I won't bother you with here. > > Mike > > > > On 15/02/2013 1:17 PM, Raul Miller wrote: >> >> 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, >> > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
