Boruvka's Minimum Spanning Tree algorithm
[1/5] from: lmecir::mbox::vol::cz at: 13-May-2004 23:54
I posted a Rebol implementation of Boruvka's classic Minimum Spanning
Tree algoritm to http://www.compkarori.com/vanilla/display/Graph
Any questions, comments, corrections and improvements welcome.
-L
[2/5] from: lmecir:mbox:vol:cz at: 16-May-2004 15:39
Ladislav Mečíř napsal(a):
>I posted a Rebol implementation of Boruvka's classic Minimum Spanning
>Tree algoritm to http://www.compkarori.com/vanilla/display/Graph
>
>Any questions, comments, corrections and improvements welcome.
>
>-L
>
FYI, in http://www.library.cornell.edu/nr/bookcpdf/c8-6.pdf I found a
function Eclass. The algorithm of it is attributed to D.E. Knuth. I
found out, that the Eclass function if MUCH slower (for large number of
nodes), than the combination of the Components and Adjacency functions
you can find above.
-L
[3/5] from: reblist:codeconscious at: 19-May-2004 21:04
Hi Ladislav,
I like your choice of edge representation - flexible. Haven't had a lot of
time to play with it, but I'm keeping it in the back of my mind as something
potentially quite useful.
Thanks for posting it,
Brett.
[4/5] from: lmecir:mbox:vol:cz at: 19-May-2004 18:39
Brett Handley napsal(a):
>Hi Ladislav,
>
>I like your choice of edge representation - flexible.
>
....snip...
yes, that was my primary goal, but for this algorithm (and maybe for
some other), the adjacency structure used instead of a block of graph
edges might lead to a simpler formulation. (But there would be a
problem, where to store edge weights - any idea?)
-L
[5/5] from: reblist:codeconscious at: 20-May-2004 21:47
Can't really suggest anything unfortunately . I find the process of choosing
REBOL representations for my informaion always illuminating and always
tough.
Regards,
Brett.