Consignes

Le TP est à rendre (par email) pour le lundi 30 novembre à 8h00.

Pour ce TP comme pour les suivants, la pièce la plus importante sera un fichier tp1-nom-prenom.c contenant votre programme. Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront également pris en compte :

la lisibilité de votre programme (choix pertinent pour les noms de variables, indentation etc.),
la présence de commentaires aux endroits appropriés,
...

Les réponses aux questions posées dans le TP (complexité de vos fonctions par exemple) seront insérées comme commentaires dans votre fichier principal.

Si vous le souhaitez, vous pouvez aussi m'envoyer un rapport de TP. Le format de ce rapport sera au choix, mais par ordre de préférence :

dans le corps de votre programme en commentaire,
au format texte (mais avec un minimum de mise en page),
au format pdf,
au format OpenOffice (.odt),
au format Word (beurk).

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

chaque fichier devra comporter un commentaire au début avec vos nom, prénom, filière, intitulé du cours et numéro du TP,
votre code final devra compiler avec les options de compilation -Wall -Werror -Wextra -pedantic -std=c99
une exécution du programme de test fourni ne devra pas provoquer d'erreur.

Liens utiles

Ajouts

Remarques complémentaires

Quelques trucs que j'avais oublié de préciser dans le sujet

Tiles 1 :

pour tester si une tile (file ou pile) est vide, vous pouvez soit télécharger la nouvelle version de l'archive et utiliser la fonction de prototype

int tileEstVide(Tile T);

soit insérer à la main la définition de tileEstVide() dans votre fichier :

int tileEstVide(Tile T) {
  return(T->dernier == NULL) ;
}

Tiles 2 :

pour le moment, vous n'avez besoin que de files de sommets (entiers). Les tiles sont des listes chaînées d'arcs, avec une origine, un but et un poids. Vous n'avez donc qu'à utiliser un des champs des tiles et vous pouvez ignorer les autres. D'autre part, la fonction defile() utilise un pointeur. Vous utiliserez donc les files de la manière suivante :

pour déclarer une file et l'initialiser à la file vide :
```
Tile F = tileVide() ;
```
pour insérer un sommet t dans la file F :
```
entile(t, 0, 0, F) ;
```
Remarquez que je mets 0 en arguments 2 et 3 car je n'en ai pas besoin. (Je pourrais tout aussi bien mettre 42...)
pour défiler le premier élément de la file F dans la variable t (de type int) :
```
defile(F, &t, NULL, NULL) ;
```
Le « & » devant le t vient du fait que l'on veut récupérer la valeur dans la variable t : on doit donc passer l'adresse de t. Pour les arguments 3 et 4, on peut passer le pointeur NULL car on ne demande pas leurs valeurs.

Remarque générale :

à aucun moment vous n'avez besoin d'utiliser L->origine dans ce TP : vous pouvez l'ignorer complètement car les listes d'adjacence sont des listes de sommets. De la même manière, vous pouvez pour le moment ignorer les poids...

1. Préliminaires

Avant de commencer

Récupérer les fichiers

Téléchargez l'archive du TP1. Après un

$ tar xvf info505-tp1.tar

vous devriez avoir un répertoire info505-tp1 contenant plusieurs fichiers :

graphes.h : les entêtes et les types pour les fonctions prédéfinies sur les graphes,
graphes.o : le fichier objet correspondant,
tp1.h : le fichier d'entêtes pour les fonctions que vous devrez faire pour le TP1,
tp1-hyvernat-pierre.c : le fichier squelette pour le TP1,
test.c : une fonction main minimale pour tester vos fonctions,
Makefile : mon fichier Makefile,
tp1.txt : le sujet du TP au format texte,
G1, G2, G3 et G4 : des petits exemples de graphes.

Compiler

