3MM1LDB TP

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)


Alternance.png  Alternance  CDROM.png  Informatique 

Fleche gauche.png
Fleche haut.png
Fleche droite.png

Introduction

On va travailler pendant 2 séances sur un mini-TP portant sur des graphes. Ce TP a une vocation d'entrainement : il ne s'agit pas d'un projet réaliste (ça sera le but du mini-projet à la fin du cours).

L'énoncé de ce TP est volontairement peu guidé : c'est à vous de faire vos choix d'implantation. Il n'existe pas de meilleure solution, l'important est d'obtenir un code fonctionnel et bien présenté à la fin de la séance.

On attend bien sûr de vous que vous utilisiez tout ce qu'on a vu dans les séances précédentes pour produire un code bonne qualité et robuste (assertions, modules, etc.).

Structures de données

Définitions

Un exemple de graphe orienté cyclique

Un graphe est une structure de données composée :

  • de noeuds contenant des valeurs : dans notre cas, il s'agira d'entiers sur 32 bits entre 0 et 9 inclus ;
  • d'arêtes reliant certains noeuds les uns aux autres : ces arêtes peuvent être étiquetées avec des valeurs (on parle souvent de poids).

Les arêtes peuvent être orientées : cela signifie que l'existence d'une arête entre un noeud A et un noeud B n'implique pas l'existence d'une arête entre B et A (pensez à une rue en sens unique).

Un graphe peut contenir ou non des cycles (on parle de graphe acyclique s'il n'en contient pas).

On peut autoriser un graphe à contenir des arêtes multiples, c'est à dire qu'il peut exister plusieurs arêtes entre le noeud A et le noeud B par exemple (les arêtes en question seront alors fréquemment étiquetées avec des poids différents).

Dans le cas de ce TP, on travaillera avec des graphes

  • orientés ;
  • cycliques ;
  • sans arêtes multiples ;
  • sans étiquette sur les arêtes (ou dit autrement, toutes les arêtes auront le même poids).

Arbitrairement et pour se simplifier la vie, on décide que les noeuds contiendront des valeurs entre 0 et 9 inclus, sans répétition de valeur entre différents noeuds. On impose une contrainte supplémentaire : s'il existe N noeuds dans le graphe, alors il contiendra toutes et uniquement les valeurs entre 0 et N - 1;

La figure de droite est un exemple du type de graphe sur lequel on va travailler.

Implantation

Il existe de nombreuses façon de représenter un graphe en mémoire, chacune ayant ses avantages et inconvénients en terme d'espace mémoire occupé et de rapidité d'accès ou de modification des données contenues.

Dans ce TP, on choisira de représenter un graphe comme une structure contenant :

  • le nombre de noeuds de l'arbre ;
  • un tableau de booléen à deux dimensions représentant les arêtes du graphe.

Ce tableau sera rempli selon la règle simple suivante : il existe une arête entre le noeud A et le noeud B ssi arete[A][B] == true.

En C, on va donc écrire simplement :

#define NBR_MAX_NOEUDS 10

struct graphe_t {
    uint32_t nbr_noeuds;
    bool aretes[NBR_MAX_NOEUDS][NBR_MAX_NOEUDS];
};

On notera que dans notre représentation du graphe la notion de noeud n'est pas matérialisée dans le code C, car elle nous sera en pratique inutile, notamment grâce aux contraintes imposées sur les valeurs des noeuds.

Fonctions à implanter

Module de gestion d'un graphe

On demande d'implanter un module de gestion de graphes tels que définis plus haut. On devra implanter au moins les fonctions suivantes :

  • struct graphe_t *nouv_graphe() : crée un graphe vide, en allouant toutes les structures de données dynamiques nécessaires ;
  • void detruire_graphe(struct graphe_t **graphe) : détruit le graphe en désallouant toutes ses structures de données allouées dynamiquement, et force le pointeur à NULL pour plus de sécurité ;
  • void afficher_graphe(struct graphe_t *graphe) : affiche le contenu du graphe, ce qui sera utile notamment pour aider à la mise au point des programmes ;

Dans le cas du graphe donné en exemple plus haut, l'affichage pourra être par exemple de la forme :

