gt.c

   1 #include "graph/adj.h"
   2 #include "graph/bfs.h"
   3 #include "graph/dfs.h"
   4 #include "lib/dbg.h"
   5 #include <getopt.h>
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8
   9 enum algo
  10 {
  11   ALGO_NONE,
  12   ALGO_DFS,
  13   ALGO_BFS
  14 };
  15
  16 static void
  17 print_dot_graph (struct graph *g, const char *name)
  18 {
  19   unsigned int i;
  20   struct edge *e;
  21   unsigned int vi, vj;
  22
  23   printf ("graph %s {\n", name);
  24   for (i = 0; i < g->nv; ++i)
  25     {
  26       printf ("  %d;\n", i);
  27       for (e = g->v[i].adj; e; e = e->next)
  28         {
  29           vi = i;
  30           vj = vertex_id (g, e->to);
  31           if (vi <= vj)
  32             printf ("  %d -- %d;\n", vi, vj);
  33         }
  34     }
  35   printf ("}\n");
  36 }
  37
  38 static void
  39 print_dot_digraph (struct graph *g, const char *name)
  40 {
  41   unsigned int i;
  42   struct edge *e;
  43   unsigned int vi, vj;
  44
  45   printf ("digraph %s {\n", name);
  46   for (i = 0; i < g->nv; ++i)
  47     {
  48       printf ("  %d;\n", i);
  49       for (e = g->v[i].adj; e; e = e->next)
  50         {
  51           vi = i;
  52           vj = vertex_id (g, e->to);
  53           printf ("  %d -> %d;\n", vi, vj);
  54         }
  55     }
  56   printf ("}\n");
  57 }
  58
  59 int
  60 main (int argc, char **argv)
  61 {
  62   int c;
  63   enum algo a = ALGO_NONE;
  64   struct graph *g, *dt;
  65   unsigned int nv, u, v;
  66   int i;
  67
  68   static struct option long_opts[] = { { "dfs", no_argument, 0, 'd' },
  69                                        { "bfs", no_argument, 0, 'b' },
  70                                        { 0, 0, 0, 0 } };
  71
  72   while ((c = getopt_long (argc, argv, "db", long_opts, NULL)) != -1)
  73     {
  74       switch (c)
  75         {
  76         case 'd':
  77           a = ALGO_DFS;
  78           break;
  79         case 'b':
  80           a = ALGO_BFS;
  81           break;
  82         default:
  83           fprintf (stderr, "Usage: %s [--dfs|--bfs] <nv> [u1 v1 ...]\n",
  84                    argv[0]);
  85           exit (EXIT_FAILURE);
  86         }
  87     }
  88
  89   if (a == ALGO_NONE)
  90     fatal ("no algorithm specified");
  91
  92   if (optind >= argc)
  93     fatal ("missing number of vertices");
  94
  95   nv = (unsigned int)atoi (argv[optind]);
  96   if (!(g = new_graph (nv)))
  97     fatal ("new_graph ()");
  98
  99   for (i = optind + 1; i < argc - 1; i += 2)
 100     {
 101       u = (unsigned int)atoi (argv[i]);
 102       v = (unsigned int)atoi (argv[i + 1]);
 103       if (add_edge (g, u, v))
 104         fatal ("add_edge ()");
 105     }
 106
 107   if (a == ALGO_DFS)
 108     dt = dfs (g);
 109   else
 110     dt = bfs (g);
 111
 112   if (!dt)
 113     fatal ("algorithm failed");
 114
 115   print_dot_graph (g, "g");
 116   printf ("\n");
 117   print_dot_digraph (dt, "dt");
 118
 119   free_graph (g);
 120   free_graph (dt);
 121
 122   return 0;
 123 }