/* =============================================================================
   Implementações dos algoritmos de grafos
   ========================================================================== */

#include "grafos.h"


void LeLinha() {
    char c;
    do { scanf("%c", &c); } while (c !='\n');
  return;
}

void LeGrafo(Grafo *G){
  char c;
  int i, m, u, v, custo;

  /* pula a primeira linha */
  LeLinha();

  scanf("%c", &c); /* pula a primeira letra */
  scanf("%d",&((*G).n)); /* no. vertices */
  scanf("%d",&m);        /* no. arestas  */
  LeLinha();

  /* aloca as listas de adjacências e inicializa-as como NULL */
  (*G).Adj=(ListaAdj *)calloc(((*G).n+1),sizeof(ListaAdj));

  /* lê as informações das arestas e monta as listas */
  for (i=1;i<=m;i++){
     scanf("%c %d %d %d",&c,&u,&v,&custo);
     InsereListaOrd(&(*G).Adj[u],v,custo);
     LeLinha();
  }
  return;
}

void LeGrafoNaoOrientado(Grafo *G){
  char c;
  int i, m, u, v, custo;

  /* pula a primeira linha */
  LeLinha();

  scanf("%c", &c); /* pula a primeira letra */
  scanf("%d",&((*G).n)); /* no. vertices */
  scanf("%d",&m);        /* no. arestas  */
  LeLinha();

  /* aloca as listas de adjacências e inicializa-as como NULL */
  (*G).Adj=(ListaAdj *)calloc(((*G).n+1),sizeof(ListaAdj));

  /* lê as informações das arestas e monta as listas */
  for (i=1;i<=m;i++){
     scanf("%c %d %d %d",&c,&u,&v,&custo);
     InsereListaOrd(&(*G).Adj[u],v,custo);
     InsereListaOrd(&(*G).Adj[v],u,custo);
     LeLinha();
  }
  return;
}

void ImprimeGrafo(Grafo *G){
  int n=(*G).n, i;
  ListaAdj p;

  printf("Grafo com %d vértices\n",n);
  printf("Listas de adjacência dos vértices:\n");
  for (i=1;i<=n;i++){
    printf("%d:",i);
    p=(*G).Adj[i];
    for(;p!=NULL;p=p->prox){
      printf(" %d (%d)",p->vert,p->custo);
      if (p->prox) printf(",");
    }
    printf("\n");
  }
  return;
}

/************************************
 Calcular a arvore geradora minima
 em C do grafo G dado.
 Dica: C ja esta inicializado, nao
   e preciso alocar memoria para C.
************************************/
void AGM(Grafo G, int *C) {
  int vertice[G.n+1]; /* \        */
  int custo[G.n+1];   /*  } HEAP  */
  int posicao[G.n+1]; /* /        */
  Cores cor[G.n+1]; /* enum{branco,cinza,preto} = {livre,no heap,já saiu do heap}*/
  int n; /* tamanho do heap */
  int este_vertice;
  int i;
  ListaAdj lista;
  
  for (i=0; i <= G.n+1; i++) {
    cor[i] = branco;
  }

  /* insere 1o. valor no heap */
  n=1;
  vertice[1] = 1;     /* numero do vertice      */
  custo[1]   = 0;     /* custo do vertice       */
  posicao[1] = 1;     /* posicao de 1 no heap   */
  cor[1]     = cinza; /* vertice 1 esta no heap */

  *C = 0; /* Custo total = 0 */

  while (n) {
    
    este_vertice = vertice[1];
    *C += custo[1];
    RemoveHeap(custo,vertice,posicao,&n);
    cor[este_vertice] = preto; /* este vértice já saiu do heap */

    lista = G.Adj[este_vertice];

    while (lista != NULL) {
      switch (cor[lista->vert]) {
      case branco:
	/* ainda não foi para o heap, vá agora */
	n++;
	vertice[n]           = lista->vert;
	custo[n]             = lista->custo;
	posicao[lista->vert] = n;
	cor[lista->vert]     = cinza;
	SobeHeap(custo,vertice,posicao,n);
	break;
      case cinza:
	if (lista->custo < custo[posicao[lista->vert]]) {
	  custo[posicao[lista->vert]] = lista->custo;
	  SobeHeap(custo,vertice,posicao,posicao[lista->vert]);
	}
	break;
      case preto:
	break;
      }
      lista = lista->prox;
    }

  }  
}

/************************************
 Calcular o caminho de aresta minimo
 entre dois vertices do grafo G dado
 a partir de uma raiz dada.
 Dica: dist ja esta iniciado.
************************************/
void CAM(Grafo G, int *dist, int raiz) {
  int i,j,k;
  ListaAdj noh;
  int **relacao;

  relacao = (int **) calloc(G.n+1,sizeof(int *));
  for (i=0; i <= G.n; i++) 
    relacao[i] = (int *) calloc(G.n+1,sizeof(int));


  /* faz todos os caminhos serem GRANDES o suficiente 
     para que toda comparacao com eles seja menor 
  */
  for (i=0; i <= G.n; i++)
    for (j=0; j <= G.n; j++)
      relacao[i][j]=INFINITO;

  /* Zera os caminhos da diagonal, pois a distancia ente 
     um vertice e ele mesmo é zero
  */
  for (i=0; i <= G.n; i++)
    relacao[i][i]=0;

  for (i=0; i <= G.n; i++) {
    noh = G.Adj[i];
    while (noh != NULL) {
      relacao[i][noh->vert] = noh->custo;
      noh = noh->prox;
    }
  }

  for (i=0; i <= G.n; i++)
    for (j=0; j <= G.n; j++)
      for (k=0; k <= G.n; k++)
	if (relacao[i][k] + relacao[k][j] < relacao[i][j])
	  relacao[i][j] = relacao[i][k] + relacao[k][j];

  for (i=0; i <= G.n; i++)
    dist[i] = relacao[raiz][i];  

  for (i=0; i <= G.n; i++)
    free(relacao[i]);

  free(relacao);

}

void InicializaGrafo(Grafo *G){
  (*G).Adj=NULO;
  (*G).n=0;
  return;
}


void LiberaGrafo(Grafo *G){
  int i;
  for (i=1;i<=G->n;i++)
    LiberaLista(&(G->Adj[i]));
  free((*G).Adj);
  return;
}















/* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */