add gt.c

diff --git a/.gitignore b/.gitignore
index ff3c331256392eaeeb6e7d12f0a4b81c0b4eabb3..429fdbe7d1967cd90c785dd4e6ce4c77d3aa8a0c 100644 (file)
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,3 @@
 .*.swp
 *.o
 .*.swp
 *.o

-dfs
+gt

diff --git a/Makefile b/Makefile
index 90d603bb866f89f7fb17945852e46dbbbdc8adc9..1af89841bce2fada15a6f3a7f479c66f01692130 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -13,8 +13,8 @@ CFLAGS := -I. \
           -Wdouble-promotion \
           -Wno-variadic-macros
 
           -Wdouble-promotion \
           -Wno-variadic-macros
 

-objs := dfs.o graph/adj.o graph/pr.o
-bin := dfs
+objs := gt.o graph/adj.o graph/dfs.o graph/pr.o
+bin := gt

 
 all : $(bin)
 
 
 all : $(bin)
 

diff --git a/graph/adj.c b/graph/adj.c
index dfcf0363dcf44da5290bf299dd2d20a1f0c3c9b7..fbad922f1a173dbc52eabbb7e1e91d54fe2f3aa9 100644 (file)
--- a/graph/adj.c
+++ b/graph/adj.c
@@ -127,6 +127,9 @@ free_graph (struct graph *g)
   struct vertex *v;
   unsigned int i;
 
   struct vertex *v;
   unsigned int i;
 

+  if (!g)
+    return;
+

   for (i = 0; i < g->nv; ++i)
     {
       v = &g->v[i];
   for (i = 0; i < g->nv; ++i)
     {
       v = &g->v[i];

diff --git a/gt.c b/gt.c
new file mode 100644 (file)
index 0000000..e9247e4
--- /dev/null
+++ b/gt.c
@@ -0,0 +1,126 @@
+#define _GNU_SOURCE
+#include <getopt.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "dbg.h"
+#include "graph/adj.h"
+#include "graph/dfs.h"
+
+#define bfs dfs /* stub until tomorrow */
+
+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;
+}