See the following (20. Directed Graphs) from the Dictionary http://www.jsoftware.com/docs/help801/dictionary/samp20.htm
--Kip Murray On Friday, October 24, 2014, Jon Hough <[email protected]> wrote: > Finding the minimum spanning tree of a graph is (in theory) pretty easy. > I wanted to see if I could write Prim's algorithm in J.The algorithm is > conceptually simple: http://en.wikipedia.org/wiki/Prim's_algorithm , and > I thought it would not be too difficult to write in J. My attempt goes like > this: > 1. Use a distance matrix to represent the graph (with infinity > representing no connection, and (i,i) positions are also infinity. > 2. Loop through the matrix, simultaneously looking for shortest edges from > a list of already counted nodes and strike out connections to any of these > nodes (to not make trees). > This is my attempt: > > > prim_alg =: verb define > > > > list =. 0 NB. list of already counted nodes (start at zero) > > > > pairs =: '' NB. the pairs, i.e. edges, of the spanning tree. > > > > mat =. y NB. distance matrix, infinity implies not adjacent. > > > > size =. 0{ $ y NB. Matrix must be square, so just get size of one axis. > > > > while. (size > (# list)) do. > > > NB. inner functions > > > > swap =. (0&*)`(1&*)@.(1&=) NB. to use J verbs (I.), swap _ with 0's. > > > > remove =. ,@:|:@:(_&(list}))@:(list&{"1) NB. remove rows already in the > list and flatten matrix. > > > > > > NB. get the next node (still need to get its(i,j) coords) > > > > next =. (I.@:(swap"0)@:(=<./))@:remove mat > > > > > > > NB. get the new node (row index in matrix) > > > > temp =. size | next > > > > prevnode =. ((next - temp) % size ){ list NB. find which node reached the > new node. > > > > newnode =. temp > > > > pairs =: pairs, (< ( prevnode, newnode)) > > > > NB. add new node to list (so don't try to reach it in next iteration). > > > > list =. list, newnode > > > > end. > > > > pairs > > > > ) > > It seems to work for the matrices I fed it. Here is an example of a > distance matrix: > > mat0 =: 5 5 $ _ 2 5 _ 10, 2 _ 11 _ 7, 5 11 _ 6 _, _ _ 6 _ 9, 10 7 _ 9 _ > > > Oh, and before I forget, don't feed it matrices of non-connected graphs, I > think it will infinitely loop. I need to fix that. > > > I understand that it would have been better to use Sparse arrays, if the > algorithm is intended to scale up to large graphs, but I haven't got there > yet. > > > For now, I would appreciate any comments for improvement, criticisms and > explanations of why I am doing things wrong. A code review, I suppose. > > > I was surprised how difficult it was to write this, given that J is a > matrix oriented language and graphs can be comfortably represented as > matrices, so I am assuming I mad elife difficult for myself somewhere. > > > Anyway, thanks, > Jon > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Sent from Gmail Mobile ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
