bc_spanning.c

Go to the documentation of this file.

#include "bc_spanning.h"

#if 0
int DPspanningMain (int ac,
                    char **av)
{
  double wt;
  int rval = 0;
  int i,
    ncount,
    ecount;
  int *elist = (int *) NULL;
  double *wlist = (double *) NULL;
  int *tlist = (int *) NULL;

  if (ac < 2)
  {
    DPspanningUsage (*av);
    return 1;
  }

  rval = getprob (av[1], &ncount, &ecount, &elist, &wlist);
  if (rval)
  {
    fprintf (stderr, "getprob failed\n");
    goto CLEANUP;
  }

  tlist = (int *) malloc ((ncount - 1) * sizeof (int));
  if (!tlist)
  {
    fprintf (stderr, "out of memory for tlist\n");
    rval = 1;
    goto CLEANUP;
  }

  rval = kruskal_spanningtree (ncount, ecount, elist, wlist, tlist, 0);
  if (rval)
  {
    fprintf (stderr, "kruskal_spanningtree failed\n");
    goto CLEANUP;
  }

  wt = 0.0;
  for (i = 0; i < ncount - 1; i++)
    wt += wlist[tlist[i]];

  printf ("Tree Weight: %f\n", wt);
  fflush (stdout);

CLEANUP:

  if (tlist)
    free (tlist);
  if (elist)
    free (elist);
  if (wlist)
    free (wlist);
  return rval;
}
#endif

int biased_spanningtree (int ncount,
                         int ecount,
                         int *elist,
                         double *wlist,
                         int *tlist,
                         void *function_data)
{
  DPedgeSet_t *eedges = (DPedgeSet_t *) function_data;
  int i,
    k,
    tcount = 0;
  DPspanningEdge *e;
  int *perm = (int *) NULL;
  DPspanningNode *nlist = (DPspanningNode *) NULL;
  DPspanningEdge *edglist = (DPspanningEdge *) NULL;
  int rval = 0;
  int nsedges = 0;
  int *nodemarks = 0;

  rval = buildgraph (ecount, elist, wlist, &edglist);
  function_data = 0;
  if (rval)
  {
    fprintf (stderr, "buildgraph failed\n");
    goto CLEANUP;
  }

  perm = (int *) malloc (ecount * sizeof (int));
  nodemarks = (int *) malloc (ncount * sizeof (int));
  if (!perm || !nodemarks)
  {
    fprintf (stderr, "out of memory for perm\n");
    rval = 1;
    goto CLEANUP;
  }
  memset (nodemarks, 0, sizeof (int) * ncount);
  for (i = 0; i < ecount; i++)
    perm[i] = i;

  /* here we put at the end some special edges */
  for (i = 0; i < eedges->nedges; i++)
  {
    nodemarks[eedges->edges[i * 2]] = 1;
    nodemarks[eedges->edges[i * 2 + 1]] = 1;
  }
  for (i = 1; i < ecount; i++)
  {
    if (nodemarks[edglist[perm[i]].ends[0]]
        || nodemarks[edglist[perm[i]].ends[1]])
    {
      SWAP (perm[i], perm[nsedges++], k);
    }
  }
  /* up to now the edges touching the 'marked' nodes are in the first 'nsedges' positions */

  qsort_DPspanningEdges (perm, edglist, nsedges, ecount - 1);
  qsort_DPspanningEdges (perm, edglist, 0, nsedges - 1);

  nlist = (DPspanningNode *) malloc (ncount * sizeof (DPspanningNode));
  if (!nlist)
  {
    fprintf (stderr, "out of memory for nlist\n");
    rval = 1;
    goto CLEANUP;
  }
  for (i = 0; i < ncount; i++)
  {
    makeset (&nlist[i]);
  }

  for (i = 0, k = ncount - 1; k > 0 && i < ecount; i++)
  {
    e = &edglist[perm[i]];
    if (find (&nlist[e->ends[0]]) != find (&nlist[e->ends[1]]))
    {
      slink (find (&nlist[e->ends[0]]), find (&nlist[e->ends[1]]));
      tlist[tcount++] = perm[i];
      k--;
    }
  }

  if (k)
  {
    fprintf (stderr, "Disconected graph\n");
    rval = 1;
  }

CLEANUP:

  if (perm)
    free (perm);
  if (nlist)
    free (nlist);
  if (edglist)
    free (edglist);
  if (nodemarks)
    free (nodemarks);

  return rval;
}

int kruskal_spanningtree (int ncount,
                          int ecount,
                          int *elist,
                          double *wlist,
                          int *tlist,
                          void *function_data)
{
  int i,
    k,
    tcount = 0;
  DPspanningEdge *e;
  int *perm = (int *) NULL;
  DPspanningNode *nlist = (DPspanningNode *) NULL;
  DPspanningEdge *edglist = (DPspanningEdge *) NULL;
  int rval = 0;

  rval = buildgraph (ecount, elist, wlist, &edglist);
  function_data = 0;
  if (rval)
  {
    fprintf (stderr, "buildgraph failed\n");
    goto CLEANUP;
  }

  perm = (int *) malloc (ecount * sizeof (int));
  if (!perm)
  {
    fprintf (stderr, "out of memory for perm\n");
    rval = 1;
    goto CLEANUP;
  }
  for (i = 0; i < ecount; i++)
    perm[i] = i;

  qsort_DPspanningEdges (perm, edglist, 0, ecount - 1);

  nlist = (DPspanningNode *) malloc (ncount * sizeof (DPspanningNode));
  if (!nlist)
  {
    fprintf (stderr, "out of memory for nlist\n");
    rval = 1;
    goto CLEANUP;
  }
  for (i = 0; i < ncount; i++)
  {
    makeset (&nlist[i]);
  }

  for (i = 0, k = ncount - 1; k > 0 && i < ecount; i++)
  {
    e = &edglist[perm[i]];
    if (find (&nlist[e->ends[0]]) != find (&nlist[e->ends[1]]))
    {
      slink (find (&nlist[e->ends[0]]), find (&nlist[e->ends[1]]));
      tlist[tcount++] = perm[i];
      k--;
    }
  }

  if (k)
  {
    fprintf (stderr, "Disconected graph\n");
    rval = 1;
  }

CLEANUP:

  if (perm)
    free (perm);
  if (nlist)
    free (nlist);
  if (edglist)
    free (edglist);

  return rval;
}

