#include <stdlib.h>
#include "grafo.h"
#include "fila.h"

/*função que inicializa um grafo com um determinado número de vértices
fornecido pelo usuário
Atenção: as listas de adjacências contêm nós de cabeçalho, pois isso facilita
na inserção posterior de arestas
essa função faz parte do TAD Grafo!
*/
void criar(Grafo *G, int NumVertices, int *erro) {
     if (NumVertices>MaxNumVertices)
        *erro=1;
     else {
          *erro=0;
          G->NumVertices=NumVertices;
          int i;
          for (i=0; i < G->NumVertices; i++) {
              G->Adj[i].inicio=(no_lista*) malloc(sizeof(no_lista));
              G->Adj[i].inicio->prox=NULL;
              G->Adj[i].fim=G->Adj[i].inicio;
          }
     }
}


/*função que verifica se um vértice não tem vértices adjacentes, assumindo a E.D. anterior
  essa função faz parte do TAD Grafo!!
*/
int ListaAdjVazia(Grafo *G, int V, int *erro) {
    if (V >= G->NumVertices) {
       *erro=1;
       return(1);
    }
    else {
         *erro=0;
         if (G->Adj[V].inicio->prox==NULL)
            return(1);
         else return(0);
    }
}

/* retorna o endereço do primeiro vértice na lista de adjacentes de V
   esta é uma função interna ao TAD Grafo
*/
no_lista* PrimeiroListaAdj(Grafo *G, int V, int *erro) {
    if (V >= G->NumVertices) {
       *erro=1;
       return(NULL);
    }
    else {
         *erro=0;
         return(G->Adj[V].inicio->prox);
    }
}

/*retorna o vértice adjacente Adj (apontado por Prox) da lista de adjacentes
de V, bem como o peso associado à aresta V-Adj, e posiciona Prox no próximo
vértice adjacente; FimListaAdj retorna 1 se o final da lista foi encontrado
esta é uma função interna ao TAD Grafo
*/
void ProxAdj(Grafo *G, no_lista **Adj, elem *P, no_lista **Prox, int *FimListaAdj, int *erro) {
     *erro=0;
     *Adj=*Prox;
     *P=(*Adj)->peso;
     *Prox=(*Prox)->prox;
     if (*Prox==NULL)
        *FimListaAdj=1;
}

/*função auxiliar para busca em largura, utiliza o TAD fila
*/
void visita_bfs(Grafo *G, int V, int distancia[], TipoCor cor[], int antecessor[]) {
     int FimListaAdj, peso, erro;
     no_lista *Adj, *Aux;

     Fila F;
     Create(&F);

     cor[V]=cinza;
     distancia[V]=0;
     Entra(&F,&V,&erro);
     printf("No %d, distancia=%d, antecessor=%d\n",V,distancia[V],antecessor[V]);

     while (!IsEmpty(&F)) {
           Sai(&F,&V,&erro);
           if (!ListaAdjVazia(G,V,&erro)) {
              Aux=PrimeiroListaAdj(G,V,&erro);
              FimListaAdj=0;
              while (!FimListaAdj) {
                    ProxAdj(G,&Adj,&peso,&Aux,&FimListaAdj,&erro);
                    if (cor[Adj->v]==branco) {
                       cor[Adj->v]=cinza;
                       distancia[Adj->v]=distancia[V]+1;
                       antecessor[Adj->v]=V;
                       Entra(&F,&Adj->v,&erro);
                       printf("No %d, distancia=%d, antecessor=%d\n",Adj->v,distancia[Adj->v],antecessor[Adj->v]);
                    }
              }
           }
           cor[V]=preto;
     }
}

/* função para busca em largura, utiliza a função auxiliar anterior  */
void busca_largura(Grafo *G) {
     int V, distancia[MaxNumVertices+1], antecessor[MaxNumVertices+1]; TipoCor cor[MaxNumVertices+1];

     printf("*** Sequencia de nos visitados na busca em largura ***\n\n");

     for (V=0; V < G->NumVertices; V++) {
         cor[V]=branco;
         distancia[V]=-1;
         antecessor[V]=-1;
     }
     for (V=0; V < G->NumVertices; V++)
         if (cor[V]==branco)
               visita_bfs(G,V,distancia,cor,antecessor);
}