http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm looks better suited for J.
Also perhaps relevant would be the directed graphs portion of http://www.jsoftware.com/papers/tot.htm (that's a bit old, though, and my browser does not deal properly with some of the notation - which is APL rather than J - still, it can give some hints. Also the bit about distance matrices in the generalized matrix product part of http://www.jsoftware.com/papers/PNSD.htm might give some help at deciphering the notation in the tool of thought essay). Thanks, -- Raul -- Raul On Fri, Oct 24, 2014 at 10:02 AM, 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
