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
