00001
00002
00003 #include "graphes.h"
00004
00005
00006 #define NB_AL 10
00007
00008
00009
00010
00011
00012
00013
00014 GrapheListe freeGrapheListe(GrapheListe G) {
00015 if (G==NULL) return(NULL) ;
00016 int i;
00017 int n=G->nb_sommets;
00018 ListeAdj L,c;
00019 for(i=0;i<n;i++) {
00020 c=G->Adj[i];
00021 while(c!=NILL) {L=c->suivant; free(c); c=L; }
00022 }
00023 free(G);
00024 return(NULL) ;
00025 }
00026
00027
00028 GrapheMatr freeGrapheMatr(GrapheMatr H) {
00029 if (H==NULL) return(NULL) ;
00030 int i;
00031 int n=H->nb_sommets;
00032 int **T=H->Matr;
00033 for(i=0;i<n;i++) free(T[i]);
00034 free(H);
00035 return(NULL) ;
00036 }
00037
00038
00039
00040
00041
00042 int main (void) {
00043
00044 GrapheMatr H;
00045 GrapheListe G;
00046 GrapheListe G2;
00047 int *T;
00048 int n,m;
00049 int i,j;
00050
00051 int k;
00052
00053 printf("================================================================================================\n");
00054 printf("TEST AFFICHAGE...\n");
00055 G = lireGrapheListe("./graphe1.gr");
00056 afficheGrapheListe(G) ;
00057 G=freeGrapheListe(G);
00058
00059 printf("\nTEST AFFICHAGE ALÉATOIRE...\n");
00060 G=grapheListeAleatoire(8,20,5,0);
00061 afficheGrapheListe(G);
00062 G=freeGrapheListe(G);
00063
00064
00065 printf("\n================================================================================================\n");
00066 printf("TEST CONVERSIONS...\n") ;
00067 G = lireGrapheListe("./graphe2.gr");
00068 afficheGrapheListe(G);
00069 printf("listeVersMatr :\n");
00070 H = listeVersMatrice(G);
00071 printf("matrVersListe :\n");
00072 G2 = matriceVersListe(H);
00073 afficheGrapheListe(G);
00074 G=freeGrapheListe(G);
00075 G2=freeGrapheListe(G2);
00076 H=freeGrapheMatr(H);
00077
00078 printf("\nTEST CONVERSIONS ALÉATOIRE...\n") ;
00079 G=grapheListeAleatoire(133,2295,99,1);
00080 H = listeVersMatrice(G);
00081 G2 = matriceVersListe(H);
00082 G=freeGrapheListe(G);
00083 G2=freeGrapheListe(G2);
00084 H=freeGrapheMatr(H);
00085
00086 printf("\n ** Test supplémentaire :");
00087 for(k=0;k<NB_AL;k++) {
00088 printf("%i ",k);
00089 G=grapheListeAleatoire(100,5000,1000,1);
00090 H = listeVersMatrice(G);
00091 G2 = matriceVersListe(H);
00092 G=freeGrapheListe(G);
00093 G2=freeGrapheListe(G2);
00094 H=freeGrapheMatr(H);
00095 }
00096 printf(" **\n");
00097
00098
00099 printf("\n================================================================================================\n");
00100 printf("TEST TRANSPOSE...\n");
00101 G = lireGrapheListe("./graphe2.gr");
00102 afficheGrapheListe(G);
00103 G2=transpose(G);
00104 afficheGrapheListe(G2);
00105 G=freeGrapheListe(G);
00106 G2=freeGrapheListe(G2);
00107
00108 printf("\nTEST TRANSPOSE ALÉATOIRE...\n");
00109 G=grapheListeAleatoire(133,2295,99,1);
00110 G2=transpose(G);
00111 G=freeGrapheListe(G);
00112 G2=freeGrapheListe(G2);
00113
00114 printf("\n ** Test supplémentaire :");
00115 for(k=0;k<NB_AL;k++) {
00116 printf("%i ",k);
00117 G=grapheListeAleatoire(100,5000,1000,1);
00118 G2=transpose(G);
00119 G=freeGrapheListe(G);
00120 G2=freeGrapheListe(G2);
00121 }
00122 printf(" **\n");
00123
00124
00125 printf("\n================================================================================================\n");
00126 printf("TEST BIPARTI...\n");
00127 G=lireGrapheListe("graphe3.gr");
00128 n=G->nb_sommets;
00129 T = malloc(n*sizeof(int));
00130 T = biparti(G);
00131 if (T==NULL) {printf("Le graphes n'est pas biparti...\n");}
00132 else {
00133 for(i=0;i<n;i++) {
00134 if (T[i]==ROUGE) printf("sommet %i de couleur ROUGE\n",i);
00135 else printf("sommet %i de couleur VERT\n",i);
00136 }
00137 }
00138 G=freeGrapheListe(G);
00139 free(T);
00140
00141 printf("\nTEST BIPARTI ALÉATOIRE...\n");
00142 n=400; m=222;
00143 G=grapheListeAleatoire(n,m,1,0);
00144 T = malloc(n*sizeof(int));
00145 T = biparti(G);
00146 if (T==NULL) printf("Le graphes n'est pas biparti...\n");
00147 else {
00148 j=0;
00149 for(i=0;i<n;i++) {
00150 if (T[i]==ROUGE) j++;
00151 }
00152 printf("Le graphe est biparti et il y a %i sommets ROUGES et %i sommets VERTS.\n",j,n-j);
00153 }
00154 G=freeGrapheListe(G);
00155 free(T);
00156
00157 printf("\n ** Test supplémentaire :");
00158 for(k=0;k<NB_AL;k++) {
00159 printf("%i ",k);
00160 G=grapheListeAleatoire(100,5000,1000,1);
00161 T = malloc(n*sizeof(int));
00162 T = biparti(G);
00163 free(T);
00164 G=freeGrapheListe(G);
00165 }
00166 printf(" **\n");
00167
00168
00169 printf("\n================================================================================================\n");
00170 printf("TEST COMPOSANTES FORTEMENT CONNEXES...\n");
00171 G=lireGrapheListe("graphe4.gr");
00172 n=G->nb_sommets;
00173 T = malloc(n*sizeof(int));
00174 j = composantesFortemenentConnexes(G,T);
00175 printf("Le graphe comporte %i composantes fortements connexes.\n",j);
00176 if (j!=0) {for(i=0;i<n;i++) printf(" le sommet %i est dans la composante fortement connexe (%i)\n",i,T[i]);}
00177
00178 printf("\nTEST COMPOSANTES FORTEMENT CONNEXES ALÉATOIRE...\n");
00179 n=400; m=222;
00180 G=grapheListeAleatoire(n,m,1,0);
00181 n=G->nb_sommets;
00182 T = malloc(n*sizeof(int));
00183 j = composantesFortemenentConnexes(G,T);
00184 printf("Le graphe comporte %i composantes fortements connexes.\n",j);
00185
00186 printf("\n ** Test supplémentaire :");
00187 for(k=0;k<NB_AL;k++) {
00188 printf("%i ",k);
00189 G=grapheListeAleatoire(100,5000,1000,1);
00190 T = malloc(n*sizeof(int));
00191 j = composantesFortemenentConnexes(G,T);
00192 free(T);
00193 G=freeGrapheListe(G);
00194 }
00195 printf(" **\n");
00196
00197
00198 printf("\n================\n===== OK =====\n================\n") ;
00199
00200
00201 return(1) ;
00202 }
00203
