Code/graphes.c

/**********************************************************************
 ***** Pierre Hyvernat, cours info505 "Algorithmes de graphes"    *****
 *****                                                            *****
 ***** Il s'agit des définitions de quelques fonctions pour le TP *****
 ***** en salles machines...                                      *****
 ***** Les commentaire pertinents se trouvent dans le fichier     *****
 ***** "graphes.h".
 *********************************************************************/

#include "graphes.h"


ListeAdj cons(int p, int b, const ListeAdj L) {
 ListeAdj l = malloc(sizeof(struct __arc)) ;
 l->poids = p ;
 l->but = b ;
 l->suivant = L ;
 return(l) ;
}


GrapheListe grapheListeVide (int n) {
 int i;
 GrapheListe G = malloc(sizeof(struct __GrapheListe));
 G->nb_sommets = n ;
 G->Adj = malloc(n*sizeof(ListeAdj*)) ;
 for(i=0;i<n;i++) G->Adj[i]=NILL;
 return(G) ;
}


GrapheMatr grapheMatrVide (int n) {
  GrapheMatr G=malloc(sizeof(struct __GrapheMatr)) ;  int i ;
  G->nb_sommets = n ;
  G->Matr = malloc(n*sizeof(int*)) ;
  for(i=0;i<n;i++) G->Matr[i] = malloc(n*sizeof(int)) ;
  return(G) ;
}


GrapheListe lireGrapheListe(const char *fichier) {
 FILE *flot;
 GrapheListe G ;
 int n,b,p,s ;
 if ((flot = fopen(fichier, "r")) == NULL) {
  fprintf(stderr,"\nErreur: impossible d'ouvrir le fichier %s\n", fichier);
  return(NULL);
 }
 if (!fscanf(flot, "%i", &n)) {
  fprintf(stderr,"\nErreur: je n'arrive pas à lire les nombre de sommets dans %s\n", fichier);
  return(NULL);
 }
 G = grapheListeVide(n) ;
 while (fscanf(flot, "%i %i %i", &s, &p, &b) == 3) {
  if (p!=0 && s>=0 && s<n && b>=0 && b<n) G->Adj[s] = cons(p,b,G->Adj[s]) ;
 }
 return(G) ;
}


GrapheListe grapheListeAleatoire(int n, int m, int p, int o) {
 struct timeval temps ;
 int i, q, a, s, t;
 int N=n*n ;
 GrapheListe G = grapheListeVide(n) ;
 gettimeofday(&temps, NULL) ;
 srand(temps.tv_usec) ;
 for(i=0;i<m;i++) {
  q=1+(int) ((float)p*rand()/(RAND_MAX+1.0));
  a=(int) ((float)N*rand()/(RAND_MAX+1.0));
  s = a%n ;
  t = a/n ;
  G->Adj[t] = cons(q,s,G->Adj[t]) ;
  if (o==0) G->Adj[s] = cons(q,t,G->Adj[s]);
 }
 return(G) ;
}

---