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 <jgho...@outlook.com>: > 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
