On a tangentially related note: It's usually worthwhile first coming up with something that works and then (if performance is an issue) addressing the problems.
It's somewhat frightening, sometimes, how bad problems can be (and honestly, in this example of minimum spanning tree code the problems are not all that bad). But not having anything that works at all is generally worse than something that works in a flawed manner. That said, the existence of flaws that you have created tends to impose an obligation on you (to fix them), and that can be something of a struggle sometimes. Thanks, -- Raul On Fri, Oct 24, 2014 at 12:34 PM, Jon Hough <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
