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
