#include "dbg.h"
#include "graph/adj.h"
#include "graph/pr.h"

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

struct v_state
{
  enum color c;
};

static __inline__ unsigned int
v_idx (struct graph *g, struct vertex *v)
{
  return (unsigned int)(v - g->v);
}

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

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

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

      if (ns->c == WHITE)
        {
          if (new_arc (dt, ri, ni))
            fatal ("new_arc ()");
          dfs_ (g, dt, vs, ni);
        }

      e = e->next;
    }

  rs->c = BLUE;
}

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

  if (!(dt = new_graph (g->nv)))
    fatal ("new_graph ()");

  if (!(vs = calloc (g->nv, sizeof *vs)))
    fatal ("calloc ()");

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

  free (vs);
  return dt;
}

static struct graph *
create_example (int argc, char **argv)
{
  struct graph *g;
  unsigned int nv, u, v;
  int i;

  if (argc < 2)
    {
      fprintf (stderr, "Usage: %s <num_vertices> [u1 v1 u2 v2 ...]\n", argv[0]);
      exit (EXIT_FAILURE);
    }

  nv = (unsigned int) atoi (argv[1]);
  if (!(g = new_graph (nv)))
    fatal ("new_graph ()");

  /* parse edges in pairs */
  for (i = 2; i < argc - 1; i += 2)
    {
      u = (unsigned int) atoi (argv[i]);
      v = (unsigned int) atoi (argv[i + 1]);
      if (new_edge (g, u, v))
        fatal ("new_edge ()");
    }

  return g;
}

int
main (int argc, char **argv)
{
  struct graph *g, *dt;
  unsigned int i;
  struct edge *e;

  g = create_example (argc, argv);

  if (!(dt = dfs (g)))
    fatal ("dfs ()");

  printf ("graph g:\n");
  for (i = 0; i < g->nv; ++i)
    {
      for (e = g->v[i].adj; e; e = e->next)
        {
          pr_edge (i, v_idx (g, e->to));
          putchar (' ');
        }
      if (g->v[i].adj)
        putchar ('\n');
    }

  printf ("\ndfs tree dt:\n");
  for (i = 0; i < dt->nv; ++i)
    {
      for (e = dt->v[i].adj; e; e = e->next)
        {
          pr_arc (i, v_idx (dt, e->to));
          putchar (' ');
        }
      if (dt->v[i].adj)
        putchar ('\n');
    }

  return 0;
}