The rough J equivalent of C's array[i][j] = 30; would be 30 (<i,j)} array
For example: 30 (<2 3)} 6 6$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 That said, be aware that often (not always, but often enough to be worth discussing the algorithm) J will offer better approaches. For example, for your connectedness problem: mat1 =: 5 5 $ _ 3 4 2 _, 3 _ _ 1 8, 4 _ _ 5 5, 2 1 5 _ _, _ 8 5 _ _ mat2 =: 3 3 $ _ 1 _, 1 _ _, _ _ _ (<. <./ .+~)~^:# mat1 4 3 4 2 9 3 2 6 1 8 4 6 8 5 5 2 1 5 2 9 9 8 5 9 10 (<. <./ .+~)~^:# mat2 2 1 _ 1 2 _ _ _ _ The expression (<. <./ .+)~^:_ finds the path distance between every pair of points in your distance matrix. If any of them are _ the matrix is not connected. _ e. , (<. <./ .+)~^:_ mat1 0 _ e. , (<. <./ .+)~^:_ mat2 1 The expression (<. <./ .+)~^:# is a slightly less efficient version of (<. <./ .+)~^:_ The difference is that # specifies a repeat count equal to the number of rows in the matrix, while _ stops as soon as the result converges. To see why this matters, it can be instructive to look at some examples. You can see all the intermediate results (as well as initial and final values) by using a: instead: (<. <./ .+~)~^:a: mat1 _ 3 4 2 _ 3 _ _ 1 8 4 _ _ 5 5 2 1 5 _ _ _ 8 5 _ _ 4 3 4 2 9 3 2 6 1 8 4 6 8 5 5 2 1 5 2 9 9 8 5 9 10 and (<. <./ .+~)~^:a: mat2 _ 1 _ 1 _ _ _ _ _ 2 1 _ 1 2 _ _ _ _ The final result was achieved on the first iteration in both examples. So... how does that expression work? Structurally, it's doing something very like a transitive closure. See example 5 in the dictionary entry for ^: http://jsoftware.com/help/dictionary/d202n.htm Except, each iteration, it's adding every pair between two copies of the distance matrix and then for each endpoint pair finding the minimum distance which resulted. And, for sanity's sake, taking the minimum of that result and the original pair distance. The tricky part, if you have not seen it before, is the inner product: u/ .v Matrix multiplication is +/ .* and we are following the same pattern here. Rather than try to document the details, however, I would prefer to point you at the dictionary http://jsoftware.com/help/dictionary/d202n.htm and the nuvoc page http://www.jsoftware.com/jwiki/Vocabulary/dot#dyadic (The other thing I am using is the u~ pattern. That's even simpler: u~y is equivalent to y u y. So, +~1 is equivalent to 1+1. Actually, it's so simple that it's worth explaining just because otherwise it's something your eyes might gloss over.) Anyways, unless you are working with connection matrices which stress the capacity of your machine, I imagine that finding all the path distances and checking if any are infinity will be faster than your 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 ) I hope this helps, -- Raul On Wed, Oct 29, 2014 at 8:51 AM, Jon Hough <jgho...@outlook.com> 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
