00001 00004 #include <stdlib.h> 00005 #include <stdio.h> 00006 #include <string.h> 00007 #include <math.h> 00008 00009 #define M_PI 3.14159265358979323846 00010 #define max(X,Y) ((X)>=(Y)?(X):(Y)) 00011 #define min(X,Y) ((X)<=(Y)?(X):(Y)) 00012 00013 /* ================================================ */ 00014 /* types publics */ 00015 /* ================================================ */ 00016 00020 typedef struct cell { 00022 int som; 00024 double v_arc; 00026 struct cell * next; 00027 } cell; 00028 00032 typedef cell * pcell; 00033 00034 00038 typedef struct graphe { 00039 00040 /* informations globales */ 00041 00043 int nsom; 00045 int nmaxarc; 00047 int narc; 00048 00049 /* representation par listes chainees de successeurs (application gamma) */ 00050 00052 pcell reserve; 00054 pcell libre; 00056 pcell * gamma; 00057 00058 /* representation par liste d'arcs 00059 (vecteurs tete (sommet initial), queue (sommet final)) */ 00060 00062 int *tete; 00064 int *queue; 00065 00066 /* informations additionelles ajoutees aux arcs */ 00067 00069 double *v_arcs; 00070 00071 /* informations additionelles ajoutees aux sommets */ 00072 00074 double *v_sommets; 00075 00077 double *x; 00079 double *y; 00081 char **nomsommet; 00082 } graphe; 00083 00084 /* ================================================ */ 00085 /* prototypes */ 00086 /* ================================================ */ 00087 00088 /* ====================================================================== */ 00089 void AfficheEnsemble(boolean *s, int n); 00090 /* Donnee s : un tableau de valeurs booleennes. 00091 Donnee n : la taille du tableau. 00092 Fonction : affiche l'ensemble represente par le tableau de booleens s. */ 00093 /* ====================================================================== */ 00094 00095 /* ====================================================================== */ 00096 void AfficheListe(pcell p); 00097 /* Donnee p : une liste chainee de successeurs. 00098 Fonction : affiche le contenu de la liste p. */ 00099 /* ====================================================================== */ 00100 00101 /* ====================================================================== */ 00102 void AfficheSuccesseurs(graphe * g) ; 00103 /* Donnee g : un graphe. 00104 Fonction : affiche le graphe dans sa representation "listes de successeurs". */ 00105 /* ====================================================================== */ 00106 00107 /* ====================================================================== */ 00108 void AfficheArcs(graphe * g); 00109 /* Donnee g : un graphe. 00110 Fonction : affiche le graphe dans sa representation "listes d'arcs". */ 00111 /* ====================================================================== */ 00112 00113 /* ====================================================================== */ 00114 void AfficheValeursSommets(graphe * g); 00115 /* ====================================================================== */ 00116 00117 /* ====================================================================== */ 00118 void PSGraphe(graphe * g, char *filename, double r, double t, double marge); 00119 /* Donnee g : un graphe. 00120 Donnee filename : nom du fichier postscript a generer. 00121 Donnee r : rayon des cercles qui representent les sommets (0 pour ne pas les dessiner). 00122 Donnee t : taille (demi-longueur) des fleches pour les arcs (0 pour ne pas les dessiner). 00123 Donnee marge : marge en x et en y. 00124 Fonction : genere une figure PostScript d'apres la representation "successeurs" 00125 du graphe g. */ 00126 /* ====================================================================== */ 00127 00128 /* ====================================================================== */ 00129 /* ====================================================================== */ 00130 /* FONCTIONS DE PLONGEMENT DE GRAPHES DANS LE PLAN */ 00131 /* ====================================================================== */ 00132 /* ====================================================================== */ 00133 00134 /* ====================================================================== */ 00135 void AutoNomsSommets(graphe * g, int mode); 00136 /* Donnee g : un graphe. 00137 Donnee mode : 1 pour que les noms soient les indices des sommets, 00138 2 pour que les noms soient les valeurs associées aux sommets, 00139 3 pour des noms composes de l'indice et de la valeur. 00140 Fonction : génère automatiquement des noms pour les sommets du graphe g. */ 00141 /* ====================================================================== */ 00142 00143 /* ====================================================================== */ 00144 void PlongementCirculaire(graphe * g, double r); 00145 /* Donnee g : un graphe. 00146 Donnee r : le rayon du cercle. 00147 Resultat g : le graphe g modifie. 00148 Fonction : affecte a chaque sommet des coord. (x,y) regulierement reparties 00149 sur un cercle. */ 00150 /* ====================================================================== */ 00151 00152 /* ====================================================================== */ 00153 void PlongementRadial(graphe * g, int c); 00154 /* Donnee g : un graphe. 00155 Donnee c : le sommet a placer au centre. 00156 Resultat g : le graphe g modifie. 00157 Fonction : repartit les sommets de g sur des cercles concentriques en fonction 00158 de leur rang, avec le sommet c au centre. */ 00159 /* ====================================================================== */ 00160 00161 /* ====================================================================== */ 00162 /* ====================================================================== */ 00163 /* FONCTIONS SUR LES LISTES CHAINEES DE SOMMETS */ 00164 /* ====================================================================== */ 00165 /* ====================================================================== */ 00166 00167 /* ====================================================================== */ 00168 pcell AlloueCell(pcell * plibre); 00169 /* Donnee plibre : pointeur sur une liste chainee de cellules libres. 00170 Resultat : pointeur sur une cellule. 00171 Fonction : retire la premiere cellule de la liste pointee par plibre 00172 et retourne un pointeur sur cette cellule */ 00173 /* ====================================================================== */ 00174 00175 /* ====================================================================== */ 00176 void LibereCell(pcell * plibre, pcell p); 00177 /* Donnee plibre : pointeur sur une liste chainee de cellules libres. 00178 Donnee p : pointeur sur une cellule. 00179 Fonction : insere la cellule p au debut de la liste pointee par plibre */ 00180 /* ====================================================================== */ 00181 00182 /* ====================================================================== */ 00183 void RetireTete(pcell * plibre, pcell * pliste); 00184 /* Donnee plibre : pointeur sur une liste chainee de cellules libres. 00185 Donnee pliste : pointeur sur une liste. 00186 Fonction : retire la premiere cellule de la liste 'pliste'. La cellule 00187 est chainee a la liste plibre. */ 00188 /* ====================================================================== */ 00189 00190 /* ====================================================================== */ 00191 void AjouteTete(pcell * plibre, pcell * pliste, int a); 00192 /* Donnee plibre : pointeur sur une liste chainee de cellules libres. 00193 Donnee pliste : pointeur sur une liste. 00194 Donnee a : un index de sommet. 00195 Fonction : ajoute une cellule contenant la valeur 'a' en tete de la liste 00196 'pliste'. La cellule est prise dans la liste 'plibre'. */ 00197 /* ====================================================================== */ 00198 00199 /* ====================================================================== */ 00200 int EstDansListe(pcell p, int a); 00201 /* Donnee p : une liste chainee de successeurs. 00202 Donnee a : une valeur entiere. 00203 Resultat : booleen. 00204 Fonction : retourne 1 si la valeur 'a' se trouve dans la liste p, 0 sinon. */ 00205 /* ====================================================================== */ 00206 00207 /* ====================================================================== */ 00208 /* ====================================================================== */ 00209 /* FONCTIONS D'ALLOCATION / LIBERATION POUR UN GRAPHE */ 00210 /* ====================================================================== */ 00211 /* ====================================================================== */ 00212 00213 00214 /* ====================================================================== */ 00215 graphe * InitGraphe(int nsom, int nmaxarc); 00216 /* Donnee nsom : nombre de sommets. 00217 Donnee nmaxarc : nombre maximum d'arcs. 00218 Resultat : un graphe. 00219 Fonction : alloue la memoire necessaire pour representer un graphe a 'nsom' sommets, 00220 possedant au maximum 'nmaxarc' arcs. 00221 Retourne un pointeur sur la structure allouee. */ 00222 /* ====================================================================== */ 00223 00224 /* ====================================================================== */ 00225 void TermineGraphe(graphe * g); 00226 /* Donnee g : un graphe. 00227 Fonction : libere la memoire occupee par le graphe g. */ 00228 /* ====================================================================== */ 00229 00230 /* ====================================================================== */ 00231 graphe * ReadGraphe(char * filename); 00232 /* Donnee filename : nom du fichier graphe. 00233 Resultat : un graphe. 00234 Fonction : Lit les donnees d'un graphe dans le fichier filename, 00235 retourne un pointeur sur la structure graphe construite. */ 00236 /* ====================================================================== */ 00237 00238 /* ====================================================================== */ 00239 /* ====================================================================== */ 00240 /* FONCTIONS DE MANIPULATION DES ARCS (APPLICATION GAMMA UNIQUEMENT) */ 00241 /* ====================================================================== */ 00242 /* ====================================================================== */ 00243 00244 /* ====================================================================== */ 00245 void AjouteArc(graphe * g, int i, int s); 00246 /* Donnee g : un graphe. 00247 Donnee i, s : deux sommets de g. 00248 Resultat g : le graphe modifie. 00249 Fonction : ajoute l'arc (i,s) au graphe g (application gamma seulement). */ 00250 /* ====================================================================== */ 00251 00252 /* ====================================================================== */ 00253 void RetireArc(graphe * g, int i, int s); 00254 /* Donnee g : un graphe. 00255 Donnee i, s : deux sommets de g. 00256 Resultat g : le graphe modifie. 00257 Fonction : retire l'arc (i,s) du graphe g (application gamma seulement), 00258 si celui-ci etait present. Sinon, pas d'action. */ 00259 /* ====================================================================== */ 00260 00261 /* ====================================================================== */ 00262 int PopSuccesseur(graphe *g, int i); 00263 /* Donnee g : un graphe. 00264 Donnee i : un sommet de g. 00265 Resultat : indice de sommet. 00266 Fonction : retire un arc (i,s) du graphe g (application gamma seulement), 00267 et retourne le sommet s. */ 00268 /* ====================================================================== */ 00269 00270 /* ====================================================================== */ 00271 int EstSuccesseur(graphe *g, int i, int s); 00272 /* Donnee g : un graphe. 00273 Donnee i, s : deux sommets de g. 00274 Resultat : booleen. 00275 Fonction : retourne 1 si le sommet 's' est un successeur du sommet 'i', 0 sinon */ 00276 /* ====================================================================== */ 00277 00278 /* ====================================================================== */ 00279 /* ====================================================================== */ 00280 /* FONCTIONS DE GENERATION DE GRAPHES */ 00281 /* ====================================================================== */ 00282 /* ====================================================================== */ 00283 00284 /* ====================================================================== */ 00285 graphe * GrapheAleatoire(int nsom, int narc); 00286 /* Donnee nsom : nombre de sommets. 00287 Donnee narc : nombre d'arcs. 00288 Resultat : un graphe. 00289 Fonction : retourne un graphe aleatoire a 'nsom' sommets et 'narc' arcs. 00290 Le graphe est asymetrique et sans boucle. 00291 Le nombre d'arcs doit etre <= nsom (nsom - 1) / 2. 00292 Remarque : la methode employee ici est naive, tres inefficace du point de vue 00293 temps de calcul et ne garantit aucune propriete statistique. */ 00294 /* ====================================================================== */ 00295 00296 /* ====================================================================== */ 00297 /* ====================================================================== */ 00298 /* OPERATEURS DE BASE SUR LES GRAPHES */ 00299 /* ====================================================================== */ 00300 /* ====================================================================== */ 00301 00302 /* ====================================================================== */ 00303 graphe * Symetrique(graphe * g); 00304 /* Donnee g : un graphe. 00305 Resultat : un graphe. 00306 Fonction : construit et retourne le graphe g_1 symetrique du graphe g. 00307 ATTENTION : seule la representation 'gamma' est utilisee. */ 00308 /* ====================================================================== */ 00309 00310 /* ====================================================================== */ 00311 graphe * FermetureSymetrique(graphe * g); 00312 /* Donnee g : un graphe. 00313 Resultat : un graphe. 00314 Fonction : construit et retourne la fermeture symetrique du graphe g. 00315 ATTENTION : seule la representation 'gamma' est utilisee. */ 00316 /* ====================================================================== */ 00317 00318 /* ====================================================================== */ 00319 void CompFortConnexe(graphe * g, graphe *g_1, int a, boolean * Ca); 00320 /* Donnee g : un graphe. 00321 Donnee g_1 : le graphe symetrique de g. 00322 Donnee a : un sommet du graphe g. 00323 Resultat Ca : un sous-ensemble des sommets de g (tableau de booleens). 00324 Fonction : retourne la composante fortement connexe de g contenant a. */ 00325 /* ====================================================================== */ 00326 00327 /* ====================================================================== */ 00328 boolean ExisteCircuit(graphe * g, int a); 00329 /* Donnee g : un graphe. 00330 Donnee a : un sommet du graphe g. 00331 Resultat : booleen 00332 Fonction : teste l'existence d'un circuit dans g contenant a 00333 /* ====================================================================== */ 00334 00335 /* ====================================================================== */ 00336 void CompConnexe(graphe * g, graphe *g_1, int a, boolean * Ca); 00337 /* Donnee g : un graphe. 00338 Donnee g_1 : le graphe symetrique de g. 00339 Donnee a : un sommet du graphe g. 00340 Resultat Ca : un sous-ensemble de sommets de g (tableau de booleens). 00341 Fonction : retourne la composante connexe de g contenant a. */ 00342 /* ====================================================================== */ 00343 00344 /* ====================================================================== */ 00345 boolean Connexe(graphe * g, graphe *g_1); 00346 /* Donnee g : un graphe. 00347 Donnee g_1 : le graphe symetrique de g. 00348 Resultat : booleen. 00349 Fonction : retourne TRUE si le graphe est connexe, FALSE sinon. */ 00350 /* ====================================================================== */
1.5.5