add gt.c

[graph-theory.git] / graph / adj.c

diff --git a/graph/adj.c b/graph/adj.c
index ec9cd0c8690d0d8acf381d05409a0f515160350c..fbad922f1a173dbc52eabbb7e1e91d54fe2f3aa9 100644 (file)
--- a/graph/adj.c
+++ b/graph/adj.c
@@ -1,39 +1,53 @@
-#include "adj.h"
-#include <stdlib.h>
+#include "graph/adj.h"
 #include <errno.h>
+#include <stdlib.h>
 
 struct graph *
 new_graph (unsigned int nv)
 {
-  struct graph *g;  
+  struct graph *g;
+  int err;
 
   if (!nv)
-    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;
 
   if (vi >= g->nv || vj >= g->nv)
-    return -EINVAL;
+    return -(errno = EINVAL);
 
   if (!(e = malloc (sizeof *e)))
-    return -ENOMEM;
+    return -errno;
 
   e->to = &g->v[vj];
   e->next = g->v[vi].adj;
@@ -43,15 +57,87 @@ 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 ((err = new_arc (g, vi, vj)))
-    return err;
+  if (vi == vj)
+    {
+      err = -EINVAL;
+      goto err_einval;
+    }
 
-  if (vi != vj && (err = new_arc (g, vj, vi)))
-    return err; /* should delete the other arc but fuck it we ball */
+  if ((err = add_arc (g, vi, vj)))
+    goto err_vivj;
+
+  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;
+
+  if (!g)
+    return;
+
+  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);
 }