LAB 5 / CES 11

          Olá! Nesta publicação, o projeto tinha a função de avaliar a manipulação de grafos, através de algoritmos como o de Dijkstra, DFS (Depth-First Search) e de Tarjan modificado para verificar a ciclicidade de um dígrafo. A ideia seria a de fornecer a uma agência aérea: os menores caminhos (custo-mínimo) e os ciclos existentes entre aeroportos. Acompanhe a seguir:

 #include <stdio.h>  
 #include <stdlib.h>  
 #include <string.h>  
 #include <stdbool.h>  
 #define INFINITO 1000000  
 typedef int vertice;  
 typedef struct CelAdj CelAdj;  
 struct CelAdj  
 {  
   vertice vert;  
   int minutos;  
   CelAdj *prox;  
 };  
 typedef struct CelVert CelVert;  
 struct CelVert  
 {  
   char aeroporto[30];  
   CelAdj *listaAdj;  
 };  
 typedef struct digrafo digrafo;  
 struct digrafo  
 {  
   int nvert;  
   CelVert *vertices;  
 };  
 typedef struct node node;  
 struct node  
 {  
   int vertice;  
   node *prox;  
 };  
 typedef node *pilha;  
 typedef node *posicao;  
 void BubbleSort (digrafo *G)  
 {  
   //EXECUTA 'BUBBLE-SORT' NAS LISTAS ADJACENTES DO DIGRAFO G  
   int i, vert_aux, minutos_aux;  
   CelAdj *P;  
   bool mudou = true;  
   for(i = 0; i <= G->nvert-1; i++)  
   {  
     P = G->vertices[i].listaAdj;  
     while(mudou == true)  
     {  
       mudou = false;  
       P = G->vertices[i].listaAdj;  
       while(P->prox != NULL)  
       {  
         if(P->vert > P->prox->vert)  
         {  
           vert_aux = P->vert;  
           minutos_aux = P->minutos;  
           P->vert = P->prox->vert;  
           P->minutos = P->prox->minutos;  
           P->prox->vert = vert_aux;  
           P->prox->minutos = minutos_aux;  
           mudou = true;  
         }  
         P = P->prox;  
       }  
     }  
   }  
 }  
 int Dijkstra(digrafo G, int ref, int desc, vertice parent[], vertice dist[])  
 {  
   vertice v, w, v_aux, w_aux;  
   CelAdj *P;  
   for (w = 0; w <= G.nvert-1; w++)  
   {  
     parent[w] = -1;  
     dist[w] = INFINITO;  
   }  
   parent[ref] = ref;  
   dist[ref] = 0;  
   while (1)  
   {  
     //EXECUTA O LOOP ENQUANTO ALGUMA DISTANCIA SOFRE ALTERACAO, TODA VEZ QUE SE PERCORRE O DIGRAFO  
     int min_dist = INFINITO;  
     for (v = 0; v <= G.nvert-1; v++)  
       if (parent[v] != -1)  
         for (P = G.vertices[v].listaAdj; P != NULL; P = P->prox)  
           if (parent[P->vert] == -1 && min_dist > dist[v] + P->minutos)  
           {  
             min_dist = dist[v] + P->minutos;  
             v_aux = v;  
             w_aux = P->vert;  
           }  
     if (min_dist == INFINITO)  
       break;  
     parent[w_aux] = v_aux;  
     dist[w_aux] = min_dist;  
   }  
   return dist[desc];  
 }  
 void push (pilha *P, vertice v)  
 {  
   node *temp;  
   temp = *P;  
   *P = (node *) malloc (sizeof (node));  
   (*P)->vertice = v;  
   (*P)->prox = temp;  
 }  
 void pop (pilha *P)  
 {  
   node *temp;  
   temp = *P;  
   *P = (*P)->prox;  
   free (temp);  
 }  
 void DFS(vertice v, bool *aciclico, vertice *expl, vertice *comp, pilha *P, int *ce, int *cc, digrafo G, FILE *f_saida)  
 {  
   expl[v] = ++(*ce);  
   push(P,v);  
   CelAdj *Q;  
   for(Q = G.vertices[v].listaAdj; Q != NULL; Q = Q->prox)  
     if(expl[Q->vert] == 0) //CASO AINDA NAO TENHA SIDO EXPLORADO, ENTRA NESSE VERTICE  
       DFS(Q->vert, aciclico, expl, comp, P, ce, cc, G, f_saida);  
     else if (expl[Q->vert] < expl[v] && comp[Q->vert]==0)  
     {  
       //CASO SEJA UMA ARESTA DE RETORNO (B), MOSTRA CILICIDADE, E IMPRIME O CICLO  
       *aciclico = false;  
       int j, tamanho_pilha = 0;  
       posicao T, F;  
       T = *P;  
       while(T->prox != NULL)  
       {  
         T = T->prox;  
         tamanho_pilha++;  
       }  
       F = T;  
       while(tamanho_pilha >= 0)  
       {  
         for(j = tamanho_pilha, T = *P; j >= 1; j--)  
           T = T->prox;  
         fprintf(f_saida, "%d-", T->vertice);  
         tamanho_pilha--;  
       }  
       fprintf(f_saida, "%d\n", F->vertice);  
     }  
   pop(P);  
   comp[v] = ++(*cc);  
 }  
 void Ciclos (digrafo G, vertice *expl, vertice *comp, FILE *f_saida)  
 {  
   pilha P;  
   P = NULL;  
   bool aciclico = true;  
   int ce = 0, cc = 0;  
   vertice v;  
   for (v = 0; v <= G.nvert-1; v++)  
   {  
     expl[v] = 0;  
     comp[v] = 0;  
   }  
   for (v = 0; v <= G.nvert-1; v++)  
     if (expl[v] == 0)  
       DFS(v, &aciclico, expl, comp, &P, &ce, &cc, G, f_saida);  
 }  
 int main()  
 {  
   digrafo G;  
   FILE *f_entrada, *f_saida;  
   f_entrada = fopen("entrada.txt", "r");  
   f_saida = fopen("saida.txt", "w");  
   int i;  
   /** RECEBE OS VERTICES **/  
   char aeroporto[31], lixo;  
   fscanf(f_entrada, "%d%c", &G.nvert, &lixo);  
   G.vertices = (CelVert *)malloc(G.nvert * sizeof(CelVert));  
   for(i = 0; i <= G.nvert-1; i++)  
     G.vertices[i].listaAdj = NULL;       //ZERA TODAS AS LISTAS ADJACENTES  
   for(i = 0; i <= G.nvert-1; i++)  
   {  
     fgets(aeroporto, 31, f_entrada);  
     aeroporto[strlen(aeroporto)-1] = '\0';   //TIRA O '\N' DO FINAL DA STRING  
     strcpy(G.vertices[i].aeroporto, aeroporto); //PASSA O NOME PARA O DIGRAFO  
   }  
   /** RECEBE OS ARCOS **/  
   int quant_arcos;  
   fscanf(f_entrada, "%d", &quant_arcos);  
   int pred, suc, custo;  
   CelAdj *P;  
   for(i = 1; i <= quant_arcos; i++)  
   {  
     fscanf(f_entrada, "%d %d %d", &pred, &suc, &custo);  
     if(G.vertices[pred].listaAdj == NULL)    //INICIA A LISTA ADJACENTE DE 'PRED'  
     {  
       P = G.vertices[pred].listaAdj = (CelAdj *)malloc(sizeof(CelAdj));  
       P->vert = suc;  
       P->minutos = custo;  
       P->prox = NULL;  
     }  
     else                    //CONTINUA A LISTA ADJACENTE JA INICIADA  
     {  
       P->prox = (CelAdj *)malloc(sizeof(CelAdj));  
       P = P->prox;  
       P->vert = suc;  
       P->minutos = custo;  
       P->prox = NULL;  
     }  
   }  
   BubbleSort(&G);                 //ORDENA AS LISTAS DE ADJACENCIAS  
   fprintf(f_saida ,"Digrafo:\n");  
   for(i = 0; i <= G.nvert-1; i++)  
   {  
     fprintf(f_saida, "%d (%s):", i, G.vertices[i].aeroporto);  
     P = G.vertices[i].listaAdj;  
     while(P != NULL)  
     {  
       fprintf(f_saida, " %d(%d)", P->vert, P->minutos);  
       P = P->prox;  
     }  
     fprintf(f_saida, "\n");  
   }  
   fprintf(f_saida, "\n");  
   /** CONSULTAS DE ROTAS MINIMAS **/  
   fprintf(f_saida, "Rotas minimas:\n");  
   int c, partida, chegada, dist_esp;         //CONSULTA DE ROTAS MINIMAS  
   vertice *dist;                   //VETOR DE PONTEIROS PARA INT  
   vertice *parent;                  //VETOR DE PAIS DE UM VERTICE  
   vertice vert, filho;  
   dist = (vertice *)malloc(G.nvert * sizeof(vertice));  
   parent = (vertice *)malloc(G.nvert * sizeof(vertice));  
   fscanf(f_entrada, "%d", &c);  
   for(i = 1; i <= c; i++)               //PARA CADA 'C', EXECUTA O ALG. DIJKSTRA  
   {  
     fscanf(f_entrada, "%d %d", &partida, &chegada);  
     fprintf(f_saida, "%d a %d: ", partida, chegada);  
     if(partida == chegada)  
       fprintf(f_saida, "(0 minutos)\n");  
     else  
     {  
       dist_esp = Dijkstra(G, partida, chegada, parent, dist); //EXECUTA DIJKSTRA PARA DEFINIR 'PARENT'  
       if(dist[chegada] == INFINITO)  
         fprintf(f_saida, "sem voos\n");  
       else  
       {  
         while (partida != chegada)             //IMPRIME O CAMINHO A SER SEGUIDO  
         {  
           for(vert = chegada; vert != partida; vert = parent[vert])  
             filho = vert;  
           fprintf(f_saida, "%d-", vert);  
           partida = filho;  
         }  
         fprintf(f_saida, "%d ", chegada);  
         fprintf(f_saida, "(%d minutos)\n", dist_esp);  
       }  
     }  
   }  
   fprintf(f_saida, "\n");  
   fclose(f_entrada);  
   /** ANALISE DE TRAJETOS FECHADOS **/  
   fprintf(f_saida, "Trajetos fechados:\n");  
   vertice *expl, *comp;  
   expl = (vertice *)malloc(G.nvert * sizeof(vertice));  
   comp = (vertice *)malloc(G.nvert * sizeof(vertice));  
   Ciclos(G, expl, comp, f_saida);           //IMPRIME OS CICLOS, SE EXISTIREM  
   fclose(f_saida);  
   return 0;  
 }