graph/prim.c

   1 #include "graph/prim.h"
   2 #include "graph/search.h"
   3 #include <errno.h>
   4 #include <stdlib.h>
   5
   6 /*
   7  * todo priority queue, currently its broken
   8  * */
   9
  10 static int
  11 prim_ (struct graph *g, struct graph *pt, struct state *vs, unsigned int ri,
  12        unsigned int (*w) (unsigned int, unsigned int))
  13 {
  14   struct squeue sq;
  15   struct vertex *r, *n;
  16   struct state *rs, *ns;
  17   struct edge *e;
  18   unsigned int ni;
  19   int err;
  20
  21   if (!(sq.q = calloc (g->nv, sizeof *sq.q)))
  22     return -errno;
  23
  24   sq.f = sq.l = sq.q;
  25   *sq.f = &g->v[ri];
  26   vs[ri].c = RED;
  27
  28   while (sq.f <= sq.l)
  29     {
  30       r = *sq.f;
  31       ri = vertex_id (g, r);
  32       rs = &vs[ri];
  33       e = r->adj;
  34
  35       while (e && (n = e->to))
  36         {
  37           ni = vertex_id (g, n);
  38           ns = &vs[ni];
  39
  40           switch (ns->c)
  41             {
  42             case WHITE:
  43               ns->c = RED;
  44
  45               if ((err = add_arc (pt, ri, ni)))
  46                 {
  47                   free (sq.q);
  48                   return err;
  49                 }
  50
  51               ns->w = w (ri, ni);
  52               ns->from = r;
  53
  54               *(++sq.l) = n;
  55               break;
  56
  57             case RED:
  58               if (ns->w < w (ri, ni))
  59                 break;
  60
  61               del_arc (pt, vertex_id (g, ns->from), ni);
  62
  63               if ((err = add_arc (pt, ri, ni)))
  64                 {
  65                   free (sq.q);
  66                   return err;
  67                 }
  68
  69               ns->w = w (ri, ni);
  70               ns->from = r;
  71
  72               break;
  73             }
  74
  75           e = e->next;
  76         }
  77
  78       rs->c = BLUE;
  79       ++sq.f;
  80     }
  81
  82   free (sq.q);
  83   return 0;
  84 }
  85
  86 struct graph *
  87 prim (struct graph *g, unsigned int (*w) (unsigned int, unsigned int))
  88 {
  89   struct graph *pt;
  90   struct state *vs;
  91   unsigned int vi;
  92
  93   if (!(pt = new_graph (g->nv)))
  94     goto err_new_graph;
  95
  96   if (!(vs = calloc (g->nv, sizeof *vs)))
  97     goto err_calloc;
  98
  99   for (vi = 0; vi < g->nv; ++vi)
 100     if (vs[vi].c == WHITE)
 101       if (prim_ (g, pt, vs, vi, w))
 102         goto err_prim_;
 103
 104   free (vs);
 105   return pt;
 106
 107 err_prim_:
 108   free (vs);
 109 err_calloc:
 110   free_graph (pt);
 111 err_new_graph:
 112   return NULL;
 113 }