In terms of a code review, a few things: the first thing that jumps out to me is that you're defining some verbs in your loop:
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
