TD-9, encore les graphes

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/X.97/TD-9/enonce.html

Programmes Prenom.Nom.c à déposer par ftp sur poly en /users/profs/maranget/TD-9.

1 Sortir d'un labyrinthe

La sortie d'un labyrinthe est une illustration très parlante du parcours de graphe. Un labyrinthe, composé de n × m cases numérotées par des couples (i,j), est représenté en machine par un graphe (non orienté) dont les sommets sont étiquetés par des couples (i,j). Lorsqu'une case (i₀,j₀) communique avec une autre case (i₁,j₁), alors il existe un arc entre les sommets (i₀,j₀) et (i₁,j₁) du graphe. En outre, deux cases (et sommets) sont particuliers, ce sont l'entrée et la sortie du labyrinthe. Soit le labyrinthe suivant :

+-+-+-+-+-+-+-+-+
|I| |     |     |
+ +-+ + + + +-+ +
|     | |     | |
+-+ +-+ +-+ + + +
| | | |       | |
+-+ +-+-+-+ + + +
| |     |   | |O|
+-+-+-+-+-+-+-+-+

Il sera représenté par le graphe :

Aller de l'entrée vers la sortie du labyrinthe revient donc à trouver un chemin dans le graphe d'un sommet vers un autre. On commencera pour cela un parcours exhaustif du graphe à partir du sommet entrée, parcours que l'on arrêtera dès que la sortie sera atteinte.

1.1 Représentation machine du graphe

Afin que vous puissiez vous concentrer sur la programmation du parcours, le type des labyrinthes ainsi que les fonction d'entrée/sortie sont donnés.

Un fichier d'en-tête labyio.h, à récupérer, contient les définitions de types et les prototypes des fonctions que vous aurez à utiliser :

/********************************/
/* Sommets et listes de sommets */
/********************************/
typedef struct {
  int i,j;
} Sommet;

typedef struct cell {
  Sommet s;
  struct cell *next;
} *List;

List cons(Sommet s,List next); /* constructeur des listes */

/************************/
/* Type des labyrinthes */
/************************/

#define NMAX 64
#define MMAX 64

typedef struct {
  int n,m;       /* taille */
  Sommet in,out;  /* entree et sortie */
  List port[NMAX][MMAX];
} Laby;

/* Lecture d'un labyrinthe */
Laby read_laby(FILE *fp);

/* Impression d'un labyrinthe */
void print_laby(FILE *fp,Laby laby,List sol);

Remarquez que les labyrinthes sont des graphes représentés en utilisant les listes de voisins. Voici donc les premiers éléments du tableau laby.port dans le cas où le petit labyrinthe donné en exemple est représenté par la variable laby de type Laby :

Remarquez aussi que les labyrinthes comprennent les points d'entrée et de sortie. Les commentaires devrait suffire pour pouvoir utiliser les fonctions cons, read_laby et print_laby.

Pour pouvoir compiler votre programme (c'est à dire produire un fichier objet avec l'extension .obj), qui utilisera le type des labyrinthes et fera des appels à cons, read_laby et print_laby, vous devez y mettre une ligne

#include
"labyio.h"

.

Mais cela ne suffit par, votre exécutable (extension .exe) devra effectivement appeler les fonction déclarées dans labyio.h. Pour cela, il faut disposer du code de ces fonctions et l'inclure dans votre exécutable lors de l'édition de liens. Le source C de ces fonctions se trouve dans le fichier labyio.c. Vous allez procéder de la façon suivante.

