Graphes et tas

Deux types de structures de données sont nécessaires pour traiter de façon agréable le problème : les graphes, qui sont une représentation instinctive et mathématique des réseaux considérés, et les tas, files de priorité qui organisent les éléments d’un ensemble muni d’une relation d’ordre et qui permettront de comparer rapidement les longueurs d’un ensemble de chemins.

Les Graphes

Définition mathématique

Un graphe est la donnée d’un quadruplé {S,A,X,F}@@@ avec:

  • S un ensemble fini non vide des sommets du graphe (les points)
  • A une partie de SxS dont les éléments forment les arêtes du graphe (les liaisons)
  • X un ensemble quelconque, fini ou non, qui détermine les poids possibles des arêtes
  • F la fonction de valuation du graphe qui à chaque arête associe son poids

Schématiquement, voici une représentation classique d’un graphe :

Schema classique d’un graphe : Sommets reliés par des fleches, assortis d’un nombre determinant leur poids

Dans cet exemple, on a:

  • S: {d,a,o,u,s,t}
  • A: {(d,d),(d,a),(a,o),(a,u),(o,u),(u,s),(s,o),(s,t),(t,s)}
  • X: les entiers naturels
  • F peut être représentée par la matrice suivante :
    Matrice de la fonction de valuation
    u->v d a o u s t
    d 1 2
    a 1 7
    o 3
    u 1
    s 4 3
    t 5

On dit que le graphe est symétrique si la matrice de F est symétrique, c'est-à-dire si toutes les liaisons peuvent être parcourues dans les deux sens.

On appelle chemin de a à b toute suite finie (u0,u1,…,un) telle que u0=a, un=b et telle que quelque soit i, 1<i<=n, (ui-1,ui) appartient à A. On dit que le graphe est connexe si pour tout couple de sommets distincts (a,b), il existe un chemin de a à b.

Nous nous limiterons par la suite aux graphes composés d’arêtes de poids positifs.

Implémentation matricielle

Il suffit de reprendre l’exemple précédent pour s'apercevoir que la simple donnée de la matrice de suffit pour reconstruire le graphe en entier (du moins si on attribue un numéro à chacun des sommets). Ainsi, une idée simple consiste à définir un graphe comme la matrice des transitions (en convenant d’un symbole, dans notre cas -1, lorsque l’arête n’existe pas). On obtient donc quelque chose comme ceci :

Representation matricielle du graphe de l’exemple precedent
1 2 -1 -1 -1 -1
-1 -1 1 7 -1 -1
-1 -1 -1 3 -1 -1
-1 -1 -1 -1 1 -1
-1 -1 4 -1 -1 3
-1 -1 -1 -1 5 -1

Les calculs à effectuer sur le graphe sont alors extrêmement simples : (i,j) est le poids de l’arête qui relie le sommet i au sommet j. L’inconvénient majeur de ce type de structure de données, c'est qu'elle tient une place mémoire considérable. En fait, pour coder un graphe avec O(n) de données, on utilise une place mémoire en O(n2) puisqu'on est obligé de coder toutes les arêtes, qu'elles existent ou non. De plus, supposons qu'une nouvelle gare se crée ou que suite à des ennuis techniques, une gare soit fermée, il faut adapter le graphe en conséquence, et une matrice est par définition statique, la taille étant fixée une bonne fois pour toutes à l’initialisation.

Implémentation avec des listes

Pour palier à ces deux problèmes, on se tourne vers des structures dynamiques : les listes chaînées. Un graphe apparaît alors comme une liste d’étoiles, chaque étoile étant composée d’un sommet et de la liste des arêtes qui ont ce sommet comme origine :

Une etoile est un sommet et la liste des aretes qui ont ce sommet pour origine : un sommet represente par un carre avec un label, et les arretes qui ont ce sommet pour origine representees par des fleches assorties d’un poids

Dans ce cas, la gymnastique à effectuer pour implémenter la structure est plus poussée, mais on ne code plus que pour les arêtes effectives donc le gain d’espace mémoire est considérable. De plus, l’ajout ou la suppression d’un élément se fait relativement sans problème. Seul point noir : faire des calculs sur les poids des arêtes relève de la haute voltige…

Regardons cette structure de plus près (se reporter en Annexe pour le détail des fonctions, excepté pour Dijkstra qui va bien sûr être décortiqué par la suite):

   


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é
} ;

La classe principale qui implémente l’algorithme de Dijkstra

   


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 Dijkstra
	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…)
*/

Passage d’une représentation à l’autre

En pratique, on utilise la représentation avec des listes pour stocker le graphe, car c'est elle qui occupe le moins d’espace mémoire, et dès qu'il s'agit de passer aux calculs, on transforme le graphe en matrice pour éviter des parcours de listes redondants et coûteux ; d’où la nécessité de définir une fonction de « matricialisation » pour transformer nos listes en matrice. Qui plus est, afin d’assurer un algorithme de coût minimal, il est nécessaire de connaître l’adresse de l’étoile à laquelle est rattaché un sommet i. La fonction de matricialisation renvoie donc, outre la matrice du graphe, le tableau d’adresses de ces étoiles.

En C++, on définit ainsi le type MatriceDouble:

  • rep[i][j] donne le poids de l’arête qui va de i vers j
  • adresse[i] renverra 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
} ;
MatriceDouble * Graphe::matricialisation()
{
	int ** rep = new int * [taille] ;
	for (int i=0 ; i<taille ; i++)
		rep[i]=new int [taille] ;
	Element ** adresse = new Element *[taille] ;

	// Initialisation
	for (i=0 ; i<taille ; i++)
	{
		for (int j=0 ; j<taille ; j++)
		{
			if (i!=j)
				rep [i][j] = -1 ;
			else rep [i][i] = 0 ;
		}
	}
	for (Element * l = premier ; l!=NULL ; l=l->suivant)
	{
		/* Parcours des arêtes liées à chaque sommet */
		for (Rayons * s=l->sommet.liste ; s!=NULL ; s=s->suivant)
		{
			rep [l->sommet.sommet] [s->fleche.extrem]=s->fleche.poids ;
		}
		adresse[l->sommet.sommet]= l ;
	}
	return (new MatriceDouble(rep, adresse)) ;
}