0 -> 1 2 3 
1 -> 4 
2 -> 3 
3 -> 5 
4 -> 
5 -> 0 4 
6 -> 8 
7 -> 6 8 
8 -> 0 7 
  • struct graphe_t *lire_graphe(char *nom) : lit un graphe décrit dans le fichier dont le nom est passé en paramètre, crée la structure de donnée correspondante et l'initialise en fonction du contenu du fichier ;

On utilisera le format de fichier du logiciel GraphViz, intéressant pour sa simplicité. Un fichier GraphViz (.gv) est un simple fichier texte rempli avec une syntaxe très simple (qu'on ne détaillera pas ici).

Le graphe donné en exemple plus haut peut être obtenu en créant un fichier texte graphe.gv contenant :

digraph {
    7 -> 6;
    6 -> 8;
    7 -> 8;
    8 -> 0;
    8 -> 7;
    0 -> 1;
    0 -> 2;
    0 -> 3;
    1 -> 4;
    2 -> 3;
    3 -> 5;
    5 -> 4;
    5 -> 0;
}

Si vous voulez générer le PDF correspondant à ce graphe, vous pouvez taper dot -Tpdf -Gmargin=0 graphe.gv -ographe.pdf.

La première ligne décrit le type de graphe (ici un directed-graph, c'est à dire un graphe orienté). Ensuite, on trouve la description des noeuds et des arêtes.

La fonction à écrire doit donc analyser le fichier texte : on ne vous demande pas de faire une analyse syntaxique poussée, on considèrera notamment que le fichier donné est sensé avoir la bonne syntaxe (vous pouvez donc implanter une gestion minimale des erreurs).

  • void trouver_un_chemin(struct graphe_t *graphe, uint32_t src, uint32_t dst) : cette fonction trouve un chemin entre les noeuds src et dst s'il existe ;

Cette fonction doit être implantée de façon récursive. Si le chemin existe, il doit être affiché à l'écran, sinon on affichera un message du type "aucun chemin trouve". On n'impose pas de contrainte sur quel chemin on doit trouver s'il existe : en pratique, on trouvera vraisemblablement simplement le premier.

Indications : un algorithme général du parcours récursif du graphe peut se résumer comme suit :

si src == dst alors
    -> on a trouve
sinon
    marquer_noeud(src)
    pour chaque noeud i du graphe faire
        si le noeud i n'est pas deja marque alors
            s'il existe une arete entre src et i alors
                s'il existe un chemin entre i et dst alors
                    -> on a trouve
                fin si
            fin si
    fin faire
    -> pas de chemin
fin si 

Marquer un noeud consiste simplement à mettre à vrai un booléen indiquant qu'on est déjà passé par ce noeud : dans un graphe contenant des cycles, c'est nécessaire pour garantir que la fonction va bien s'arrêter dans le cas où il n'existe pas de chemin.

Pour afficher le chemin, on peut commencer par ajouter des traces lors du parcours : mais vu la structure de l'algorithme, on se rend rapidement compte que le chemin est affiché à l'envers. Pour remédier à ce problème, on peut utiliser une pile comme expliqué plus bas.

  • void trouver_plus_court_chemin(struct graphe_t *graphe, uint32_t src, uint32_t dst) : cette fonction trouve le (ou un s'il en existe plusieurs) plus court chemin entre les noeuds src et dst.

Cette fonction doit être écrite de façon itérative. Si le chemin existe, il doit être affiché à l'écran, sinon on affichera un message approprié.

Indications : on pourra s'inspirer de l'algorithme de parcours proposé par Edsger W. Dijkstra en 1959. Le principe général de cet algorithme est le suivant :

fifo = nouv_fifo()
marquer_noeud(src)
ajouter(src, fifo)
tant que fifo n'est pas vide faire
    n = retirer(fifo)
    si n == dst alors
        -> on a trouve
    sinon
        pour chaque noeud i du graphe faire
            si le noeud i n'est pas deja marque alors
                s'il existe une arete entre n et i alors
                    marquer_noeud(i)
                    ajouter(i, fifo)
                fin si
            fin si
        fin faire
    fin si
fin faire
-> pas de chemin

On voit que cet algorithme nécessite l'utilisation d'une file FIFO (comme définie plus bas), pour permettre le parcours par niveau du graphe (plutôt qu'en profondeur d'abord comme dans le cas de l'algorithme récursif précédent).

Pour l'affichage du chemin, il sera utile d'ajouter une structure de donnée mémorisant le noeud précédent de chaque noeud visité, au fur et à mesure du parcours, afin de pouvoir retrouver le chemin en partant du noeud final. Ce chemin sera évidemment inversé donc on pourra utiliser la même technique que dans la fonction précédente, en introduisant une pile.

Vous devez bien sûr en plus écrire un programme principal pour tester votre module de gestion de graphes.

Module de gestion d'une pile

On va implanter un module de gestion d'une pile bornée d'entiers naturels sur 32 bits. On vous impose également de stocker les éléments de cette pile dans un tableau (pas une structure chainée).

On rappelle qu'une pile est une structure de donnée permettant de stocker et d'extraire des valeurs en respectant la propriété suivante : lorsqu'on extrait une valeur, la valeur renvoyée est la plus récente ayant été insérée (pensez à une pile d'assiettes : on commence par enlever celle du haut).

Le module de gestion d'une pile qu'on va utiliser doit supporter au moins les trois opérations suivantes :

  • struct pile_t *nouv_pile(uint32_t capacite) : crée une pile de capacité maximum donnée (donc allouer l'espace mémoire nécessaire et initialiser les champs pertinents) ;
  • void push(uint32_t val, struct pile_t *pile) : empile une valeur val dans la pile ;
  • uint32_t pop(struct pile_t *pile) : dépile une valeur de la pile ;
  • void detruire_pile(struct pile_t **) : détruit la pile, c'est à dire libère toutes les structures de données allouées dynamiquement et force le pointeur sur la pile à NULL pour plus de sécurité.

Bien sûr, vous pouvez rajouter toutes les fonctions qui vous paraissent nécessaires (par exemple pour tester si la pile est vide ou pleine, pour afficher son contenu, etc.).

On vous recommande d'écrire un programme principal de test de la pile : cela peut être tout simplement un programme qui empile et dépile des entiers et affiche le contenu de la pile après chaque modification.

Module de gestion d'une file FIFO

On va implanter un module de gestion d'une file bornée d'entiers naturels sur 32 bits. On vous impose de stocker les éléments de cette pile dans un tableau (pas une structure chainée).

Une file FIFO (first-in, first-out) est une structure permettant de stocker et extraire des valeurs, en respectant la propriété suivante : quand on extrait une valeur, la valeur renvoyée est la plus ancienne actuellement stockée dans la file.

Votre module doit implanter au moins les fonctions suivantes :

  • struct fifo_t *nouv_fifo(uint32_t capacite) : crée une file de capacité donnée (en allouant les structures pertinentes et en les initialisation comme nécessaire) ;
  • void put(uint32_t val, struct fifo_t *fifo) : ajoute une valeur val dans la file ;
  • uint32_t get(struct fifo_t *fifo) : extrait une valeur de la file ;
  • void detruire_fifo(struct fifo_t **) : détruit la file, c'est à dire libère toutes les structures de données allouées dynamiquement et force le pointeur sur la file à NULL pour plus de sécurité.

Cette file doit être implantée sous la forme d'un tableau circulaire : cela signifie que si on arrive à la fin du tableau, mais qu'il y a des cases libres au début (parce qu'on a déjà retiré des valeurs précédemment ajoutées), alors vous devez insérer les valeurs suivantes au début du tableau (cela implique donc de gérer deux indices : un désignant la case occupée la plus ancienne et un désignant la première case vide).

Bien sûr, vous pouvez rajouter toutes les fonctions qui vous paraissent nécessaires (par exemple pour tester si la file est vide ou pleine, pour afficher son contenu, etc.).

On vous recommande d'écrire un programme principal de test de la file : cela peut être tout simplement un programme qui ajoute et retire des entiers en affichant le contenu de la file après chaque modification.