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
