#include #include #include /* Le graphe est codé par les listes chaînées des pères. La structure suivante sert de base pour la construction des listes chaînées des pères. */ typedef struct pere { int nomPere; int longueur; struct pere * suivant; }PERE; /* synonyme du plus grand int */ #define INFINI INT_MAX /*************** Déclaration des variables globales ***************/ extern int ordre; /* remarque : les sommets s'appellent 0, 1, ..., ordre-1 */ extern PERE ** graphe;/* le tableau pour les listes chaînées des pères */ extern int * distance; /* distance[s] contiendra la distance au sommet s depuis un sommet donné */ extern int * antecedent; /* antecedent[s] contiendra l'avant-dernier sommet dans un plus court depuis un sommet donné vers s */ extern int * num; /* contiendra la numerotation topologique */ extern int * tableauDatePlusTot; extern int * tableauDatePlusTard; extern int derniereTache; extern int tacheDepart; extern int dureeTotaleProjet; extern int * deNum; /* contiendra la réciproque de la numerotation topologique. Si num[x] = numero, alors deNum{numero] = x. */ /****************** Fin des variables globales ************/ /************* prototype de la fonction construire *********** La fonction construire ouvre le fichier dont le nom est indiqué en paramètre puis y lit, d'abord l'ordre du graphe, puis la liste des arcs codés sous la forme (origine, extrémité, longueur). La fonction DOIT ALLOUER la place en mémoire pour le tableau graphe et doit construire les chaînes de pères. Exemple : le graphe ayant trois sommets, dont les noms sont 0, 1 et 2, l'arc (0,1) de poids 5 et l'arc (2,0) de poids -3 sera décrit ainsi dans un fichier : 3 0 1 5 2 0 -3 La fonction ferme le fichier qu'elle a ouvert. */ void construire(char *); /********** fin du prototype de la fonction construire *******/ /******** prototype de la fonction triTopologique ******* La fonction triTopologique tente d'effectuer un tri topologique des sommets du graphe. - S'il y a un circuit dans le graphe, la fonction retourne 0. - S'il n'y pas de circuit, la fonction remplit le tableau num qui doit contenir la numérotation topologique. Les numéros topologiques sont compris entre 0 et ordre - 1. La fonction remplit aussi le tableau deNum qui donne la bijection réciproque de num : si num[sommet] = numero, alors deNum[numero] = sommet. La fonction retourne 1. */ int triTopologique(void); /******** prototype de la fonction algoBellman ******* Lorsque l'on appelle cette fonction, on suppose que le graphe ne possède pas de circuit. Si cette condition n'est pas vérifiée, la fonction ne fonctionnera pas correctement. L'argument r indiqué en paramètre est le nom d'un sommet à partir duquel on cherche à calculer une arborescence de plus courts chemins. On suppose qu'au moment de l'appel de la fonction, une allocation mémoire a déjà été faite pour les tableaux distance et antecedent. Il s'agit de deux tableaux pouvant contenir chacun "ordre int". La fonction algoBellman remplit les tableaux distance et antecedent. À la fin de l'algorithme : - pour un sommet x non accessible à partir de r, distance[x] vaut INFINI (défini plus haut par un #define) et antecedent[x] vaut -1. - l'antecedent de r vaut -1. - pour un sommet x accessible à partir de r et autre que r, antecedent[x] est l'avant-dernier sommet dans un plus court chemin de r à x et distance[x] est la distance de r à x. */ void algoBellman(int r); void algoBellmanLong(int r); void algoBellmanCourt(); /******** prototype de la fonction afficher ******* La fonction "afficher" prend en paramètre un sommet r à partir duquel une arborescence des plus courts chemins a été calculée. Elle suppose que les tableaux antécédents et distance ont été correctement remplis ; pour un sommet s : - si s n'est pas accessible depuis r, antecedent[s] vaut -1 - si s est accessible depuis r, distance[s] indique la distance de r à s et antecedent[s] indique l'avant-dernier sommet dans un plus court chemin de r à s. Elle indique, pour chaque sommet s autre que r, le cas échéant que le sommet s n'est pas accessible depuis r, et sinon un plus court chemin pour aller de r à s (suite des sommets à emprunter) et la distance de r à s. */ void afficher(int); void afficherLong(int); void afficherCourt(int); /******** prototype de la fonction ecrireValeurs ************ /* Cette fonction sert à afficher à l'écran les valeurs mises dans un tableau dont les indices sont compris entre 0 et ordre - 1. Elle sert ici à vérifier le calcul des degrés extérieurs et celui des numéros topologiques. */ void ecrireValeurs(int *); /*********** POUR UNE PILE d'entiers positifs ou nuls ************/ /*La fonction suivante retourne 0 si la pile n'est pas vide et 1 si elle est vide */ int estVide(void); void afficherEtapesCritiques(); /* La fonction suivante empile l'entier indiqué en paramètre */ void empiler(int); /* Si la pile n'est pas vide, la fonction suivante dépile un entier et retourne la valeur de cet entier. Si la pile est vide, retourne -1 */ int depiler(void); /****************** FIN de POUR LA PILE ********************/