My code is for directed graphs as defined in Graphs in Computer Science:
http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html
However, suppose our undirected graph is
0--1--2--3 (the only edges are those shown).
Am I right that every set of two nodes is visitable from node 2? These are
{0 1} contained in 0--1--2
{0 2} contained in 0--1--2
{0 3} contained in 0--1--2--3
{1 2} contained in 1--2
{1 3} contained in 1--2--3
{2 3} contained in 2--3
( No order is implied in the conventional set notation {a b} )
Kip
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:
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
