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
