Un graphe est une structure mathématique définie par :
Intuitivement, les arcs décrivent des relations entre sommets, en spécifiant comment on peut passer d'un sommet à l'autre. Par exemple, on peut voir une carte routière comme un graphe (il s'agit généralement d'un graphe non orienté, c'est-à-dire tel que, si l'arc (x,y) appartient à A, alors il en va de même pour (y,x)). Les sommets sont alors les intersections, et les arcs sont les portions de routes comprises entre deux intersections successives. On utilise bien souvent la représentation graphique ci-dessous, qui en donne une présentation intuitive.
Généralement, on attache des informations aux nœuds et aux arcs. On parle alors de graphes étiquetés. Par exemple, on pourra associer un nom aux nœuds représentant des intersections et une valeur entière à chaque arc, correspondant à la distance couverte par la portion de route que celle-ci décrit.
Le graphe ci-dessous définit une carte routière très simplifiée des alentours de l'École Polytechnique (il s'agit d'un graphe non orienté) :
En pratique, les graphes ont de très nombreuses applications, en informatique et dans d'autres domaines :
Au cours de ce TD, nous nous proposons de programmer quelques algorithmes classiques sur les graphes, en utilisant tout d'abord une représentation très simple (mais peu efficace), que l'on pourra ensuite améliorer. Le texte du TD vous guide moins que les TDs précédents ; il est donc normal que vous ayiez à définir vous même la structure de votre programme.
Il est généralement préférable d'associer à chaque nœud les arcs sortants. Cela suggère la représentation suivante :
Définir les classes suivantes :
Pour chaque classe, on pourra ajouter un constructeur (dont vous devrez choisir les arguments).
Pour pouvoir tester chacune de vos fonctions, vous allez avoir besoin d'afficher des graphes. Pour cela, écrire un ensemble de fonctions d'affichage chaque composant du graphe (on pourra également opter pour la conversion de chaque composant vers une chaîne de caractères, en utilisant le format de la méthode toString).
Avant d'écrire des fonctions manipulant des graphes, nous devons en construire, et nous vous proposons pour cela d'utiliser des graphes fournis sous la forme de fichiers texte. Nous vous fournissons une fonction qui va se charger de la lecture de ces fichiers, en utilisant deux fonctions sur les graphes que vous devez d'abord écrire :
Pour décrire les graphes, nous avons choisi le format ci-dessous :
n oriente origine_1 destination_1 distance_1 origine_2 destination_2 distance_2 ... origine_n destination_n distance_n
Plus précisément, n est le nombre d'arcs et oriente est un booléen qui détermine si le graphe est orienté ou non. Ensuite, le fichier contient la liste des arcs décrits par le nom du nœud "origine", le nom du nœud "destination" et la distance associée à l'arc. Dans le cas d'un graphe non orienté, chaque ligne du fichier correspond à deux arcs dans le graphe. Nous vous fournissons la fonction de lecture ci-dessous, que vous pourrez intégrer à la classe principale de votre projet :
static Graphe lireGraphe( String name ){
TC.lectureDansFichier( name );
int num = TC.lireInt( );
String oriente = TC.lireMot( );
TC.lireLigne( );
boolean isoriente = oriente.equals( "true" );
Graphe g = new Graphe( );
for( int i = 0 ; i < num ; i++ ){
String nsrc = TC.lireMot( );
String ndst = TC.lireMot( );
int dist = TC.lireInt( );
Noeud src = g.extraireNoeud( nsrc );
Noeud dst = g.extraireNoeud( ndst );
src.ajouterArc( dst, dist );
if( !isoriente )
dst.ajouterArc( src, dist);
TC.lireLigne( );
}
return g;
}
Vous pourrez tester votre programme avec les graphes suivants : graph0.txt (graphe à 5 sommets), graph1.txt (graphe à 10 sommets), td789.txt (graphe de classes), routes.txt (graphe de routes), automate.txt (un automate simple : tâches à accomplir pour valider le cours), inf321.txt (liens entre les pages du cours). On recommande également d'ajouter vos propres exemples. Dans chaque cas, pensez à afficher le graphe qui a été lu et à le comparer avec le fichier initial.
Nous allons à présent passer à quelques algorithmes classiques sur les graphes.
Écrire une fonction prenant un nœud d'un graphe en paramètre, et calculant l'ensemble des sommets atteignables depuis ce nœud, c'est-à-dire que l'on peut rejoindre en suivant zéro, un, ou plusieurs arcs. Pour représenter un ensemble de nœuds, on pourra utiliser une liste. Faire attention à garantir la terminaison de votre programme (il faut en particulier éviter de traiter deux fois un même nœud) : pour cela, on pourra rajouter un champ booléen à chaque sommet. Tester cette fonction à l'aide des exemples fournis (ou d'autres exemples).
En vous inspirant de la fonction précédente, écrire une fonction prenant en paramètre un graphe étiqueté g et un nœud n, et calculant pour chaque nœ n' qui peut être atteint depuis n, la distance minimale à parcourir depuis n pour atteindre n'. On pourra à nouveau ajouter un champ à la classe Noeud.
Nous avons vu que la représentation graphique des graphes les rendait plus simples à comprendre. Nous vous proposons donc d'afficher vos graphes en utilisant le langage DOT. Pour cela, il faut écrire une autre fonction d'affichage, produisant un texte décrivant le graphe dans le langage DOT (ce texte sera sauvegardé dans un fichier). Ensuite, il faut convertir le fichier texte obtenu vers une image à l'aide de la commande dot (vous pouvez vous référer au manuel de cette application en faisant man dot).
Les structures de données que nous avons utilisées au cours de ce TD ne sont pas optimales. En particulier, la recherche d'un nœud nécessite de parcourir la liste de tous les nœuds du graphe.
Par quelle structure de données vue lors d'un TD précédent pourrions nous remplacer cette liste ? Choisir une structure de données plus efficace et mettre à jour votre code. On pourra soit re-programmer la nouvelle structure de données en s'inspirant du TD précédent, soit utiliser la bibliothèque standard.