Eesuk Chung published a very exciting algorithm in
the Minimal Spanning Tree essay, based on (min,max)-algebra (MMA),
in addition to Roger Hui's initial Kruskal algorithm
http://www.jsoftware.com/jwiki/Essays/Minimal_Spanning_Tree
It's beautiful and the simplest MST algorithm I've seen.
Is there more cool stuff where it was coming from?
I wasn't able to find any discussion of MMA on the web about it.
or in textbooks, e.g. Introduction to Algorithms.
values x in [0,_]. <. and >. are symmetrical, unlike add and multiply.
<. has unity at _ and zero at 0: x=_<.x, 0=0<.x
>. has unity at 0 and zero at _: x=0>.x, _=_>.x
Here's a tacitised form of Eesuk's MMA transitive closure
and a transform to order by weight as returned by `mst`.
mai=: <. _ 0 {~ [EMAIL PROTECTED]@# NB. add identity matrix, min is add
mx =: <./ . >. NB. matrix product in MMA
mxc=: = mai mx^:_ ] NB. transitive closure of product
ndx=: $ #: I.@, NB. boolean matrix indices
utr=: #~ </"1 NB. upper triangular filter
mxn=: utr @ ndx @ mxc NB. MMA transitive closure indices
mxs=: (] /: {::~) mxn NB. sorted by weight
((# mst efm) -: mxs) m
1
Which is symmetrically transformed to maximum spanning tree
nai=: >. 0 _ {~ [EMAIL PROTECTED]@#
nx =: >./ . <.
nxc=: = nai nx^:_ ]
nxn=: utr @ ndx @ nxc
nxs=: (] \: {::~) nxn
((# mst efm) -: nxs@([EMAIL PROTECTED])@(100-])) m
1
mxs f.
(] /: {::~) (#~ </"1)@($ #: I.@,)@(= (<. _ 0 {~ [EMAIL PROTECTED]@#) <./ .>.^:_
])
nxs f.
(] \: {::~) (#~ </"1)@($ #: I.@,)@(= (>. 0 _ {~ [EMAIL PROTECTED]@#) >./ .<.^:_
])
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