/* qsort from J. Bentley (unix review, march '92)  */

void qsort_DPspanningEdges (int *perm,
                            DPspanningEdge * elist,
                            int l,
                            int u)
{
  int i,
    j;
  int itemp;
  double t;

  if (l >= u)
    return;

  SWAP (perm[l], perm[(l + u) / 2], itemp);

  i = l;
  j = u + 1;
  t = elist[perm[l]].weight;

  while (1)
  {
    do
      i++;
    while (i <= u && elist[perm[i]].weight > t);
    do
      j--;
    while (elist[perm[j]].weight < t);
    if (j < i)
      break;
    SWAP (perm[i], perm[j], itemp);
  }
  SWAP (perm[l], perm[j], itemp);
  qsort_DPspanningEdges (perm, elist, l, j - 1);
  qsort_DPspanningEdges (perm, elist, i, u);
}

void printtree (int ncount,
                int *elist,
                int *tlist)
{
  int i,
    p;

  printf ("%d %d\n", ncount, ncount - 1);
  for (i = 0; i < ncount - 1; i++)
  {
    p = tlist[i];
    printf ("%d %d 1\n", elist[2 * p], elist[2 * p + 1]);
  }
}

int getprob (char *fname,
             int *p_ncount,
             int *p_ecount,
             int **p_elist,
             double **p_wlist)
{
  FILE *f = (FILE *) NULL;
  int i,
    end1,
    end2;
  double w;
  int rval = 0;
  int ncount,
    ecount;
  double *wlist = (double *) NULL;
  int *elist = (int *) NULL;

  if ((f = fopen (fname, "r")) == NULL)
  {
    fprintf (stderr, "Unable to open %s for input\n", fname);
    rval = 1;
    goto CLEANUP;
  }

  if (fscanf (f, "%d %d", &ncount, &ecount) != 2)
  {
    fprintf (stderr, "Input file %s has invalid format\n", fname);
    rval = 1;
    goto CLEANUP;
  }

  printf ("Nodes: %d  Edges: %d\n", ncount, ecount);
  fflush (stdout);

  elist = (int *) malloc (2 * ecount * sizeof (int));
  if (!elist)
  {
    fprintf (stderr, "out of memory for elist\n");
    rval = 1;
    goto CLEANUP;
  }

  wlist = (double *) malloc (ecount * sizeof (double));
  if (!wlist)
  {
    fprintf (stderr, "out of memory for wlist\n");
    rval = 1;
    goto CLEANUP;
  }

  for (i = 0; i < ecount; i++)
  {
    if (fscanf (f, "%d %d %lf", &end1, &end2, &w) != 3)
    {
      fprintf (stderr, "%s has invalid input format\n", fname);
      rval = 1;
      goto CLEANUP;
    }
    elist[2 * i] = end1;
    elist[2 * i + 1] = end2;
    wlist[i] = w;
  }

  *p_ncount = ncount;
  *p_ecount = ecount;
  *p_elist = elist;
  *p_wlist = wlist;

CLEANUP:

  if (f)
    fclose (f);
  return rval;
}


int buildgraph (int ecount,
                int *elist,
                double *wlist,
                DPspanningEdge ** p_edglist)
{
  DPspanningEdge *edglist = (DPspanningEdge *) NULL;
  int i,
    rval = 0;

  edglist = (DPspanningEdge *) malloc (ecount * sizeof (DPspanningEdge));
  if (!edglist)
  {
    fprintf (stderr, "out of memory for edglist\n");
    rval = 1;
    goto CLEANUP;
  }

  for (i = 0; i < ecount; i++)
  {
    edglist[i].ends[0] = elist[2 * i];
    edglist[i].ends[1] = elist[2 * i + 1];
    edglist[i].weight = wlist[i];
  }

  *p_edglist = edglist;

CLEANUP:

  return rval;
}

/* disjoint sets ala Tarjan (from Data Structures and Network Algorithms
   by Robert Tarjan) */

void makeset (DPspanningNode * v)
{
  v->setinfo.parent = v;
  v->setinfo.rank = 0;
}

DPspanningNode *find (DPspanningNode * v)
{
  DPspanningNode *p = v->setinfo.parent;

  return v == p ? v : (v->setinfo.parent = find (p));
}

DPspanningNode *slink (DPspanningNode * x,
                       DPspanningNode * y)
{
  DPspanningNode *t;
  if (x->setinfo.rank > y->setinfo.rank)
  {
    SWAP (x, y, t);
  }
  else if (x->setinfo.rank == y->setinfo.rank)
  {
    y->setinfo.rank++;
  }
  x->setinfo.parent = y;
  return y;
}

---