Argh, sent prematurely: In terms of a code review, a few things:
1. It's imperative style and doesn't feel like idiomatic J. I wonder if it's possible to use more of an array style (no loops) 2. You are defining some verbs in the loop. Seek to define verbs outside the loop and only define nouns swap =. (0&*)`(1&*)@.(1&=) NB. to use J verbs (I.), swap _ with 0's. You may want to see Roger's essay on the topic: http://www.jsoftware.com/jwiki/Essays/Minimal%20Spanning%20Tree as a comparison implementation in J On Fri, Oct 24, 2014 at 12:09 PM, Joe Bogner <[email protected]> wrote: > 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
