Oops, that's a rather bad problem. Here's a fixed version:
prim_alg2a =: verb define
mat =. y
size =. #y
list =. 0
pairs =: ''
while. (size > (# list)) do.
next =. (i. <./) ,|:_ list} list {"1 mat
'pndx newnode'=. (0,size)#: next
pairs =. pairs, < (pndx{list),newnode
list =. list, newnode
end.
pairs
)
As you can see, I was calculating the "node coming from" incorrectly, which
happened to work for the original test data, but not for this data set.
Thanks,
--
Raul
On Sat, Oct 25, 2014 at 1:44 AM, Jon Hough <[email protected]> wrote:
> I just ran a couple of tests with prim_alg and prim_alg2, and it seems
> prim_alg2 seems to fail for the following matrix:
>
> mat3 =: 7 7 $ _ _ _ _ 12 34 19, _ _ 30 _ 14 _ 22, _ 30 _ 18 10 _ _, _ _
> 18 _ 40 27 11, 12 14 10 40 _ _ _, 34 _ _ 27 _ _ _, 19 22 _ 11 _ _ _
>
>
>
> It's result:
>
> ┌───┬───┬───┬───┬───┬───┐
>
> │0 4│1 2│1 1│2 3│4 6│4 5│
>
> └───┴───┴───┴───┴───┴───┘
>
>
> i.e. it contains the impossible edge 1 1
>
>
> prim_alg gives the result:
>
> ┌───┬───┬───┬───┬───┬───┐
>
> │0 4│4 2│4 1│2 3│3 6│3 5│
>
> └───┴───┴───┴───┴───┴───┘
>
>
>
>
>
> > From: [email protected]
> > Date: Fri, 24 Oct 2014 12:45:39 -0400
> > To: [email protected]
> > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's Algorithm
> >
> > On a tangentially related note:
> >
> > It's usually worthwhile first coming up with something that works and
> then
> > (if performance is an issue) addressing the problems.
> >
> > It's somewhat frightening, sometimes, how bad problems can be (and
> > honestly, in this example of minimum spanning tree code the problems are
> > not all that bad). But not having anything that works at all is generally
> > worse than something that works in a flawed manner.
> >
> > That said, the existence of flaws that you have created tends to impose
> an
> > obligation on you (to fix them), and that can be something of a struggle
> > sometimes.
> >
> > Thanks,
> >
> > --
> > Raul
> >
> >
> >
> > On Fri, Oct 24, 2014 at 12:34 PM, Jon Hough <[email protected]> wrote:
> >
> > > Joe Bogner said:
> > > "1. It's imperative style and doesn't feel like idiomatic J. I wonder
> > > ifit's possible to use more of an array style (no loops)"
> > > Yes, I realized that. I'm still not great at thinking only in arrays.
> But,
> > > specifically for this problem, I'm not sure it is possible to do it
> without
> > > an explicit for or while loop.
> > > As in your link:
> > > http://www.jsoftware.com/jwiki/Essays/Minimal%20Spanning%20Tree
> > > even Roger Hui's minimal spanning tree needed a for loop.
> > >
> > > > From: [email protected]
> > > > To: [email protected]
> > > > Date: Fri, 24 Oct 2014 17:29:17 +0100
> > > > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's
> Algorithm
> > > >
> > > > I just realized
> > > >
> > > > (i. <./) ,|:_ list} list {"1 mat
> > > > does the removal. You put it much more tersely than I did.
> > > > > From: [email protected]
> > > > > To: [email protected]
> > > > > Date: Fri, 24 Oct 2014 17:27:50 +0100
> > > > > Subject: Re: [Jprogramming] Minimum Spanning Tree, J and Prim's
> > > Algorithm
> > > > >
> > > > > 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
> > > >
> > > >
> ----------------------------------------------------------------------
> > > > 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
