gt.c

   1 #define _GNU_SOURCE
   2 #include <getopt.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include "lib/dbg.h"
   6 #include "graph/adj.h"
   7 #include "graph/dfs.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[] = {
  71     {"dfs", no_argument, 0, 'd'},
  72     {"bfs", no_argument, 0, 'b'},
  73     {0, 0, 0, 0}
  74   };
  75
  76   while ((c = getopt_long (argc, argv, "db", long_opts, NULL)) != -1)
  77     {
  78       switch (c)
  79         {
  80         case 'd':
  81           a = ALGO_DFS;
  82           break;
  83         case 'b':
  84           a = ALGO_BFS;
  85           break;
  86         default:
  87           fprintf (stderr, "Usage: %s [--dfs|--bfs] <nv> [u1 v1 ...]\n", argv[0]);
  88           exit (EXIT_FAILURE);
  89         }
  90     }
  91
  92   if (a == ALGO_NONE)
  93     fatal ("no algorithm specified");
  94
  95   if (optind >= argc)
  96     fatal ("missing number of vertices");
  97
  98   nv = (unsigned int) atoi (argv[optind]);
  99   if (!(g = new_graph (nv)))
 100     fatal ("new_graph ()");
 101
 102   for (i = optind + 1; i < argc - 1; i += 2)
 103     {
 104       u = (unsigned int) atoi (argv[i]);
 105       v = (unsigned int) atoi (argv[i + 1]);
 106       if (add_edge (g, u, v))
 107         fatal ("add_edge ()");
 108     }
 109
 110   if (a == ALGO_DFS)
 111     dt = dfs (g);
 112   else
 113     dt = bfs (g);
 114
 115   if (!dt)
 116     fatal ("algorithm failed");
 117
 118   print_dot_graph (g, "g");
 119   printf ("\n");
 120   print_dot_digraph (dt, "dt");
 121
 122   free_graph (g);
 123   free_graph (dt);
 124
 125   return 0;
 126 }