graph/dfs.c

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