dfs

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

+dfs

diff --git a/Makefile b/Makefile
new file mode 100644 (file)
index 0000000..90d603b
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,27 @@
+CC := gcc
+CFLAGS := -I. \
+          -std=gnu90 \
+          -g \
+          -pedantic \
+          -pedantic-errors \
+          -Wall \
+          -Wextra \
+          -Wconversion \
+          -Wstrict-prototypes \
+          -Wshadow \
+          -Wundef \
+          -Wdouble-promotion \
+          -Wno-variadic-macros
+
+objs := dfs.o graph/adj.o graph/pr.o
+bin := dfs
+
+all : $(bin)
+
+clean :
+       rm -f $(bin) $(objs)
+
+.PHONY : all clean
+
+$(bin) : $(objs)
+       $(CC) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@

diff --git a/dbg.h b/dbg.h
new file mode 100644 (file)
index 0000000..422c681
--- /dev/null
+++ b/dbg.h
@@ -0,0 +1,20 @@
+#ifndef DBG_H
+#define DBG_H
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define dbg(...) fprintf (stderr, __VA_ARGS__)
+
+#define fatal(x)                                                              \
+  do                                                                          \
+    {                                                                         \
+      fprintf (stderr, "(%s:%d) %s () failed: %s errno: %s\n", __FILE__,      \
+               __LINE__, __func__, x, strerror (errno));                      \
+      exit (EXIT_FAILURE);                                                    \
+    }                                                                         \
+  while (0)
+
+#endif /* DBG_H  */

diff --git a/dfs.c b/dfs.c
new file mode 100644 (file)
index 0000000..f189f43
--- /dev/null
+++ b/dfs.c
@@ -0,0 +1,142 @@
+#include "dbg.h"
+#include "graph/adj.h"
+#include "graph/pr.h"
+
+enum color
+{
+  WHITE = 0,
+  RED,
+  BLUE
+};
+
+struct v_state
+{
+  enum color c;
+};
+
+static __inline__ unsigned int
+v_idx (struct graph *g, struct vertex *v)
+{
+  return (unsigned int)(v - g->v);
+}
+
+static void
+dfs_ (struct graph *g, struct graph *dt, struct v_state *vs, unsigned int ri)
+{
+  struct vertex *r, *n;
+  struct v_state *rs, *ns;
+  struct edge *e;
+  unsigned int ni;
+
+  (rs = &vs[ri])->c = RED;
+  r = &g->v[ri];
+  e = r->adj;
+
+  while (e && (n = e->to))
+    {
+      ni = v_idx (g, n);
+      ns = &vs[ni];
+
+      if (ns->c == WHITE)
+        {
+          if (new_arc (dt, ri, ni))
+            fatal ("new_arc ()");
+          dfs_ (g, dt, vs, ni);
+        }
+
+      e = e->next;
+    }
+
+  rs->c = BLUE;
+}
+
+static struct graph *
+dfs (struct graph *g)
+{
+  struct graph *dt;
+  struct v_state *vs;
+  unsigned int vi;
+
+  if (!(dt = new_graph (g->nv)))
+    fatal ("new_graph ()");
+
+  if (!(vs = calloc (g->nv, sizeof *vs)))
+    fatal ("calloc ()");
+
+  for (vi = 0; vi < g->nv; ++vi)
+    {
+      if (vs[vi].c == WHITE)
+        dfs_ (g, dt, vs, vi);
+    }
+
+  free (vs);
+  return dt;
+}
+
+static struct graph *
+create_example (int argc, char **argv)
+{
+  struct graph *g;
+  unsigned int nv, u, v;
+  int i;
+
+  if (argc < 2)
+    {
+      fprintf (stderr, "Usage: %s <num_vertices> [u1 v1 u2 v2 ...]\n", argv[0]);
+      exit (EXIT_FAILURE);
+    }
+
+  nv = (unsigned int) atoi (argv[1]);
+  if (!(g = new_graph (nv)))
+    fatal ("new_graph ()");
+
+  /* parse edges in pairs */
+  for (i = 2; i < argc - 1; i += 2)
+    {
+      u = (unsigned int) atoi (argv[i]);
+      v = (unsigned int) atoi (argv[i + 1]);
+      if (new_edge (g, u, v))
+        fatal ("new_edge ()");
+    }
+
+  return g;
+}
+
+int
+main (int argc, char **argv)
+{
+  struct graph *g, *dt;
+  unsigned int i;
+  struct edge *e;
+
+  g = create_example (argc, argv);
+
+  if (!(dt = dfs (g)))
+    fatal ("dfs ()");
+
+  printf ("graph g:\n");
+  for (i = 0; i < g->nv; ++i)
+    {
+      for (e = g->v[i].adj; e; e = e->next)
+        {
+          pr_edge (i, v_idx (g, e->to));
+          putchar (' ');
+        }
+      if (g->v[i].adj)
+        putchar ('\n');
+    }
+
+  printf ("\ndfs tree dt:\n");
+  for (i = 0; i < dt->nv; ++i)
+    {
+      for (e = dt->v[i].adj; e; e = e->next)
+        {
+          pr_arc (i, v_idx (dt, e->to));
+          putchar (' ');
+        }
+      if (dt->v[i].adj)
+        putchar ('\n');
+    }
+
+  return 0;
+}

