Elaborating on this: graphs2=: ".&><;._2]0 : 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 )
NB. Rough graphical representation of the above: grPic=: 0 : 0 -------| | 0 - 1 - 4 | |\ /| |--6 3---/ | |_______| 2--5 \ | 7--8 ) If we make a bidirectional version of "graphs2": ]grbi=. graphs2 +. |: graphs2 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 Then we can find the two unconnected groups: ~.(] +. +./ .*.~)^:_]grbi 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 1 However, I'm not sure about the result for the non-symmetric, original graph: ~.(] +. +./ .*.~)^:_]graphs2 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 It may be thrown by the fact that node 4 has nodes directed to it but directs to no other node. Also, I'm putting the extra "] +." at the start of this expression because I copied the APL from the "Directed Graphs" section of this - http://www.jsoftware.com/papers/tot.htm - but am unsure if it's necessary since, for this example, I get the same answer without it: ~.(] +./ .*.~)^:_]grbi 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 1 ~.(] +./ .*.~)^:_]graphs2 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 On Wed, Oct 29, 2014 at 10:33 AM, Jan-Pieter Jacobs < janpieter.jac...@gmail.com> wrote: > 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 > -- Devon McCormick, CFA ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
