refac

diff --git a/dfs.c b/dfs.c
deleted file mode 100644 (file)
index f189f43..0000000
--- a/dfs.c
+++ /dev/null
@@ -1,142 +0,0 @@
-#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 e44f58344175baab1ddc32e21e19466aadde1283..dfcf0363dcf44da5290bf299dd2d20a1f0c3c9b7 100644 (file)
--- a/graph/adj.c
+++ b/graph/adj.c
@@ -6,29 +6,40 @@ struct graph *
 new_graph (unsigned int nv)
 {
   struct graph *g;
+  int err;
 
   if (!nv)
     {
-      errno = EINVAL;
-      return NULL;
+      err = EINVAL;
+      goto err_einval;
     }
 
   if (!(g = malloc (sizeof *g)))
-    return NULL;
+    {
+      err = errno;
+      goto err_malloc;
+    }
 
   g->nv = nv;
 
   if (!(g->v = calloc (nv, sizeof *g->v)))
     {
-      free (g);
-      return NULL;
+      err = errno;
+      goto err_calloc;
     }
 
   return g;
+
+err_calloc:
+  free (g);
+err_malloc:
+err_einval:
+  errno = err;
+  return NULL;
 }
 
 int
-new_arc (struct graph *g, unsigned int vi, unsigned int vj)
+add_arc (struct graph *g, unsigned int vi, unsigned int vj)
 {
   struct edge *e;
 
@@ -46,18 +57,84 @@ new_arc (struct graph *g, unsigned int vi, unsigned int vj)
 }
 
 int
-new_edge (struct graph *g, unsigned int vi, unsigned int vj)
+add_edge (struct graph *g, unsigned int vi, unsigned int vj)
 {
   int err;
 
   if (vi == vj)
-    return -(errno = EINVAL);
+    {
+      err = -EINVAL;
+      goto err_einval;
+    }
 
-  if ((err = new_arc (g, vi, vj)))
-    return err;
+  if ((err = add_arc (g, vi, vj)))
+    goto err_vivj;
 
-  if ((err = new_arc (g, vj, vi)))
-    return err;
+  if ((err = add_arc (g, vj, vi)))
+    goto err_vjvi;
 
   return 0;
+
+err_vjvi:
+  del_arc (g, vi, vj);
+err_vivj:
+err_einval:
+  return -(errno = -err);
+}
+
+void
+del_arc (struct graph *g, unsigned int vi, unsigned int vj)
+{
+  struct vertex *i, *j;
+  struct edge *e, *p;
+
+  if (vi >= g->nv || vj >= g->nv)
+    return;
+
+  i = &g->v[vi];
+  j = &g->v[vj];
+
+  e = i->adj;
+  p = NULL;
+
+  while (e && e->to != j)
+    {
+      p = e;
+      e = e->next;
+    }
+
+  if (!e) /* not found */
+    return;
+
+  if (!p)
+    i->adj = e->next;
+  else
+    p->next = e->next;
+
+  free (e);
+}
+
+void
+del_edge (struct graph *g, unsigned int vi, unsigned int vj)
+{
+  del_arc (g, vi, vj);
+  del_arc (g, vj, vi);
+}
+
+void
+free_graph (struct graph *g)
+{
+  struct vertex *v;
+  unsigned int i;
+
+  for (i = 0; i < g->nv; ++i)
+    {
+      v = &g->v[i];
+
+      while (v->adj)
+        del_arc (g, i, vertex_id (g, v->adj->to)); /* lazy */
+    }
+
+  free (g->v);
+  free (g);
 }

diff --git a/graph/adj.h b/graph/adj.h
index b0ec7233c41fc2b70825cbf7d4db014094405fce..2ec54a3b562a450cb4fb316edf2fa3bc20b3fa9c 100644 (file)
--- a/graph/adj.h
+++ b/graph/adj.h
@@ -3,31 +3,38 @@
 
 /* adjacency list implementation */
 
-struct vertex;
 struct edge;
-struct graph;
 
-struct edge
+struct vertex
 {
-  struct vertex *to;
-  struct edge *next;
+  struct edge *adj; /* edges linked list */
 };
 
-struct vertex
+struct edge /* probably not a good name for this */
 {
-  struct edge *adj;
+  struct vertex *to; /* other vertex in edge */
+  struct edge *next;
 };
 
 struct graph
 {
-  struct vertex *v;
-  unsigned int nv;
+  struct vertex *v; /* array of vertices */
+  unsigned int nv; /* number of vertices */
 };
 
 struct graph *new_graph (unsigned int nv);
+void free_graph (struct graph *g);
+
+int add_arc (struct graph *g, unsigned int vi, unsigned int vj);
+void del_arc (struct graph *g, unsigned int vi, unsigned int vj);
 
-int new_arc (struct graph *g, unsigned int vi, unsigned int vj);
+int add_edge (struct graph *g, unsigned int vi, unsigned int vj);
+void del_edge (struct graph *g, unsigned int vi, unsigned int vj);
 
-int new_edge (struct graph *g, unsigned int vi, unsigned int vj);
+static __inline__ unsigned int
+vertex_id (struct graph *g, struct vertex *v)
+{
+  return (unsigned int)(v - g->v);
+}
 
 #endif /* GRAPH_H  */

diff --git a/graph/dfs.c b/graph/dfs.c
new file mode 100644 (file)
index 0000000..72b05bb
--- /dev/null
+++ b/graph/dfs.c
@@ -0,0 +1,78 @@
+#include "graph/dfs.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)
+{
+  struct vertex *r, *n;
+  struct state *rs, *ns;
+  struct edge *e;
+  unsigned int ni;
+  int err;
+
+  (rs = &vs[ri])->c = RED;
+  r = &g->v[ri];
+  e = r->adj;
+
+  while (e && (n = e->to))
+    {
+      ni = vertex_id (g, n);
+      ns = &vs[ni];
+
+      if (ns->c == WHITE)
+        {
+          if ((err = add_arc (dt, ri, ni)))
+            return err;
+
+          if ((err = dfs_ (g, dt, vs, ni)))
+            return err;
+        }
+
+      e = e->next;
+    }
+
+  rs->c = BLUE;
+
+  return 0;
+}
+
+struct graph *
+dfs (struct graph *g)
+{
+  struct graph *dt;
+  struct state *vs;
+  unsigned int vi;
+
+  if (!(dt = 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 (dfs_ (g, dt, vs, vi))
+        goto err_dfs_;
+
+  free (vs);
+  return dt;
+
+err_dfs_:
+  free (vs);
+err_calloc:
+  free_graph (dt);
+err_new_graph:
+  return NULL;
+}

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