Documents publiés » Implémentation de l’algorithme de Dijkstra » Code de l’implémentation de l’algorithme de Dijkstra (Annexe) »

djikstra.cpp


#include <stdio.h>
#include "types.h"
#include "graphe.h"
#include "menu.h"
#include <string.h>
#include <stdlib.h>

void Interrogation(char * s, char * c)
{
 printf("\n %s \n", s) ;
 fgets(c,255,stdin) ;
 // On se débarrasse du retour de chariot
 c[strlen(c)-1]='\0';

}

Bool LectChn (FILE * fR, char * chn)
{
  fgets (chn, 255, fR);
  return vrai ;
}

void main()
{
 Bool charge = faux ;
 Bool sauve = vrai ;
 char * c [] = {"creation interactive d’un Graphe", "Afficher un graphe", "Charger un graphe en format texte", "Sauver un graphe en format texte", "Trouver les plus courts chemins", "Enregistrer le resultat", "Quitter" } ;
 Menu * m = new Menu("Menu principal", 7, c, "GACSTEQ") ;
 Graphe * g = NULL ;
 Res * re = NULL ;
 while (vrai)
 {
  m->Affiche() ;
  int r = m->Reponse() ;
  char chn [255] ;
  char * index ;
  Bool flag, sym = vrai ;
  char rep [3] ;
  char fichier[12] ;
  int * * mat ;
  int n, i, j, t, k, p;
  FILE * f;
  switch (r)
  {
  case 0 :
   Interrogation("Nombre de sommets :", rep) ;
   n = atoi(strdup(rep)) ;
   Interrogation("Symetrique : O/N", rep) ;
   if (toupper(strdup(rep)[0])=='N')
    sym = faux ;
   else
    sym = vrai ;
   mat =new int * [n] ;
   for ( i=0; i<n ; i++)
    mat[i]= new int [n] ;
   for ( i=0; i<n ; i++)
   {
    printf("Sommet %d \n", i) ;
    for (j=0 ; j<n ; j++)
    {
     if (i!=j && (i<j || sym==faux))
     {
      printf("\t Relie au sommet %d par une arete de poids :", j) ;
      Interrogation("",rep) ;
      if (strlen(rep)==0)
       t = -1 ;
      else
       t = atoi(strdup(rep)) ;
      mat[i][j]=t ;
      if (sym==vrai)
       mat[j][i]=mat[i][j] ;
     }
     else if (i==j)
      mat[i][i]=0 ;
    }
   }
   g = new Graphe(mat, n) ;
   g->Affiche() ;
   sauve = faux ;
   for (i=0 ; i<n ; i++)
    delete mat[i] ;
   delete mat ;
   break ;
  case 1 :
   if (g!=NULL)
   {
    g->Affiche() ;
   }
   else
    printf("Aucun graphe selectionne \n") ;
   break ;
  case 2 :
   do
   Interrogation("Entrez le nom du fichier :",fichier) ;
   while (strlen(fichier)==0) ;
   printf("\n %s \n", fichier) ;
   f = fopen (fichier, "r") ;
   if (f == NULL)
   {
    fprintf(stderr, "%s est introuvable !\a \n", fichier);
    break ;
   }
   LectChn(f, chn) ;
   index=strstr(chn, "Taille : ") ;
   if (index==NULL)
   {
    printf("Format de fichier non valide !\n") ;
    break ;
   }
   n = atoi(index+9) ;
   mat =new int * [n] ;
   for ( i=0; i<n ; i++)
   {
    mat[i]= new int [n] ;
    for(j=0 ; j<n ; j++)
     mat[i][j]=-1 ;
    mat[i][i]=0 ;
   }
   for(k=0 ; k<n ; k++)
   {
    if (index!=NULL)
     LectChn(f, chn) ;
    index=strstr(chn, "Sommet : ") ;
    if (index==NULL)
    {
     printf("Format de fichier non valide (Sommet %d)!\n",k) ;
     break ;
    }
    i = atoi(index+9) ;
    index = NULL ;
    flag=vrai;
    while (vrai) 
    {
     LectChn(f, chn) ;
     index=strstr(chn, "Extremite : ") ;
     if (index==NULL)
     {
      flag=faux ;
      break ;
     }
     j = atoi(index+12) ;
     LectChn(f, chn) ;
     index=strstr(chn, "Poids : ") ;
     if (index==NULL)
     {
      flag=faux ;
      break ;
     }
     p = atoi(index + 8) ;
     if (flag)
     mat[i][j]= p ;
    }   
   }
   g = new Graphe(mat, n) ;
   g->Affiche() ;
   charge = vrai ;
   fclose(f) ;
   for (i=0 ; i<n ; i++)
    delete mat[i] ;
   delete mat ;
   break ;
  case 3 :
   /*if (sauve!=faux)
   {
    printf("Rien à sauvegarder…\n") ;
    break ;
   }*/
   if (g!=NULL)
   {
    do
    Interrogation("Sous quel nom voulez-vous l’enregistrer ?",fichier) ;
    while (strlen(fichier)==0) ;
    f= fopen(fichier, "w+") ;
    g->Affiche(f) ;
    sauve = vrai ;
    fclose(f) ;
   }
   else
    printf("Aucun graphe selectionne \n") ;
   break ;
  case 4 :
   if (g!=NULL)
   {
    Interrogation("Sommet source ?", rep) ;
    i = atoi(rep) ;
    re = g->Djikstra(i) ;
    re->Affiche() ;
   }
   else
    printf("Aucun graphe selectionne \n") ;
   break ;
  case 5 :
   if (re!=NULL)
   {
    do
    Interrogation("Sous quel nom voulez-vous l’enregistrer ?",fichier) ;
    while (strlen(fichier)==0) ;
    f= fopen(fichier, "w+") ;
    re->Affiche(f) ;
    fclose(f) ;
   }
   else
    printf("Aucun resultat calcule \n") ;
   break ;
  case 6 :
   delete m ;
   if (g!=NULL)
    delete g;
   if (re!=NULL)
    delete re;
   exit(0) ;
  }
 }
}