[net.sources] Minimum Weight Spanning Tree subroutine

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