#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "algrafo.h"
#include "RQ.h"



/* Funções Lista - Ligada */
node NovaLista() {
  return NULL;
}

node AddLista(node lista, int item) {
  node a = malloc(sizeof*a);
  a->num = item;
  a->next = lista;
  return a;
}

int BuscaLista(node lista, int item) {
  while(lista) {
    if(item==lista->num)
      return 1;
    lista = lista->next;
  }
  return 0;
}

node RemoveLista(node lista, int item) {
  node a;
  if(lista==NULL)
    return NULL;
  if(item==lista->num) {
    a = lista->next;
    free(lista);
    return RemoveLista(a,item);
  }
  lista->next = RemoveLista(lista->next, item);
  return lista;
}

void DestroiLista(node lista) {
  node a;
  while(lista) {
    a = lista->next;
    free(lista);
    lista=a;
  }
}

void ImprimeLista(node lista) {
  while(lista) {
    printf("[%d]",lista->num);
    lista = lista->next;
  }
  printf("\n");
}

/* fim das funcoes de Lista Ligada */

node* Listagem(int a);
int* Graus(int a, int valor);
Graph GRAPHinit(int a) {
  Graph b = malloc(sizeof*b);
  b->V = a;
  b->E = 0;
  b->listas = Listagem(a);
  return b;
}

Edge EDGE(int a, int b) {
   Edge c;
   c.v = a;
   c.w = b;
   return c;
}

void GRAPHinsertE(Graph a, Edge b) {

/*  if(BuscaLista(a->listas[b.w], b.v) || b.w == b.v)
    return;*/
  (a->E)++;
  a->listas[b.v] = AddLista(a->listas[b.v], b.w);
  a->listas[b.w] = AddLista(a->listas[b.w], b.v);
}

void GRAPHremoveE(Graph a, Edge b) {
  if(BuscaLista(a->listas[b.v], b.w)) {
    a->listas[b.v] = RemoveLista(a->listas[b.v], b.w);
    a->listas[b.w] = RemoveLista(a->listas[b.w], b.v);
    (a->E)--;
  }
}

void GRAPHdestroy(Graph a) {
  int i;
  for(i=0;i<a->V;i++) {
    DestroiLista(a->listas[i]);

  }
  free(a->listas);
  free(a);
}

void GRAPHshow(Graph g) {
  int b;
  printf("[%d Arestas, %d Vertices]\n",g->E, g->V);
  for(b=0;b<g->V;b++) {
    printf("%d: ",b);
    ImprimeLista(g->listas[b]);

  }
}

Graph GRAPHrand(int V, int E) {
  Edge arr;
  Graph a = GRAPHinit(V);
  while(a->E<E) {
    arr.w = rand()%V;
    arr.v = rand()%V;
    fflush(NULL);
    GRAPHinsertE(a, arr);
  }
  return a;

}

Graph GRAPHscan(int V, int E) {
  Edge arr;
  int i;
  Graph a = GRAPHinit(V);
  for(i=0;i<E;i++) {
    scanf("%d %d", &arr.v, &arr.w);
    GRAPHinsertE(a, arr);
  }
  return a;
}


node* Listagem(int a) {
  node* n;
  int i;
  n = malloc(a*sizeof(node*));
  for(i=0;i<a;i++)
    n[i]=NULL;
  return n;
}
int *h, hMax;
void rfs(Graph G, Edge e) {
   node t; int v;
   RQput(e);
   while(!RQEmpty())
      if(h[(e=RQget()).w] == -1) {
         h[e.w] = h[e.v]+1;
         if(hMax < h[e.w])
            hMax = h[e.w];
         for(t=G->listas[e.w]; t!=NULL; t=t->next) {
            if(h[v=t->num] == -1)
               RQput(EDGE(e.w,v));
         }
      }
}

int EPbla(Graph g) {
   int i;
   h = malloc(g->V*(sizeof*h));
   hMax = 0;
   RQInit((int)((double)g->V*g->V + 1)/4.0);
   for(i=0;i<g->V;i++)
      h[i]=-1;
   rfs(g,EDGE(0,0));
   free(h);
   return hMax;
}

Graph GRAPHcompleto(int V) {
   int i;
   node no;
   Graph g = GRAPHinit(V);
   no = NovaLista();
   for(i=0;i<V;i++)
      no = AddLista(no, i);

   for(i=0;i<V;i++)
      g->listas[i]=no;

   return g;

}