gt.c

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