I should also note that while. (size > (# list)) do.
can be replaced with for. i. (#list)-1 do. In other words, the contents of the loop needs to run once per edge in the minimum spanning tree. Thanks, -- Raul On Fri, Oct 24, 2014 at 12:25 PM, Raul Miller <[email protected]> wrote: > Yes, that had line wrap problems, in comments. > > Here's versions of the code with comments removed: > > prim_alg =: verb define > list =. 0 > pairs =: '' > mat =. y > size =. 0{ $ y > while. (size > (# list)) do. > swap =. (0&*)`(1&*)@.(1&=) > remove =. ,@:|:@:(_&(list}))@:(list&{"1) > next =. (I.@:(swap"0)@:(=<./))@:remove mat > temp =. size | next > prevnode =. ((next - temp) % size ){ list > newnode =. temp > pairs =: pairs, (< ( prevnode, newnode)) > slist =. list, newnode > end. > pairs > ) > > and > > prim_alg2 =: verb define > mat =. y > size =. #y > list =. 0 > pairs =: '' > while. (size > (# list)) do. > next =. (i. <./) ,|:_ list} list {"1 mat > pairs =. pairs, <'prevnode newnode'=. (0,size)#: next > list =. list, newnode > end. > pairs > ) > > Hopefully that is readable. > > Thanks, > > -- > Raul > > > On Fri, Oct 24, 2014 at 12:20 PM, Raul Miller <[email protected]> > wrote: > >> 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
