graph/bfs.c

   1 #include "graph/bfs.h"
   2 #include "graph/search.h"
   3 #include <errno.h>
   4 #include <stdlib.h>
   5
   6 static int
   7 bfs_ (struct graph *g, struct graph *bt, struct state *vs, unsigned int ri)
   8 {
   9   struct squeue sq;
  10   struct vertex *r, *n;
  11   struct state *rs, *ns;
  12   struct edge *e;
  13   unsigned int ni;
  14   int err;
  15
  16   if (!(sq.q = calloc (g->nv, sizeof *sq.q)))
  17     return -errno;
  18
  19   sq.f = sq.l = sq.q;
  20   *sq.f = &g->v[ri];
  21   vs[ri].c = RED;
  22
  23   while (sq.f <= sq.l)
  24     {
  25       r = *sq.f;
  26       ri = vertex_id (g, r);
  27       rs = &vs[ri];
  28       e = r->adj;
  29
  30       while (e && (n = e->to))
  31         {
  32           ni = vertex_id (g, n);
  33           ns = &vs[ni];
  34
  35           if (ns->c == WHITE)
  36             {
  37               ns->c = RED;
  38
  39               if ((err = add_arc (bt, ri, ni)))
  40                 {
  41                   free (sq.q);
  42                   return err;
  43                 }
  44
  45               *(++sq.l) = n;
  46             }
  47
  48           e = e->next;
  49         }
  50
  51       rs->c = BLUE;
  52       ++sq.f;
  53     }
  54
  55   free (sq.q);
  56   return 0;
  57 }
  58
  59 struct graph *
  60 bfs (struct graph *g)
  61 {
  62   struct graph *bt;
  63   struct state *vs;
  64   unsigned int vi;
  65
  66   if (!(bt = new_graph (g->nv)))
  67     goto err_new_graph;
  68
  69   if (!(vs = calloc (g->nv, sizeof *vs)))
  70     goto err_calloc;
  71
  72   for (vi = 0; vi < g->nv; ++vi)
  73     if (vs[vi].c == WHITE)
  74       if (bfs_ (g, bt, vs, vi))
  75         goto err_bfs_;
  76
  77   free (vs);
  78   return bt;
  79
  80 err_bfs_:
  81   free (vs);
  82 err_calloc:
  83   free_graph (bt);
  84 err_new_graph:
  85   return NULL;
  86 }