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
