graph/adj.c

   1 #include "graph/adj.h"
   2 #include <errno.h>
   3 #include <stdlib.h>
   4
   5 struct graph *
   6 new_graph (unsigned int nv)
   7 {
   8   struct graph *g;
   9   int err;
  10
  11   if (!nv)
  12     {
  13       err = EINVAL;
  14       goto err_einval;
  15     }
  16
  17   if (!(g = malloc (sizeof *g)))
  18     {
  19       err = errno;
  20       goto err_malloc;
  21     }
  22
  23   g->nv = nv;
  24
  25   if (!(g->v = calloc (nv, sizeof *g->v)))
  26     {
  27       err = errno;
  28       goto err_calloc;
  29     }
  30
  31   return g;
  32
  33 err_calloc:
  34   free (g);
  35 err_malloc:
  36 err_einval:
  37   errno = err;
  38   return NULL;
  39 }
  40
  41 int
  42 add_arc (struct graph *g, unsigned int vi, unsigned int vj)
  43 {
  44   struct edge *e;
  45
  46   if (vi >= g->nv || vj >= g->nv)
  47     return -(errno = EINVAL);
  48
  49   if (!(e = malloc (sizeof *e)))
  50     return -errno;
  51
  52   e->to = &g->v[vj];
  53   e->next = g->v[vi].adj;
  54   g->v[vi].adj = e;
  55
  56   return 0;
  57 }
  58
  59 int
  60 add_edge (struct graph *g, unsigned int vi, unsigned int vj)
  61 {
  62   int err;
  63
  64   if (vi == vj)
  65     {
  66       err = -EINVAL;
  67       goto err_einval;
  68     }
  69
  70   if ((err = add_arc (g, vi, vj)))
  71     goto err_vivj;
  72
  73   if ((err = add_arc (g, vj, vi)))
  74     goto err_vjvi;
  75
  76   return 0;
  77
  78 err_vjvi:
  79   del_arc (g, vi, vj);
  80 err_vivj:
  81 err_einval:
  82   return -(errno = -err);
  83 }
  84
  85 void
  86 del_arc (struct graph *g, unsigned int vi, unsigned int vj)
  87 {
  88   struct vertex *i, *j;
  89   struct edge *e, *p;
  90
  91   if (vi >= g->nv || vj >= g->nv)
  92     return;
  93
  94   i = &g->v[vi];
  95   j = &g->v[vj];
  96
  97   e = i->adj;
  98   p = NULL;
  99
 100   while (e && e->to != j)
 101     {
 102       p = e;
 103       e = e->next;
 104     }
 105
 106   if (!e) /* not found */
 107     return;
 108
 109   if (!p)
 110     i->adj = e->next;
 111   else
 112     p->next = e->next;
 113
 114   free (e);
 115 }
 116
 117 void
 118 del_edge (struct graph *g, unsigned int vi, unsigned int vj)
 119 {
 120   del_arc (g, vi, vj);
 121   del_arc (g, vj, vi);
 122 }
 123
 124 void
 125 free_graph (struct graph *g)
 126 {
 127   struct vertex *v;
 128   unsigned int i;
 129
 130   if (!g)
 131     return;
 132
 133   for (i = 0; i < g->nv; ++i)
 134     {
 135       v = &g->v[i];
 136
 137       while (v->adj)
 138         del_arc (g, i, vertex_id (g, v->adj->to)); /* lazy */
 139     }
 140
 141   free (g->v);
 142   free (g);
 143 }