graph/dfs.c

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