I'm not sure how ~.(] +. +./ .*.~)^:_ works. But if I do f =: ~.(] +. +./ .*.~)^:_ f mat1 NB. please see mat1 in my original post I get an error
|NaN error: f | f mat1 I get the same error for mat1b, where mat1b =: 5 5 $ _ 1 1 1 _, 1 _ _ 1 1, 1 _ _ 1 1, 1 1 1 _ _, _ 1 1 _ _ > Date: Wed, 29 Oct 2014 11:08:46 -0400 > From: devon...@gmail.com > To: programm...@jsoftware.com > Subject: Re: [Jprogramming] Algorithm to Check Graph is connected > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
