graphe.h

#include <stdio.h>
#include "types.h"

typedef int Sommet ; // Les sommets sont repérés par leur numéro


/* Une flêche est constituée d’une arête et de son sommet d’arrivée*/
struct Fleche {
   Sommet extrem ; // Numéro du sommet d’arrivée
   int poids; // poids de l’arrête
   Fleche(); // Constructeur par défaut
   Fleche(Sommet, int) ; // Constructeur paramétré
} ;

/* Rayons est une implémentation de liste de flêches */
struct Rayons {
 Fleche fleche ; 
 Rayons * suivant ;
 Rayons(Fleche, Rayons *) ; // constructeur paramétré
} ;

/* Une "étoile" est la réunion d’un sommet et d’une liste de flêches qui en partent*/
struct Etoile {
   Sommet sommet ;
   Rayons * liste ;
} ;

/* Element est l’implémentation d’une liste d’étoiles, qui constitue fondamentalement le graphe.
Elle est séparée de l’objet Graphe qui est chargé de la gestion de cette liste, pour des raisons d’emplacement mémoire…*/
struct Element {
 Etoile sommet ;
 Element * suivant ;
 Element() ; // constructeur par défaut
 Element(Etoile s, Element * lien) ; // constructeur paramétré
} ;
/* MatriceDouble est une structure utile pour la transition entre un graphe sous forme de liste (telle qu'implémentée ci-dessus)
et un graphe implémenté sous forme de matrice : rep[i][j] donne le poids de l’arête qui va de i vers j ; par ailleurs adresse[i]
reverra l’adresse de l’Element correspondant au sommet i*/
struct MatriceDouble {
 int * * rep ;
 Element * * adresse ;
 MatriceDouble(int * * r= NULL , Element * * a =NULL) ; //Constructeur paramétré
 ~MatriceDouble() ; // destructeur
} ;

/* Res est une structure utile uniquement pour le retour des résultats du calcul des plus courts chemins du graphe */
struct Res {
 int taille ; // taille du graphe calculé
 Sommet source ; // source des chemins considérés 
 int * distances ; // distances[i] est la distance totale de la source à i
 int * parcours ; // parcours[i] est le sommet précédent i dans le parcours de la source à i
 Res() ; // constructeur par défaut
 ~Res() ; // destructeur
 void Affiche(FILE * f = stdout) ; // Affiche le résultat (sue l’écran ou dans un fichier)
} ;

/* La classe principale qui implémente l’algorithme de Djikstra */
class Graphe
{
 // Membres
 Element * premier ; // premier élément de la liste qui constitue le graphe
 int taille ; // taille du graphe (nombre de sommets)

 // Fonctions sur entiers + infini (pour les poids)
 static Bool inf_str(int, int) ; // fonction de comparaison sur les entiers et l’infini
 static int somme(int, int) ; // fonction d’addition sur les entiers et l’infini

 // Fonctions internes
 MatriceDouble * matricialisation() ; // Transforme la liste en système de matrice double (explicité ci-dessus)

public :
 // Constructeurs
 Graphe(int * * tab, int n=0) ; // Ce constructeur prend en paramètres une matrice (sur le principe matrice[i][j] est le poids de l’arrête qui relie i à j, -1 signifiant une arête de poids infini), et la taille du graphe à construire
 Graphe(int * donnees, int n) ; // Ce constructeur prend en paramètres un tableau dont le principe est expliqué en bas de page, et la taille n

 // Destructeur
 ~Graphe () ;

 // Algo de Djikstra
 Res * Djikstra(int i) ;

 // Affichage d’un graphe sous forme de texte (à l’écran ou dans un fichier)
 void Affiche(FILE * f=stdout) ;
} ;

/* Explication pour le tableau int * donnees utilisé dans le constructeur de graphe :
le tableau donnee est une forme compressee de graphe, qui fonctionne suivant ce principe :
[n0,s10,p10,…,sn0,pn0,n1,s11,p11,…,sn1,pn1,….,nm,s1m,p1m,…,snm,pnm]
avec 
ni qui désigne le nombre de sommets auquels est relié le sommet i
 sji l’une des sommets auquels est relié i (j variant de 1 à ni)
 pji le poids de l’arête allant de i vers j (j variant de 1 à ni)
et tout ceci avec i variant de 0 à m (la taille du graphe est donc a priori m+1
(a priori seulement, du fait de l’existence de graphes non connexes…)
*/