Untitled

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define VOIS_MAX 10

typedef struct voisins_s
{
  int poid;
  struct noeud_s *pstation;
} voisins;

typedef struct noeud_s
{
  char name[255];
  double x;
  double y;
  int n_vois;
  struct voisins_s *vois[VOIS_MAX];
} noeuds;

typedef struct graph_s
{
  int n_som;
  int n_arcs;
  struct noeud_s *list_stations;
} graph;

enum file_e
{ header, sum_names, sum_pos, arcs, err };

int
init_graphe (graph * this, int n_som, int n_arcs)
{
  this->n_som = n_som;
  this->n_arcs = n_arcs;
  this->list_stations = calloc (n_som, sizeof (noeuds));
  return (this->list_stations) ? 1 : 0;
}

void
destroy_graphe (graph * this)
{
  int i, j;
  noeuds *n;
  for (i = 0; i < this->n_som; i++)
    {
      for (j = 0, n = &(this->list_stations[i]); j < n->n_vois; j++)
        {
          free (n->vois[j]);
        }
    }
  free (this->list_stations);
}

void
name_graphe (graph * this, int n_som, char *tmp)
{
  strcpy (this->list_stations[n_som].name, tmp);
}

void
coord_graphe (graph * this, int n_som, int x, int y)
{
  this->list_stations[n_som].x = x;
  this->list_stations[n_som].y = y;
}

void
arc_graphe (graph * this, int n_som, int n_vois, int poid)
{
  if ((this->list_stations[n_som].vois[this->list_stations[n_som].n_vois] =
       malloc (sizeof (voisins))))
    {
      (this->list_stations[n_som].vois[this->list_stations[n_som].n_vois])->
        pstation = &this->list_stations[n_vois];
      (this->list_stations[n_som].vois[this->list_stations[n_som].n_vois])->
        poid = poid;
      this->list_stations[n_som].n_vois++;
    }
}

void
LireGraphe (graph * this, char *filename)
{
  int i = 0;
  int n_som = 0, n_arcs, j;
  double xi, yi;
  char buffer[BUFSIZ];
  char tmp[BUFSIZ];
  FILE *mf = fopen (filename, "r");
  enum file_e state = header;
  if (mf != NULL)
    {
      while (fgets (buffer, sizeof (buffer), mf) != NULL)
        {
          if (strncmp (buffer, "noms sommets", 12) == 0)
            {
              state = sum_names;
            }
          else if (strncmp (buffer, "coord sommets", 13) == 0)
            {
              state = sum_pos;
            }
          else if (strncmp (buffer, "arcs values", 11) == 0)
            {
              state = arcs;
            }
          switch (state)
            {
            case header:
              if (sscanf (buffer, "%d %d", &n_som, &n_arcs) == 2)
                {
                  init_graphe (this, n_som, n_arcs);
                }
              break;
            case sum_names:
              if (sscanf (buffer, "%d %[^\n]s", &j, tmp) == 2)
                {
                  name_graphe (this, j, tmp);
                }
              break;
            case sum_pos:
              if (sscanf (buffer, "%d %lf %lf", &j, &xi, &yi) == 3)
                {
                  coord_graphe (this, j, xi, xi);
                }
              break;
            case arcs:
              if (sscanf (buffer, "%d %d %lf", &j, &i, &xi) == 3)
                {
                  arc_graphe (this, j, i, xi);
                }
              break;
            case err:
            default:
              return;
            }
        }
        fclose(mf);
    }
}

/*
 fonction Dijkstra (n��uds, fils, distance, debut, fin)
  Pour n parcourant n��uds
    n.parcouru = infini   // Peut ��tre impl��ment�� avec -1
    n.precedent = 0
  Fin pour
  debut.parcouru = 0
  DejaVu = liste vide
  PasEncoreVu = n��uds
  Tant que PasEncoreVu != liste vide
    n1 = minimum(PasEncoreVu)   // Le n��ud dans PasEncoreVu avec parcouru le plus petit
    DejaVu.ajouter(n1)
    PasEncoreVu.enlever(n1)
    Pour n2 parcourant fils(n1)   // Les n��uds reli��s �� n1 par un arc
      Si n2.parcouru > n1.parcouru + distance(n1, n2)   // distance correspond au poids de l'arc reliant n1 et n2
        n2.parcouru = n1.parcouru + distance(n1, n2)
        n2.precedent = n1   // Dis que pour aller �� n2, il faut passer par n1
      Fin si
    Fin pour
  Fin tant que
  chemin = liste vide
  n = fin
  Tant que n != debut
    chemin.ajouterAvant(n)
    n = n.precedent
  Fin tant que
Retourner chemin
Fin fonction Dijkstra
*/

#define VERB 0

int
main (int argc, char **argv)
{

  graph mstruct;

  if (argc != 2)
    {
      fprintf (stderr, "usage: %s <filename>\n%s\n", argv[0],
               "lit un graphe dans le fichier <filename> et construit les structures de donnees correspondante");
      return EXIT_FAILURE;
    }
  LireGraphe (&mstruct, argv[1]);       // lit le graphe a partir du fichier 
#if(VERB)
  //Affichage du graphe
  int i, j;
  noeuds *n;
  printf ("nb sommets : %d \t nb arcs : %d \n", mstruct.n_som,
          mstruct.n_arcs);
  for (i = 0; i < mstruct.n_som; i++)
    {
      printf ("sommet n%d : %s \t\t x=%lf \t y=%lf \n", i,
              (mstruct.list_stations[i]).name, mstruct.list_stations[i].x,
              mstruct.list_stations[i].y);

    }
  for (i = 0; i < mstruct.n_som; i++)
    {
      for (j = 0, n = &(mstruct.list_stations[i]); j < n->n_vois; j++)
        {
          printf ("from: %s to %s: %d\n", n->name,
                  ((n->vois[j])->pstation)->name, (n->vois[j])->poid);
        }
    }
#endif

  destroy_graphe (&mstruct);
  return 0;
}