iPad time and space results for Kip's code. Brian Schott tells me correctly
that verb open can be replaced by verb Raze ;
ones =: ; pairs 1 = ?. 200 200 $ 100 NB. paths with one move
# ones
390
5 {. ones NB. each pair represents one move
1 8
1 9
2 41
2 44
2 84
ts ';@:next^:3 ones' NB. create all paths with four moves
0.694511 2.89005e6
ts ';@:next^:4 ones' NB. create all paths with five moves
|out of memory: ts
| ;@:next^:4 ones
fours =: ;@:next^:3 ones NB. all paths with four moves
#fours
45601
5 {. fours NB. each five-tuple represents four moves
1 8 37 13 151
1 8 37 13 186
1 8 37 13 49
1 8 37 13 71
1 8 37 13 192
Kip Murray
Sent from my iPad
On Feb 15, 2013, at 6:23 PM, km <[email protected]> wrote:
>
> P.S. I do not expect my directed graph code to be efficient for large graphs
> and long chains, but I will experiment and report back.
>
> Sent from my iPad
>
>
> On Feb 15, 2013, at 3:30 PM, Raul Miller <[email protected]> wrote:
>
>> 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
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
