NB. from Sample Topic 21 of Dictionary
closure =: ([ +. +./ .*.)^:_~
NB. transforming distance matrix into boolean adjacency matrix
NB. and checking closure is all 1
connected =: (1 = *. / @: ( , @: closure)) @: (~: & _)
mat1 =: 5 5 $ _ 3 4 2 _, 3 _ _ 1 8, 4 _ _ 5 5, 2 1 5 _ _, _ 8 5 _ _
mat2 =: 3 3 $ _ 1 _, 1 _ _, _ _ _
NB. mat1 should be connected, while mat2 is disconnected.
connected mat1
1
connected mat2
0
On 29/10/2014 15:25, Jon Hough wrote:
I'm not sure how ~.(] +. +./ .*.~)^:_ works.
But if I do
f =: ~.(] +. +./ .*.~)^:_
f mat1 NB. please see mat1 in my original post
I get an error
|NaN error: f
| f mat1
I get the same error for mat1b,
where
mat1b =: 5 5 $ _ 1 1 1 _, 1 _ _ 1 1, 1 _ _ 1 1, 1 1 1 _ _, _ 1 1 _ _
Date: Wed, 29 Oct 2014 11:08:46 -0400
From: [email protected]
To: [email protected]
Subject: Re: [Jprogramming] Algorithm to Check Graph is connected
Elaborating on this:
graphs2=: ".&><;._2]0 : 0
0 1 0 1 0 0 1 0 0
1 0 0 0 1 0 1 0 0
0 0 0 0 0 1 0 1 0
1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1
0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 1 0
)
NB. Rough graphical representation of the above:
grPic=: 0 : 0
-------|
| 0 - 1 - 4
| |\ /|
|--6 3---/ |
|_______|
2--5
\ |
7--8
)
If we make a bidirectional version of "graphs2":
]grbi=. graphs2 +. |: graphs2
0 1 0 1 0 0 1 0 0
1 0 0 0 1 0 1 0 0
0 0 0 0 0 1 0 1 1
1 0 0 0 1 0 0 0 0
0 1 0 1 0 0 1 0 0
0 0 1 0 0 0 0 0 1
1 1 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 1
0 0 1 0 0 1 0 1 0
Then we can find the two unconnected groups:
~.(] +. +./ .*.~)^:_]grbi
1 1 0 1 1 0 1 0 0
0 0 1 0 0 1 0 1 1
However, I'm not sure about the result for the non-symmetric, original
graph:
~.(] +. +./ .*.~)^:_]graphs2
1 1 0 1 1 0 1 0 0
0 0 1 0 0 1 0 1 1
0 0 0 0 0 0 0 0 0
It may be thrown by the fact that node 4 has nodes directed to it but
directs to no other node.
Also, I'm putting the extra "] +." at the start of this expression because
I copied the APL from the "Directed Graphs" section of this -
http://www.jsoftware.com/papers/tot.htm - but am unsure if it's necessary
since, for this example, I get the same answer without it:
~.(] +./ .*.~)^:_]grbi
1 1 0 1 1 0 1 0 0
0 0 1 0 0 1 0 1 1
~.(] +./ .*.~)^:_]graphs2
1 1 0 1 1 0 1 0 0
0 0 1 0 0 1 0 1 1
0 0 0 0 0 0 0 0 0
On Wed, Oct 29, 2014 at 10:33 AM, Jan-Pieter Jacobs <
[email protected]> wrote:
Hmm, forgot some things in my previous mail, and got curious myself so I
looked it up myself.
The section in Mastering Dyalog APL is 5.3.6: "Is a graph contiguous?"
Spoiler allert
5
4
3
2
1
0
Translated to J the expression for indicating second rank connections would
be:
graph +./ . *. graph
If all nodes are connected after repeating this, then the graph is
connected. Converting distances to connected-or-not and pouring it all into
one verb:
connected0 =: ($$1:) -: [: (+./ . *.~ ^:_) _ ~: ]
or alternatively:
connected1 =: [: *./&,@(+./ . *.~ ^:_) _ ~: ]
connected mat1
(connected0;connected1) each mat1;mat2
┌─────┬─────┐
│┌─┬─┐│┌─┬─┐│
││1│1│││0│0││
│└─┴─┘│└─┴─┘│
└─────┴─────┘
Jan-Pieter
2014-10-29 15:13 GMT+01:00 Jan-Pieter Jacobs <[email protected]>:
Maybe not strictly J, but close enough and well explained:
Mastering Dyalog APL [1] has a section about applying inner product to
graph related problems. Translating the primitives or experimenting with
APL (NARS2000 or GNU APL are free implementations) itself might learn you
to apply the same approach in J.
Greetings,
Jan-Pieter
[1]:http://www.dyalog.com/mastering-dyalog-apl.html (free PDF download)
2014-10-29 13:51 GMT+01:00 Jon Hough <[email protected]>:
I have written an algorithm in J to test if a given graph is connected.
Graphs are represented as square matrices, where infinite entries
indicate no edge between the rowand column nodes.
My algorithm works (as far as I have tested it), but it is very
procedural and doesn't seem to fit in with the J style.
If possible I would like some tips on making it more J like. I found the
most difficult parts of doing any algorithms with square matrices to be
inserting values into elements of the matrix.
In C-like languages, this is very simple:
array[i][j] = 30;
for example. In J, I find it hard to replicate this. It seems the
suitable tool is {. But using this in a 2-d square doesn't seem so
simple.
For example, for the purposes of arithmetic, I wanted to convert all _
(infinite) edges to 0.
Anyway, this is my algorithm (copy-n-pasted straight from jQTide, so if
line endings are lost I apologize).
NB. Test if graph y is connected.
NB. Returns 1 if connected, 0 otherwise.
connected =: verb define
mat =: y NB. the graph (square matrix)
in =: 0 NB. list of connected nodes, start at node 0.
size =: # y NB. Size of y
all =: i. size NB. all nodes.
isconnected =: 0 NB. is connected flag.
counter =: 0
NB. loop through all nodes in graph.
NB. Add any nodes connected to the in list to the in list.
NB. If connected, in will eventually contain every node.
while. (counter < size) do.
counter=: counter + 1 NB. increment counter (very bad J?).
toin =: ''
NB. only want nodes that may not be connected. (remove "in"
nodes)
for_j. all -. in do.
NB. Get each column from in list and find non-infinite
NB. edges from these nodes to nodes in all - in list.
NB. (%) is to convert _ to 0.
if. ((+/@:%@:(j &{"2) @: (in& { "1) mat ) > 0) do.
toin =: toin , j
end.
end.
NB. append toin to in. Number of connected nodes increases.
in =: ~. in, toin
NB. check connectivity.
isconnected =:-. (# in ) < size
if. isconnected do.
end.
end.
isconnected
)
For testing purposes here are two sample matrices:
mat1 =: 5 5 $ _ 3 4 2 _, 3 _ _ 1 8, 4 _ _ 5 5, 2 1 5 _ _, _ 8 5 _ _
mat2 =: 3 3 $ _ 1 _, 1 _ _, _ _ _
mat1 should be connected, while mat2 is disconnected.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
--
Devon McCormick, CFA
----------------------------------------------------------------------
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
