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 <janpieter.jac...@gmail.com>: > 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
