#include "graph/adj.h"
#include "graph/bfs.h"
#include "graph/dfs.h"
#include "lib/dbg.h"
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>

enum algo
{
  ALGO_NONE,
  ALGO_DFS,
  ALGO_BFS
};

static void
print_dot_graph (struct graph *g, const char *name)
{
  unsigned int i;
  struct edge *e;
  unsigned int vi, vj;

  printf ("graph %s {\n", name);
  for (i = 0; i < g->nv; ++i)
    {
      printf ("  %d;\n", i);
      for (e = g->v[i].adj; e; e = e->next)
        {
          vi = i;
          vj = vertex_id (g, e->to);
          if (vi <= vj)
            printf ("  %d -- %d;\n", vi, vj);
        }
    }
  printf ("}\n");
}

static void
print_dot_digraph (struct graph *g, const char *name)
{
  unsigned int i;
  struct edge *e;
  unsigned int vi, vj;

  printf ("digraph %s {\n", name);
  for (i = 0; i < g->nv; ++i)
    {
      printf ("  %d;\n", i);
      for (e = g->v[i].adj; e; e = e->next)
        {
          vi = i;
          vj = vertex_id (g, e->to);
          printf ("  %d -> %d;\n", vi, vj);
        }
    }
  printf ("}\n");
}

int
main (int argc, char **argv)
{
  int c;
  enum algo a = ALGO_NONE;
  struct graph *g, *dt;
  unsigned int nv, u, v;
  int i;

  static struct option long_opts[] = { { "dfs", no_argument, 0, 'd' },
                                       { "bfs", no_argument, 0, 'b' },
                                       { 0, 0, 0, 0 } };

  while ((c = getopt_long (argc, argv, "db", long_opts, NULL)) != -1)
    {
      switch (c)
        {
        case 'd':
          a = ALGO_DFS;
          break;
        case 'b':
          a = ALGO_BFS;
          break;
        default:
          fprintf (stderr, "Usage: %s [--dfs|--bfs] <nv> [u1 v1 ...]\n",
                   argv[0]);
          exit (EXIT_FAILURE);
        }
    }

  if (a == ALGO_NONE)
    fatal ("no algorithm specified");

  if (optind >= argc)
    fatal ("missing number of vertices");

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

  for (i = optind + 1; i < argc - 1; i += 2)
    {
      u = (unsigned int)atoi (argv[i]);
      v = (unsigned int)atoi (argv[i + 1]);
      if (add_edge (g, u, v))
        fatal ("add_edge ()");
    }

  if (a == ALGO_DFS)
    dt = dfs (g);
  else
    dt = bfs (g);

  if (!dt)
    fatal ("algorithm failed");

  print_dot_graph (g, "g");
  printf ("\n");
  print_dot_digraph (dt, "dt");

  free_graph (g);
  free_graph (dt);

  return 0;
}