Ooops. Just realized why I got NAN errors. My graphs use _ to represent no connection. Sorry.
> From: jgho...@outlook.com > To: programm...@jsoftware.com > Date: Wed, 29 Oct 2014 15:25:55 +0000 > Subject: Re: [Jprogramming] Algorithm to Check Graph is connected > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
