#include "graph/dfs.h"
#include <stdlib.h>

enum color
{
  WHITE = 0,
  RED,
  BLUE
};

struct state
{
  enum color c;
};

static int
dfs_ (struct graph *g, struct graph *dt, struct state *vs, unsigned int ri)
{
  struct vertex *r, *n;
  struct state *rs, *ns;
  struct edge *e;
  unsigned int ni;
  int err;

  (rs = &vs[ri])->c = RED;
  r = &g->v[ri];
  e = r->adj;

  while (e && (n = e->to))
    {
      ni = vertex_id (g, n);
      ns = &vs[ni];

      if (ns->c == WHITE)
        {
          if ((err = add_arc (dt, ri, ni)))
            return err;

          if ((err = dfs_ (g, dt, vs, ni)))
            return err;
        }

      e = e->next;
    }

  rs->c = BLUE;

  return 0;
}

struct graph *
dfs (struct graph *g)
{
  struct graph *dt;
  struct state *vs;
  unsigned int vi;

  if (!(dt = new_graph (g->nv)))
    goto err_new_graph;

  if (!(vs = calloc (g->nv, sizeof *vs)))
    goto err_calloc;

  for (vi = 0; vi < g->nv; ++vi)
    if (vs[vi].c == WHITE)
      if (dfs_ (g, dt, vs, vi))
        goto err_dfs_;

  free (vs);
  return dt;

err_dfs_:
  free (vs);
err_calloc:
  free_graph (dt);
err_new_graph:
  return NULL;
}