00001 /********************************************************************** 00002 ***** Pierre Hyvernat, cours info505 "Algorithmes de graphes" ***** 00003 ***** ***** 00004 ***** Il s'agit des définitions de quelques types de données ***** 00005 ***** pour le TP en salles machines... ***** 00006 ***** Le fichier contient également les prototypes de toutes les ***** 00007 ***** les fonctions définies dans "graphes.c" et les prototypes ***** 00008 ***** des fonctions que vous devrez définir. ***** 00009 *********************************************************************/ 00010 00011 00012 #include <stdlib.h> 00013 #include <stdio.h> 00014 #include <sys/time.h> 00015 00016 /* Une abbréviation pour la liste vide. */ 00017 #define NILL NULL 00018 00019 #define NON_VU 0 00020 #define VU 1 00021 #define EXAMINE 2 00022 #define GRIS 0 00023 #define ROUGE 1 00024 #define VERT -1 00025 00026 00027 00028 /* On va utiliser des listes chainées pour les listes d'adjacences. 00029 * Comme on veut pouvoir faire des graphes avec un poids sur les arêtes, 00030 * on utilise la définition suivante. 00031 * 00032 * Une liste d'adjacence est donc définit par le type "ListeAdj". Si L 00033 * est une telle liste, on peut accéder aux différents champs avec 00034 * - "L->but" : but de la première arête 00035 * - "L->poids" : poids de la première arête 00036 * - "L->suivant : suite de la liste 00037 * 00038 */ 00039 struct __arc { 00040 int poids ; /* poids de l'arête en question */ 00041 int but ; /* sommet but de l'arête en question */ 00042 struct __arc *suivant ; 00043 } ; 00044 00045 typedef struct __arc *ListeAdj ; 00046 00047 00048 /* prototype de la fonction "cons". 00049 * Pour faciliter l'insertion, on définit une fonction "cons" qui 00050 * rajoute une arête en tête de liste chainées. Elle prend en arguments 00051 * un poids "p" et un but "b" et renvoie une nouvelle liste d'adjacence. 00052 */ 00053 ListeAdj cons(int,int,const ListeAdj) ; 00054 00055 00056 /* Le type des graphes en liste d'adjacences est maintenant simple à 00057 * définir : un graphes est une structure qui contient un entier "n" 00058 * (nombre de sommets) et un tableau de listes d'adjacences de longueur 00059 * "n". 00060 */ 00061 typedef struct __GrapheListe { 00062 int nb_sommets ; 00063 ListeAdj *Adj ; 00064 } *GrapheListe ; 00065 00066 00067 /* prototype de la fonction de création d'un graphe en listes 00068 * d'ajacences. On définit une fonction qui initialise un graphe vide. 00069 * Elle prend en argument le nombre de sommets du graphe voulu. 00070 */ 00071 GrapheListe grapheListeVide (int) ; 00072 00073 00074 /* Le type des graphes en matrices d'adjacences... */ 00075 typedef struct __GrapheMatr { 00076 int nb_sommets ; 00077 int ** Matr ; 00078 } *GrapheMatr ; 00079 00080 00081 /* prototype de la fonction de création d'un graphe en matrice d'adjacence. 00082 * Une fonction qui initialise une matrice d'adjacence. ATTENTION, cette 00083 * fonction ne fait que créer la structure. La matrice est complêtement 00084 * arbitraire... 00085 */ 00086 GrapheMatr grapheMatrVide (int) ; 00087 00088 00089 /* prototype de la fonction de lecture d'un graphe dans un fichier. 00090 * Une petite fonction qui permet de lire un graphe dans un fichier. La 00091 * première ligne du fichier devra comporter un entier "n" qui 00092 * représentera le nombre de sommets du graphe ; et chaque ligne 00093 * suivante sera de la forme "a p b" où a est l'origine d'un arc, b le 00094 * but de l'arc et p le poids de l'arc. 00095 * L'argument est le nom du fichier, et la valeur de retour un graphe 00096 * sous forme de liste d'adjacence. 00097 */ 00098 GrapheListe lireGrapheListe(const char*) ; 00099 00100 00101 /* prototype de la fonction de génération aléatoire d'un graphe. Une 00102 * petite fonction pour générer un graphe de manière aléatoire. Cette 00103 * fonction prend en arguments le nombre de sommets (n), le nombre 00104 * d'arcs à générer (m), le poids maximum d'un arc (p) et un booléen 00105 * pour savoir si le graphe doit être orienté ou pas (o). 00106 */ 00107 GrapheListe grapheListeAleatoire(int,int,int,int) ; 00108 00109 00110 00111 /* ******************************************************************** 00112 * ******************************************************************** 00113 * ***** LE RESTE CONTIENT LES PROTOTYPES DES FONCTIONS QUE VOUS ***** 00114 * ***** DEVREZ DÉFINIR PENDANT LE TP... ***** 00115 * ******************************************************************** 00116 * ********************************************************************/ 00117 00118 00119 00120 /* prototype de la fonction d'affichage */ 00121 void afficheGrapheListe (const GrapheListe) ; 00122 00123 00124 /* protytpes des fonctions de conversion */ 00125 GrapheMatr listeVersMatrice(const GrapheListe) ; 00126 GrapheListe matriceVersListe(const GrapheMatr) ; 00127 00128 00129 /* prototype de la fonction qui renverse tous les arcs. */ 00130 GrapheListe transpose(const GrapheListe) ; 00131 00132 00133 /* prototype de la fonction qui teste si un graphe est biparti 00134 * Cette fonction renvoie le tableau des couleurs si le graphe est biparti, et 00135 * elle renvoie le pointeur NULL sinon. 00136 */ 00137 int*biparti(const GrapheListe) ; 00138 00139 00140 /* prototype de la fonction qui calcule le diametre d'un graphe et donne deux 00141 * sommets eloignés dans a et b 00142 */ 00143 int diametre(const GrapheListe G, int *a, int *b); 00144 00145 00146 /* prototype de la fonction qui calcule les composantes fortement connexes 00147 * Cette fonction renvoie le nombre de composantes fortements connexes, et 00148 * donne le numero de la composante de chaque sommet dans le tableau CC */ 00149 int composantesFortemenentConnexes(const GrapheListe,int CC[]) ; 00150 00151 00152 /* prototype de la fonction qui fait le tri topologique 00153 * Cette fonction renvoie un tableau qui contient les sommets : le tri 00154 * topologique sera donc obtenu en parcourant le resultat. 00155 */ 00156 int*triTopologique (const GrapheListe G); 00157 00158 00159 /* prototype de la fonction qui utilise l'algorithme de Prim pour calculer un 00160 * arbre couvrant de poids minimal. 00161 * Cette fonction renvoie le poids de l'arbre minimal et stocke l'arbre 00162 * couvrant dans le tableau A. 00163 */ 00164 int Prim(const GrapheListe G, int A[]); 00165
1.5.5