I just ran a couple of tests with prim_alg and prim_alg2, and it seems prim_alg2 seems to fail for the following matrix:
mat3 =: 7 7 $ _ _ _ _ 12 34 19, _ _ 30 _ 14 _ 22, _ 30 _ 18 10 _ _, _ _ 18 _ 40 27 11, 12 14 10 40 _ _ _, 34 _ _ 27 _ _ _, 19 22 _ 11 _ _ _ It's result: ┌───┬───┬───┬───┬───┬───┐ │0 4│1 2│1 1│2 3│4 6│4 5│ └───┴───┴───┴───┴───┴───┘ i.e. it contains the impossible edge 1 1 prim_alg gives the result: ┌───┬───┬───┬───┬───┬───┐ │0 4│4 2│4 1│2 3│3 6│3 5│ └───┴───┴───┴───┴───┴───┘ > From: [email protected] > Date: Fri, 24 Oct 2014 12:45:39 -0400 > To: [email protected] > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's Algorithm > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
