array[i][j] = 30;
A =. 4 6$i.5
A
0 1 2 3 4 0
1 2 3 4 0 1
2 3 4 0 1 2
3 4 0 1 2 3
array=. dyad define
('a';'b') =. y
b =. < b
a b } x
)
A array 30;2 2
0 1 2 3 4 0
1 2 3 4 0 1
2 3 30 0 1 2
3 4 0 1 2 3
On 29 Oct 2014 12:52, "Jon Hough" <[email protected]> wrote:
> 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