Récupérez les deux fichiers labyio.h et labyio.c et placez les dans votre répertoire de travail (non, ce n'est pas C:\Bc5\bin). Vous pouvez récupérer les fichiers avec votre brouteur ou nous demander une disquette. Tant que vous y êtes, récupérez aussi les labyrinthes, le petit et le grand grand.
Créer un nouveau projet de nom, par exemple, laby.ide, qui explicitera que l'exécutable laby.exe dépend à la fois de votre source à vous (disons laby.c) et de labyio.c. Pour ce faire :
- Commencez par créer le projet laby.ie dans votre répertoire de travail, en suivant la procédure habituelle. Ensuite allez voir la fenêtre de projet. Elle contient normalement un arbre de dépendance de ce style :
```
    laby.exe
   |
   +--- laby.c
```
  C'est à dire que l'on obtient laby.exe en compilant laby.c.
- Sélectionner laby.exe, puis appuyer sur le bouton de droite de la souris, un menu apparaît, sélectionner Add Node. Ensuite, intuitez un peu et ajouter un noeud labyio.c. Normalement, vous devez obtenir un arbre projet modifié de ce style :
```
    laby.exe
   |
   +--- labyio.c
   |
   +--- laby.c
```
Il vous reste à écrire votre programme dans laby.c, qui devra contenir une ligne #include "labyio.h" (pour pouvoir connaître le type des labyrinthes et les prototypes de fonctions externes qu'il utilisera). Le fichier laby.c contiendra également la fonction principale du programme, main. Autrement dit, votre fichier source laby.c va ressembler à cela :
```
  ...
#include "labyio.h"
  ...
void main(void)
{
  ...
}
```
Notez bien que, normalement, vous n'avez pas besoin d'aller voir le fichier labyio.c les déclarations de labyio.h devraient vous suffire.

1.2 Votre programme

Votre programme lira d'abord un labyrinthe (par read_laby). Ensuite, il trouvera un chemin de l'entrée vers la sortie, ce chemin sera représenté en machine par la liste des sommets parcourus. Enfin, il affichera sa solution en utilisant print_laby :

+-+-+-+-+-+-+-+-+
|I| |XXX  |XXXXX|
+X+-+X+X+ +X+-+X+
|XXXXX|X|  XXX|X|
+-+ +-+X+-+ +X+X+
| | | |XXXXXXX|X|
+-+ +-+-+-+ + +X+
| |     |   | |O|
+-+-+-+-+-+-+-+-+

Vous disposez de deux labyrinthes, un petit et un grand.

La solution de cet exercice apparaîtra ici, en laby.c.

2 Il vous reste du temps, inondez le labyrinthe

Modifier le programme de recherche de sortie pour calculer la liste de toutes les cases que l'on peut atteindre à partir de l'entrée. L'affichage de la solution donnera alors quelque chose de ce genre :

+-+-+-+-+-+-+-+-+
|I| |X X X|X X X|
+ +-+ + + + +-+ +
|X X X|X|X X X|X|
+-+ +-+ +-+ + + +
| |X| |X X X X|X|
+-+ +-+-+-+ + + +
| |X X X|X X|X|O|
+-+-+-+-+-+-+-+-+

(Pour obtenir cet affichage, il vaut mieux utiliser print_laby2, dont la déclaration est également dans labyio.h.)

La solution de cet exercice apparaîtra ici, en trans.c.

3 Il vous reste beaucoup de temps

Introduire des télétransporteurs dans les labyrinthes. D'une case du labyrinthe marquée par une étoile (*), on peut immédiatement aller à tout autre case également marquée d'une étoile. Ceci revient à rajouter quelques arcs au graphe. Par exemple, considérons le labyrinthe :

+-+-+-+-+-+-+-+-+
|I|       |     |
+ +-+ + + + +-+-+
|  *  | |     |*|
+-+ +-+ +-+ + + +
| | | |       | |
+-+ +-+-+-+ + + +
| |  *  |   | |O|
+-+-+-+-+-+-+-+-+

Alors, une solution possible utilisant le télétransporteur est :

+-+-+-+-+-+-+-+-+
|I|       |     |
+X+-+ + + + +-+-+
|X *  | |     |*|
+-+ +-+ +-+ + +X+
| | | |       |X|
+-+ +-+-+-+ + +X+
| |  *  |   | |O|
+-+-+-+-+-+-+-+-+

Pour faire cet exercice, vous devrez modifier les fonctions de lecture et d'affichage des labyrinthes. En revanche, votre recherche de chemin du premier exercice fonctionnera sans modification, si elle est bien écrite.

Ce document a été traduit de L^AT_EX par H^EV^EA.