[Jprogramming] Minimum Spanning Tree, J and Prim's Algorithm
Raul Miller
rauldmiller at gmail.com
Fri Oct 24 16:39:26 UTC 2014
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 <rauldmiller at gmail.com> 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 <rauldmiller at gmail.com>
> 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 <jghough at outlook.com> 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: joebogner at gmail.com
>>> > To: programming at jsoftware.com
>>> > 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 <jghough at outlook.com>
>>> 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
>>>
>>
>>
>
More information about the Programming
mailing list