Vous ne devez pas modifier les fichiers graphes.h ou tp1.h. Le fichier sur lequel vous travaillerez est tp1-nom-prenom.c. Un exemple de tels fichier est inclus dans l'archive : tp1-hyvernat-pierre.c. Vous pouvez l'utiliser comme point de départ.

Pour la compilation, le plus simple est d'utiliser le fichier Makefile fournit. Il suffit de l'ouvrir dans un éditeur de texte et de modifier la ligne

NOM = tp1-hyvernat-pierre

pour mettre votre nom et prénom à la place. (Attention, il faut que votre fichier s'appelle tp1-nom-prenom.c.) Ensuite, il suffit d'utiliser la commande $ make pour recompiler tout votre TP.

Tester

Votre fichier tp1-nom-prenom.c ne contient pas de fonction main : celle ci se trouve dans le fichier test.c. Pour tester vos fonctions au fur et à mesure, vous pouvez :

modifier la fonction main du fichier test.c,
créer un nouveau fichier de test (avec sa propre fonction main) et modifier la ligne
```
TEST = test
```
dans le fichier Makefile.

Le fichier Makefile produit automatiquement un exécutable test qui contient le code de la fonction main.

Envoyer

Avant d'envoyer votre fichier tp1-nom-prenom.c, ajoutez l'option de compilation -Wextra dans le fichier Makefile et testez sur la fonction de test originale. (C'est ce que je ferais...)

1.1. La bibliothèque

Pour le moment, vous n'avez la bibliothèque de graphes qu'au format binaire (fichier graphes.o), pour une architecture Intel 32 bits (libs/graphes-32.o) ou 64 bits (libs/graphes-64.o). Le fichier graphes.o est en fait un lien symbolique vers la version appropriée...

Lisez le début du fichier graphes.h pour voir un peu quelles fonctionnalités vous sont fournies.

La bibliothèque propose deux types de données pour les graphes :

GrapheListe pour un graphe représenté sous forme de listes d'adjacences,
GrapheMatr pour un graphe représenté sous forme de matrice d'adjacence.

Dans les deux cas, si G est un graphe, vous avez accès au nombre de sommets avec G->nb_sommets. Pour accéder au tableau de listes d'adjacences, il faut faire G->Adj et pour accéder à la matrice, il faut faire G->Matr.

Les listes d'adjacences sont des listes chaînées :

la liste vide est NILL (une macro pour le pointeur NULL),
si L est une liste, le premier sommet de L est L->but, et la suite de L est L->suivant.

Pour accéder à un élément de la matrice, on utilise G->Matr[i][j].

On stocke également un poids (nombre entier) pour chaque arc. Dans le cas d'une matrice d'adjacence, le poids est stocké directement dans la matrice ; dans le cas d'une liste d'adjacence, on stocke le poids du premier arc dans L->poids.

Vous avez du voir la notation G.Adj pour accéder au champs Adj dans G. La notation G->Adj fait la même chose quand G est un pointeur. C'est donc un synonyme de (*G).Adj. Vous devriez voir tout ça dans votre cours de C...

Le fichier graphes.h vous donne également les prototypes de quelques fonctions pour manipuler ces types :

ajoute() pour ajouter un arc dans une liste,
grapheListeVide() pour initialiser un graphe vide (listes d'adjacences),
grapheMatrVide() pour initialiser un graphe vide (matrice d'adjacence),
grapheListeAleatoire() pour créer un graphe aléatoire,
lireGrapheListe() pour lire la description d'un graphe dans un fichier.

Reportez-vous aux commentaires dans ce fichier pour savoir comment utiliser ces fonctions.

Le fichier contient également un type de données Tile, qui permet de faire des piles ou des files d'arcs :

on rajoute un arc avec la fonction entile(),
on défile avec la fonction defile(),
on dépile avec la fonction depile().

Attention : un graphe contient des données mutables (modifiables). Vous ne devez pas modifier un graphe lorsque vous le donnez en argument à une fonction.

Attention (bis) : vous n'avez pas encore vu les pointeurs, ni le lien entre pointeurs et tableaux dans le langage C. Pour ce TP, vous pouvez considérer que le type int* veut dire tableau d'entiers de taille inconnue. Par exemple, le prototype

int* distances (GrapheListe G, int a);

veut dire que la fonction renvoie un tableau d'entiers.

Pour allouer un tableau dynamique (dont la taille n'est pas connue à la compilation) non local à une fonction (sur lequel on veut faire un return), il faut utiliser la syntaxe suivante :

  int *sommets = malloc(n * sizeof(int));

qui permet d'allouer un tableau de n entiers dans le tas. Ce tableau a donc une durée de vie supérieure à la fonction dans lequel il est défini.

Une déclaration int sommets[n] déclarerait le tableau dans la pile, et disparaîtrait donc hors de la fonction... (Ceci n'est valide qu'à partir de la norme C99.)

1.2. Affichage sommaire d'un graphe

Écrivez une fonction de prototype

void afficheGrapheListe (GrapheListe) ;

qui affiche les arcs d'un graphe à l'écran.

1.3. Conversion entre les deux types de données

Écrivez les deux fonctions de conversion

GrapheMatr listeVersMatrice(GrapheListe) ;
GrapheListe matriceVersListe(GrapheMatr) ;

pour passer d'un type à l'autre.

N'oubliez pas de tester vos fonctions...

1.4. Inversion des arcs d'un graphe

Écrivez une fonction

GrapheListe transpose(GrapheListe) ;

qui à partir d'un graphe, calcul son transposé : tous les arcs sont en sens inverse.

Qu'elle est la complexité de votre fonction, en fonction de n (nombre de sommets) et m (nombre d'arc) ?

2. Parcours en largeur

2.1. Parcours

Programmez l'algorithme du parcours en largeur vu en cours.

Pour changer un peu, au lieu de renvoyer un tableau pere[] contenant la foret du parcours, renvoyez un graphe Pere. (Une foret est un type particulier de graphe...)

Le prototype de votre fonction est donc

GrapheListe parcoursLargeur (GrapheListe G) ;

2.2. Calcul de distances

Programmez une fonction

int* distances(GrapheListe G, int a) ;

qui renvoie le tableau des distance du sommet a vers tous les autres sommets (ou -1 s'il n'y a pas de chemin approprié.)

Déduisez-en une fonction

int distance(GrapheListe G, int a, int b) ;

qui renvoie la distance entre les sommets a et b dans le graphe G.

Qu'elle est la complexité de votre fonction, en fonction de n (nombre de sommets) et m (nombre d'arc) ?

2.3. Calcul du diamètre (Bonus)

Le diametre d'un graphe, c'est le maximum de toutes les distances entre les sommets du graphes...

(Bonus) Écrivez une fonction

int diametre(GrapheListe G, int *a, int *b) ;

qui calcule le diamètre d'un graphe, et met deux sommets le plus éloignés possible dans a et b.

Qu'elle est la complexité de votre fonction, en fonction de n (nombre de sommets) et m (nombre d'arc) ?

Cette fonction prend en argument deux pointeurs vers des entiers. Elle n'utilise pas les valeurs entières correspondantes mais les modifie pour donner les numéros des sommets.

Votre fonction se terminera donc probablement par quelque chose comme :

int diametre(GrapheListe G, int *a, int *b) {
  ...
  ...
  *a = s1 ;
  *b = s2 ;
  return(d) ;
}

Et vous l'appellerez de la manière suivante :

  ...
  int d, s, t ;
  d = diametre(G, &s, &t) ;
  printf("Le graphe a un diamètre de %i ;
          %i et %i sont deux sommets éloignés de cette distance.\n",
             d, s, t) ;
  ...

(C'est le même principe que dans un scanf().)

3. Résolution de labyrinthes

Un labyrinthe peut être vu comme un graphe non-orienté : chaque sommet est une pièce et les arêtes sont des portes.

Si on impose qu'il y ait exactement un chemin entre chaque pièce, le graphe du labyrinthe est en fait un arbre...

Écrivez une fonction

int* resoudLabyrinthe(GrapheListe G, int entree, int sortie) ;

qui parcourt le graphe G à partir du sommet entree et cherche un chemin vers le sommet sortie.

Votre fonction renverra le morceau du tableau pere[] créé par le parcours.

Écrivez une petite fonction afficheChemin(int *pere, int entree, int sortie) qui affiche les sommets pour aller de entree à sortie en utilisant l'information contenue dans le tableau pere. Par exemple :

 - départ du sommet 12,
 - aller au sommet 5,
 - aller au sommet 6,
 - aller au sommet 22,
 - aller au sommet 0,
 - arrivée au somme 42 !

Que pensez-vous de cette méthode pour résoudre un labyrinthe « à la main » ?

Pour tester votre fonction, vous pouvez aussi utiliser les fonctions un peu plus visuelles suivantes :

labyrintheRect() et afficheGrilleRect(),
labyrintheHex() et afficheGrilleHex(),

qui permettent de créer et d'afficher un labyrinthe sur une grille rectangulaire ou hexagonale :

    +--+--+--+--+--+--+--+--+--+--+                __    __    __    __    __
    |  |  |              |     |  |               /  \__/  \__/  \__/  \__/  \__
    +  +  +  +--+  +--+--+--+  +  +               \  /  \        /   __/   __   \
    |        |        |           |               /   __   \__/  \__    __/  \__/
    +  +--+  +--+  +  +--+  +--+--+               \__/        \__/  \      __   \
    |  |     |  |  |           |  |               /  \__/  \__   \     \__/  \__/
    +  +--+--+  +  +--+--+  +--+  +               \__    __   \  /  \__/   __   \
    |        |     |     |  |     |               /   __/  \__/   __/  \  /   __/
    +  +  +--+--+--+--+  +  +  +  +               \__/   __    __/  \  /  \__   \
    |  |  |     |        |     |  |               /        \__   \__   \__/  \  /
    +  +--+  +--+  +--+--+--+--+  +               \__/  \__/  \__/   __/  \__   \
    |     |  |  |  |        |     |               /   __      /   __/  \  /     /
    +--+--+  +  +  +--+  +--+  +--+               \__/  \__/   __/  \  /  \__/  \
    |                    |        |               /   __   \        /   __/  \  /
    +  +  +--+--+--+--+--+--+--+  +               \__/  \__   \__/   __/   __   \
    |  |     |           |        |               /  \__   \__/         __/  \  /
    +  +--+--+--+  +--+--+  +--+--+               \__    __   \__/  \__   \  /  \
    |              |              |               /   __/   __/  \__/  \__   \  /
    +--+  +--+  +  +--+--+  +--+  +               \__/   __/   __    __    __/  \
    |        |  |              |  |               /     /   __   \  /  \  /  \  /
    +--+--+--+--+--+--+--+--+--+--+               \__/   __/   __/   __/   __/  \
                                                     \__/  \__/  \__/  \__/  \__/

Modifier votre fonction afficheChemin() pour qu'elle produise un tableau S[] utilisable par les fonctions afficheGrilleRect() et afficheGrilleHex().

TP1 : préliminaires, parcours en largeur et résolution de labyrinthe

info-505 : graphes et algorithmes (Pierre Hyvernat)

18/11/2009

Consignes

Liens utiles

Ajouts

1. Préliminaires

Avant de commencer

Récupérer les fichiers

Compiler

Tester

Envoyer

1.1. La bibliothèque

1.2. Affichage sommaire d'un graphe

1.3. Conversion entre les deux types de données

1.4. Inversion des arcs d'un graphe

2. Parcours en largeur

2.1. Parcours

2.2. Calcul de distances

2.3. Calcul du diamètre (Bonus)

3. Résolution de labyrinthes