dfs.c

   1 #include "dbg.h"
   2 #include "graph/adj.h"
   3 #include "graph/pr.h"
   4
   5 enum color
   6 {
   7   WHITE = 0,
   8   RED,
   9   BLUE
  10 };
  11
  12 struct v_state
  13 {
  14   enum color c;
  15 };
  16
  17 static __inline__ unsigned int
  18 v_idx (struct graph *g, struct vertex *v)
  19 {
  20   return (unsigned int)(v - g->v);
  21 }
  22
  23 static void
  24 dfs_ (struct graph *g, struct graph *dt, struct v_state *vs, unsigned int ri)
  25 {
  26   struct vertex *r, *n;
  27   struct v_state *rs, *ns;
  28   struct edge *e;
  29   unsigned int ni;
  30
  31   (rs = &vs[ri])->c = RED;
  32   r = &g->v[ri];
  33   e = r->adj;
  34
  35   while (e && (n = e->to))
  36     {
  37       ni = v_idx (g, n);
  38       ns = &vs[ni];
  39
  40       if (ns->c == WHITE)
  41         {
  42           if (new_arc (dt, ri, ni))
  43             fatal ("new_arc ()");
  44           dfs_ (g, dt, vs, ni);
  45         }
  46
  47       e = e->next;
  48     }
  49
  50   rs->c = BLUE;
  51 }
  52
  53 static struct graph *
  54 dfs (struct graph *g)
  55 {
  56   struct graph *dt;
  57   struct v_state *vs;
  58   unsigned int vi;
  59
  60   if (!(dt = new_graph (g->nv)))
  61     fatal ("new_graph ()");
  62
  63   if (!(vs = calloc (g->nv, sizeof *vs)))
  64     fatal ("calloc ()");
  65
  66   for (vi = 0; vi < g->nv; ++vi)
  67     {
  68       if (vs[vi].c == WHITE)
  69         dfs_ (g, dt, vs, vi);
  70     }
  71
  72   free (vs);
  73   return dt;
  74 }
  75
  76 static struct graph *
  77 create_example (int argc, char **argv)
  78 {
  79   struct graph *g;
  80   unsigned int nv, u, v;
  81   int i;
  82
  83   if (argc < 2)
  84     {
  85       fprintf (stderr, "Usage: %s <num_vertices> [u1 v1 u2 v2 ...]\n", argv[0]);
  86       exit (EXIT_FAILURE);
  87     }
  88
  89   nv = (unsigned int) atoi (argv[1]);
  90   if (!(g = new_graph (nv)))
  91     fatal ("new_graph ()");
  92
  93   /* parse edges in pairs */
  94   for (i = 2; i < argc - 1; i += 2)
  95     {
  96       u = (unsigned int) atoi (argv[i]);
  97       v = (unsigned int) atoi (argv[i + 1]);
  98       if (new_edge (g, u, v))
  99         fatal ("new_edge ()");
 100     }
 101
 102   return g;
 103 }
 104
 105 int
 106 main (int argc, char **argv)
 107 {
 108   struct graph *g, *dt;
 109   unsigned int i;
 110   struct edge *e;
 111
 112   g = create_example (argc, argv);
 113
 114   if (!(dt = dfs (g)))
 115     fatal ("dfs ()");
 116
 117   printf ("graph g:\n");
 118   for (i = 0; i < g->nv; ++i)
 119     {
 120       for (e = g->v[i].adj; e; e = e->next)
 121         {
 122           pr_edge (i, v_idx (g, e->to));
 123           putchar (' ');
 124         }
 125       if (g->v[i].adj)
 126         putchar ('\n');
 127     }
 128
 129   printf ("\ndfs tree dt:\n");
 130   for (i = 0; i < dt->nv; ++i)
 131     {
 132       for (e = dt->v[i].adj; e; e = e->next)
 133         {
 134           pr_arc (i, v_idx (dt, e->to));
 135           putchar (' ');
 136         }
 137       if (dt->v[i].adj)
 138         putchar ('\n');
 139     }
 140
 141   return 0;
 142 }