Minimum Weight Spanning Tree subroutine
Duane Morse
duane at anasazi.UUCP
Fri Aug 9 00:15:13 AEST 1985
In designing computer networks, I've frequently used the following
subroutine to do part of the work. It lays out a Minimum Weight
Spanning Tree given a set of points and an external cost function.
It puts the resulting tree in the vector of that name. I wrote the
routine in Fortran 5 or 6 years ago and rewrote it in C early
this year and used it in network layout programs.
-----------------------Software follows, then my signature -------------
/*TITLE mwst.c - minimum weight spanning tree routine 1/17/85 16:55:16 */
static char *version = "@(#)mwst.c 1.5 1/17/85 16:55:16";
/*
** void mwst(tree, isopt, npts)
**
** This routine constructs a minimum weight spanning tree in
** vector tree. It calls external function "cost" to compute the cost
** of linking two points.
**
** The algorithm is based on "Shortest Connection Networks and
** Some Generalizations" by R. C. Prim, BSTJ (11/57), pp 1389-1401.
**
** Parameters:
** tree = points to vector of shorts which indicates the resulting
** links.
** isopt = vector of indices of isolated points to link.
** npts = number of elements in isopt.
**
** Returns:
** Nothing.
**
** Side effects:
** Upon return, tree[i] == j => i links to j except that
** tree[isopt[0]] is not used.
*/
#include <stdio.h>
static float *cst; /* Costs go here */
extern float cost();
extern char *malloc();
extern void free();
/*PAGE*/
void mwst(tree, isopt, npts)
short tree[];
short isopt[];
short npts;
{
register short i, j, *iptr, lastpt;
short isomin, iold, niter;
char *s;
float cstmin, d, z;
if (npts == 1)
return;
if (npts < 1) {
fprintf(stderr, "mwst called with %d points to link", npts);
exit(-1);
}
/*
** Find the maximum index in isopt and allocate storage for cst.
*/
j = isopt[0];
iptr = isopt + 1;
for (i = npts - 1; i-- > 0; iptr++)
if (*iptr > j)
j = *iptr;
j = (j + 1) * sizeof(z);
if ((s = malloc(j)) == NULL) {
fprintf(stderr, "malloc failed\n");
exit(-1);
}
cst = (float *) s;
/*
** Initialize the costs to max.
*/
iptr = isopt;
for (i = 0; i++ < npts; ) {
if ((j = *iptr++) < 0) {
fprintf(stderr, "mwst called with bad index %d in isopt", j);
exit(-1);
}
cst[j] = 1E20;
}
/* Establish the first point of the tree */
lastpt = isopt[0];
/*PAGE*/
/*
** At the beginning of the outer loop, there are niter-1 isolated
** points left, isopt[1] through isopt[niter], and cst contains
** the minimum costs to link those points to the current tree.
**
** In the inner loop, a check is made to see if the addition of
** that last point (lastpt) to the tree reduces the minimum cost
** of the next isolated point to the tree; then this minimum cost
** is compared to the current minumum cost link. When the inner
** loop is done, isomin is the next closest point to the tree -- it
** becomes lastpt. isopt[iold] is reset to isopt[niter] so that
** isopt[1] through isopt[niter] will always contain only
** isolated points.
**
** In other words, the current tree is always connected to its
** nearest neighbor.
*/
for (niter = npts - 1; niter; ) {
/* Initialize the minimum cost to max */
cstmin = 1E20;
for (i = 1; i <= niter; i++) {
j = isopt[i];
d = cost(lastpt, j);
z = cst[j];
/*
** Compare j's cost from the tree to its cost from lastpt.
** If it's as close or closer now, change the link.
*/
if (d <= z) {
cst[j] = d;
z = d;
tree[j] = lastpt;
}
/*
** If the new minimum cost has changed, store it.
*/
if (z < cstmin) {
cstmin = z;
isomin = j;
iold = i;
}
}
/*
** Add isomin to the tree.
*/
lastpt = isomin;
isopt[iold] = isopt[niter--];
}
free(cst);
}
--
Duane Morse ...!noao!terak!anasazi!duane
(602) 275-0302
More information about the Comp.sources.unix
mailing list