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
