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