diff --git a/graph/adj.c b/graph/adj.c
index ec9cd0c8690d0d8acf381d05409a0f515160350c..e44f58344175baab1ddc32e21e19466aadde1283 100644 (file)
--- a/graph/adj.c
+++ b/graph/adj.c
@@ -1,14 +1,17 @@
-#include "adj.h"
-#include <stdlib.h>
+#include "graph/adj.h"

 #include <errno.h>
 #include <errno.h>

+#include <stdlib.h>

 
 struct graph *
 new_graph (unsigned int nv)
 {
 
 struct graph *
 new_graph (unsigned int nv)
 {

-  struct graph *g;  
+  struct graph *g;

 
   if (!nv)
 
   if (!nv)

-    return NULL;
+    {
+      errno = EINVAL;
+      return NULL;
+    }

 
   if (!(g = malloc (sizeof *g)))
     return NULL;
 
   if (!(g = malloc (sizeof *g)))
     return NULL;


@@ -30,10 +33,10 @@ new_arc (struct graph *g, unsigned int vi, unsigned int vj)
   struct edge *e;
 
   if (vi >= g->nv || vj >= g->nv)
   struct edge *e;
 
   if (vi >= g->nv || vj >= g->nv)

-    return -EINVAL;
+    return -(errno = EINVAL);

 
   if (!(e = malloc (sizeof *e)))
 
   if (!(e = malloc (sizeof *e)))

-    return -ENOMEM;
+    return -errno;

 
   e->to = &g->v[vj];
   e->next = g->v[vi].adj;
 
   e->to = &g->v[vj];
   e->next = g->v[vi].adj;


@@ -47,11 +50,14 @@ new_edge (struct graph *g, unsigned int vi, unsigned int vj)
 {
   int err;
 
 {
   int err;
 

+  if (vi == vj)
+    return -(errno = EINVAL);
+

   if ((err = new_arc (g, vi, vj)))
     return err;
 
   if ((err = new_arc (g, vi, vj)))
     return err;
 

-  if (vi != vj && (err = new_arc (g, vj, vi)))
-    return err; /* should delete the other arc but fuck it we ball */
+  if ((err = new_arc (g, vj, vi)))
+    return err;

 
   return 0;
 }
 
   return 0;
 }

diff --git a/graph/adj.h b/graph/adj.h
index 680d6b05d2f558b348efe296854af8b85b77c3dc..b0ec7233c41fc2b70825cbf7d4db014094405fce 100644 (file)
--- a/graph/adj.h
+++ b/graph/adj.h
@@ -24,10 +24,10 @@ struct graph
   unsigned int nv;
 };
 
   unsigned int nv;
 };
 

-struct graph *
-new_graph (unsigned int nv);
+struct graph *new_graph (unsigned int nv);

 
 

-int
-new_edge (struct graph *g, unsigned int vi, unsigned int vj);
+int new_arc (struct graph *g, unsigned int vi, unsigned int vj);
+
+int new_edge (struct graph *g, unsigned int vi, unsigned int vj);

 
 #endif /* GRAPH_H  */
 
 #endif /* GRAPH_H  */

diff --git a/graph/pr.c b/graph/pr.c
new file mode 100644 (file)
index 0000000..491258c
--- /dev/null
+++ b/graph/pr.c
@@ -0,0 +1,28 @@
+#include "graph/pr.h"
+#include <stdio.h>
+
+void
+pr_vertex (unsigned int vi)
+{
+  printf ("%d", vi);
+}
+
+void
+pr_edge (unsigned int vi, unsigned int vj)
+{
+  putchar ('{');
+  pr_vertex (vi);
+  putchar (',');
+  pr_vertex (vj);
+  putchar ('}');
+}
+
+void
+pr_arc (unsigned int vi, unsigned int vj)
+{
+  putchar ('(');
+  pr_vertex (vi);
+  putchar (',');
+  pr_vertex (vj);
+  putchar (')');
+}

diff --git a/graph/pr.h b/graph/pr.h
new file mode 100644 (file)
index 0000000..8d0ebdd
--- /dev/null
+++ b/graph/pr.h
@@ -0,0 +1,10 @@
+#ifndef GRAPH_PR_H
+#define GRAPH_PR_H
+
+void pr_vertex (unsigned int vi);
+
+void pr_edge (unsigned int vi, unsigned int vj);
+
+void pr_arc (unsigned int vi, unsigned int vj);
+
+#endif /* GRAPH_PR_H  */