duane@anasazi.UUCP (Duane Morse) (08/08/85)
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