In http://www.jsoftware.com/pipermail/programming/2006-September/003258.html the maximal connected subgraphs are determined in a fast way.
R.E. Boss > -----Original Message----- > From: programming-boun...@forums.jsoftware.com [mailto:programming- > boun...@forums.jsoftware.com] On Behalf Of Jon Hough > Sent: woensdag 29 oktober 2014 13:52 > To: programm...@jsoftware.com > Subject: [Jprogramming] Algorithm to Check Graph is connected > > 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
