#include "graph/adj.h"
#include <errno.h>
#include <stdlib.h>

struct graph *
new_graph (unsigned int nv)
{
  struct graph *g;
  int err;

  if (!nv)
    {
      err = EINVAL;
      goto err_einval;
    }

  if (!(g = malloc (sizeof *g)))
    {
      err = errno;
      goto err_malloc;
    }

  g->nv = nv;

  if (!(g->v = calloc (nv, sizeof *g->v)))
    {
      err = errno;
      goto err_calloc;
    }

  return g;

err_calloc:
  free (g);
err_malloc:
err_einval:
  errno = err;
  return NULL;
}

int
add_arc (struct graph *g, unsigned int vi, unsigned int vj)
{
  struct edge *e;

  if (vi >= g->nv || vj >= g->nv)
    return -(errno = EINVAL);

  if (!(e = malloc (sizeof *e)))
    return -errno;

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

  return 0;
}

int
add_edge (struct graph *g, unsigned int vi, unsigned int vj)
{
  int err;

  if (vi == vj)
    {
      err = -EINVAL;
      goto err_einval;
    }

  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;

  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);
}