Joe Bogner said: "1. It's imperative style and doesn't feel like idiomatic J. I wonder ifit's possible to use more of an array style (no loops)" Yes, I realized that. I'm still not great at thinking only in arrays. But, specifically for this problem, I'm not sure it is possible to do it without an explicit for or while loop. As in your link: http://www.jsoftware.com/jwiki/Essays/Minimal%20Spanning%20Tree even Roger Hui's minimal spanning tree needed a for loop.
> From: [email protected] > To: [email protected] > Date: Fri, 24 Oct 2014 17:29:17 +0100 > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's Algorithm > > I just realized > > (i. <./) ,|:_ list} list {"1 mat > does the removal. You put it much more tersely than I did. > > From: [email protected] > > To: [email protected] > > Date: Fri, 24 Oct 2014 17:27:50 +0100 > > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's Algorithm > > > > OK, thanks. I think I understand prim_alg2. > > The meat of it seems to be in: > > next =. (i. <./) ,|:_ list} list {"1 mat > > pairs =. pairs, < 'prevnode newnode'=. (0,size)#: next > > I'm not sure how you are making sure no cycles form (the way I used the > > remove verb), but your algorithm definitely works.I think Outlook.com is > > messing up my line endings. I apologize for garbled emails. > > > > > From: [email protected] > > > Date: Fri, 24 Oct 2014 12:20:11 -0400 > > > To: [email protected] > > > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's Algorithm > > > > > > That is still coming through garbled, for me. > > > > > > So here's my attempt at posting your code: > > > > > > mat0 =: 5 5 $ _ 2 5 _ 10, 2 _ 11 _ 7, 5 11 _ 6 _, _ _ 6 _ 9, 10 7 _ 9 _ > > > > > > 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). > > > slist =. list, newnode > > > end. > > > pairs > > > ) > > > > > > > > > Maybe a gist would be better, since it looks like some of those lines > > > might > > > wrap. > > > > > > Also, I think this code can be simplified. Here's my attempt at that: > > > > > > prim_alg2 =: verb define > > > mat =. y NB. distance matrix, infinity implies not adjacent. > > > size =. #y NB. Matrix must be square, so just get size of one axis. > > > list =. 0 NB. list of already counted nodes (start at zero) > > > pairs =: '' NB. the pairs, i.e. edges, of the spanning tree. > > > while. (size > (# list)) do. > > > NB. get the next node (still need to get its(i,j) coords) > > > next =. (i. <./) ,|:_ list} list {"1 mat > > > pairs =. pairs, < 'prevnode newnode'=. (0,size)#: next > > > NB. add new node to list (so don't try to reach it in next iteration). > > > list =. list, newnode > > > end. > > > pairs > > > ) > > > > > > Finally, to explain my perhaps cryptic comments in my previous email, > > > here's the minimum spanning distance between any two nodes in that graph: > > > > > > (<. <./ .+) mat0 > > > 29 2 5 29 10 > > > 2 29 11 29 7 > > > 5 11 29 6 29 > > > 29 29 6 29 9 > > > 10 7 29 9 29 > > > > > > The maximum value, here (29) represents a bound on the minimum spanning > > > tree. > > > > > > Thanks, > > > > > > -- > > > Raul > > > > > > On Fri, Oct 24, 2014 at 11:57 AM, Jon Hough <[email protected]> wrote: > > > > > > > Here it is > > > > > > > > > > > > > > > > prim_alg =: verb define > > > > > > > > list =. 0 NB. list of already counted nodes (start at zero) > > > > > > > > pairs =: '' NB. the pair, i.e. edges, of the spanning tree. > > > > > > > > mat =. y NB. distance matrix, infinity imlies not > > > > adjacent. > > > > > > > > size =. 0{ $ y NB. Matrix must be square, so just get size of one axis. > > > > > > > > while. (size > (# list)) do. > > > > > > > > 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 > > > > > > > > next =. 0{ next > > > > > > > > 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 > > > > > > > > ) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > mat0 =: 4 4 $ _ _ _ 2, _ _ _ 5, _ _ _ 1. 2 5 1 _ > > > > > > > > mat1 =: 5 5 $ _ 2 5 _ 10, 2 _ 11 _ 7, 5 11 _ 6 _, _ _ 6 _ 9, 10 7 _ 9 _ > > > > > > > > mat2 =: 6 6$ _ 184 222 177 216 231, 184 _ 45 123 128 200, 222 45 _ > > > > 129 121 203, 177 123 129 _ 46 83, 216 128 121 46 _ 83, 231 > > > > 200 > > > > 203 83 83 _ > > > > > > > > > > > > > > > > > > > > > > > > (along with some example matrices) > > > > > Date: Fri, 24 Oct 2014 11:53:28 -0400 > > > > > From: [email protected] > > > > > To: [email protected] > > > > > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's > > > > > Algorithm > > > > > > > > > > Jon, can you resend without the extra line feeds? > > > > > > > > > > You may need to paste as text or ctrl+shift+v > > > > > > > > > > Pasting it into another editor, such as notepad and then copy/pasting > > > > from > > > > > there is another way to be sure it's plain text > > > > > > > > > > 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 > > > > > > > > ---------------------------------------------------------------------- > > > > 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 > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
