X-Git-Url: https://git.wirehaze.ovh/graph-theory.git/blobdiff_plain/8285b08b1ca5d40e691bdc6bcd0e0a6dfd904135..5638cc2d0dc28b74e32271de100952c0b305ef37:/graph/adj.c

diff --git a/graph/adj.c b/graph/adj.c
index e44f583..dfcf036 100644
--- 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);
 }