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
