add bfs

diff --git a/graph/bfs.c b/graph/bfs.c
new file mode 100644 (file)
index 0000000..f7cc002
--- /dev/null
+++ b/graph/bfs.c
@@ -0,0 +1,86 @@
+#include "graph/bfs.h"
+#include "graph/search.h"
+#include <errno.h>
+#include <stdlib.h>
+
+static int
+bfs_ (struct graph *g, struct graph *bt, struct state *vs, unsigned int ri)
+{
+  struct squeue sq;
+  struct vertex *r, *n;
+  struct state *rs, *ns;
+  struct edge *e;
+  unsigned int ni;
+  int err;
+
+  if (!(sq.q = calloc (g->nv, sizeof *sq.q)))
+    return -errno;
+
+  sq.f = sq.l = sq.q;
+  *sq.f = &g->v[ri];
+  vs[ri].c = RED;
+
+  while (sq.f <= sq.l)
+    {
+      r = *sq.f;
+      ri = vertex_id (g, r);
+      rs = &vs[ri];
+      e = r->adj;
+
+      while (e && (n = e->to))
+        {
+          ni = vertex_id (g, n);
+          ns = &vs[ni];
+
+          if (ns->c == WHITE)
+            {
+              ns->c = RED;
+
+              if ((err = add_arc (bt, ri, ni)))
+                {
+                  free (sq.q);
+                  return err;
+                }
+
+              *(++sq.l) = n;
+            }
+
+          e = e->next;
+        }
+
+      rs->c = BLUE;
+      ++sq.f;
+    }
+
+  free (sq.q);
+  return 0;
+}
+
+struct graph *
+bfs (struct graph *g)
+{
+  struct graph *bt;
+  struct state *vs;
+  unsigned int vi;
+
+  if (!(bt = new_graph (g->nv)))
+    goto err_new_graph;
+
+  if (!(vs = calloc (g->nv, sizeof *vs)))
+    goto err_calloc;
+
+  for (vi = 0; vi < g->nv; ++vi)
+    if (vs[vi].c == WHITE)
+      if (bfs_ (g, bt, vs, vi))
+        goto err_bfs_;
+
+  free (vs);
+  return bt;
+
+err_bfs_:
+  free (vs);
+err_calloc:
+  free_graph (bt);
+err_new_graph:
+  return NULL;
+}

diff --git a/graph/bfs.h b/graph/bfs.h
new file mode 100644 (file)
index 0000000..15baa36
--- /dev/null
+++ b/graph/bfs.h
@@ -0,0 +1,8 @@
+#ifndef BFS_H
+#define BFS_H
+
+#include "graph/adj.h"
+
+struct graph *bfs (struct graph *g);
+
+#endif /* BFS_H  */

diff --git a/graph/dfs.c b/graph/dfs.c
index 72b05bbeb2f08683e4abab24f52a4f4edd2d09fe..e819f46ff263b92d32ce8521348b884e7e1a1551 100644 (file)
--- a/graph/dfs.c
+++ b/graph/dfs.c
@@ -1,18 +1,7 @@
 #include "graph/dfs.h"
+#include "graph/search.h"
 #include <stdlib.h>
 
-enum color
-{
-  WHITE = 0,
-  RED,
-  BLUE
-};
-
-struct state
-{
-  enum color c;
-};
-
 static int
 dfs_ (struct graph *g, struct graph *dt, struct state *vs, unsigned int ri)
 {

diff --git a/graph/search.h b/graph/search.h
new file mode 100644 (file)
index 0000000..738493d
--- /dev/null
+++ b/graph/search.h
@@ -0,0 +1,25 @@
+#ifndef SEARCH_H
+#define SEARCH_H
+
+#include "graph/adj.h"
+
+enum color
+{
+  WHITE = 0,
+  RED,
+  BLUE
+};
+
+struct state
+{
+  enum color c;
+};
+
+struct squeue
+{
+  struct vertex **q; /* queue */
+  struct vertex **f; /* first */
+  struct vertex **l; /* last */
+};
+
+#endif /* SEARCH_H  */

diff --git a/gt.c b/gt.c
index a3c112a21e9517a2853bf42bd05bb12554a73c96..e16d9432449533572f409fdcd32080a915572e1e 100644 (file)
--- a/gt.c
+++ b/gt.c
@@ -1,13 +1,11 @@
-#define _GNU_SOURCE
 #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>
 
-#define bfs dfs /* stub until tomorrow */
-
 enum algo
 {
   ALGO_NONE,