INF 441 - TD 3

Files d'entiers et parcours en largeur de graphes

Votre opinion sur le cours de ce matin : Votre opinion sur le TD de la semaine dernière :

L'objectif de ce TD est d'implémenter de plusieurs façon différentes (mais toujours en Java) des files d'entiers, autrement dit des classes qui offrent les méthodes décrites ci-dessous.

size renvoie le nombre d'éléments de la file
put insère un nouvel élément en fin de file. Lance l'exception FullQueueException si la file est pleine.
get supprime et renvoie l'élément situé en tête de file. Lance l'exception EmptyQueueException si la file est vide.
is_empty renvoie true si et seulement si la file est vide.
flush vide la file.
print affiche les entiers contenus dans la file sur une même ligne, séparés par des espaces, du plus ancien au plus récent.

Ces implémentations seront utilisées pour réaliser le parcours en largeur d'un graphe (c'est une application classique).

Les classes et interfaces du TD seront rangées dans deux paquets intfifo et applications, exceptée la classe Main avec laquelle on effectuera les tests (à mettre dans le default package de Java).

1. Interface

But : créer des paquets, des interfaces et quelques classes très simples à l'aide d'Eclipse en précisant les risques de levée d'exception.

Créer le paquet intfifo.
Créer l'interface publique FIFO dans le paquet intfifo.
Déclarer dans l'interface FIFO les méthodes décrites en haut de la page.
Par exemple public int size () ; déclare la méthode size.
Certaines méthodes sont susceptibles de lever une exception (typiquement lorsque l'on souhaite accéder à un élément de la file vide ou que l'on tente d'ajouter un élément à une file pleine). Dans l'interface FIFO, nous allons préciser lesquelles au moyen de la syntaxe:
```
          déclaration throws exception ;
          
```
où
- déclaration est une déclaration de méthode standard sans le point-virgule final, et
- exception est une classe qui étend la classe Exception de Java.
Pour ce faire
- on crée dans le paquet intfifo les classes publiques EmptyQueueException et FullQueueException qui étendent la classe Exception de Java, puis
- on indique dans l'interface FIFO quelles sont les méthodes susceptibles de lever les exceptions EmptyQueueException et FullQueueException au moyen de la syntaxe décrite précédemment.

Déposer le fichier FIFO.java :

Solution : FIFO

2. Implémentation de l'interface FIFO à base de tableaux d'entiers

But : écrire une classe ArrayQueue qui implémente l'interface FIFO à l'aide d'un tableau d'entiers de type int [].

Quelques indications et une contrainte :

On fixe (au moment de la construction de la file) la taille du tableau qui contient les entiers, autrement dit la longueur maximale des files. De ce fait, il pourra arriver qu'une file soit pleine et qu'on ne puisse plus y insérer d'éléments. La taille souhaitée sera un argument du constructeur.
On maintient deux entiers older et size qui indiquent respectivement la position de l'élément le plus ancien de la file (donc celui qui devra être supprimé lors du prochain appel à la méthode get) et le nombre d'éléments contenus dans la file.
Les ajouts et retraits doivent être faits en temps constant.
Testez votre code à l'aide de la classe Main. Il faut pour cela « décommenter » les lignes que vous souhaitez activer.

Déposer le fichier ArrayQueue.java :

Solution : ArrayQueue

3. Application : parcours en largeur des graphes (Breadth First Search)

Dans cette section, un graphe désigne un graphe orienté dont les sommets sont des entiers avec au plus un arc d'un sommet vers un autre. Si α et β sont deux sommets, il peut néanmoins y avoir un arc α→β et un arc β→α. Un graphe est donc caractérisé par une application (i.e. interface Map de Java) qui associe à chaque sommet l'ensemble (i.e. interface Set de Java) de ses successeurs.

But : implémenter les graphes en utilisant des classes (paramétrées) fournies par Java, puis exploiter un objet qui satisfait l'interface FIFO pour implémenter le parcours de graphe en largeur depuis un sommet donné.

Créer le paquet applications.

Dans le paquet applications et à l'aide des interfaces (paramétrées) Map<K,V> et Set<E>, créer l'interface Graph qui contient les méthodes ci-dessous :
- successors qui prend en argument un entier i et renvoie l'ensemble des successeurs de i dans le graphe.
- addEdge qui prend en argument deux entiers i et j et ajoute l'arc i→j au graphe.
- print qui affiche un graphe en affichant pour chaque sommet une ligne qui indique ses successeurs.

Créer une classe MyGraph qui implémente Graph. On ajoutera notamment deux constructeurs :
- MyGraph () qui construit le graphe vide ;
- MyGraph (int [][] g) qui prend un tableau de tableaux d'entiers en argument et renvoie le graphe correspondant (les éléments de la k-ème ligne sont les successeurs de k). C'est pratique pour faire des tests.
Créer une classe BFS pour réaliser le parcours en largeur, contenant
- un constructeur BFS(Graph g) prenant le graphe à parcourir en argument ;
- une méthode printReachableFrom qui prend en argument un entier i et affiche (sur une ligne et séparés par des espaces) les sommets du graphe visités par un parcours en largeur partant du sommet i.

N'oubliez pas de tester votre code à l'aide de la classe Main (décommenter les lignes que vous souhaitez activer). Vous devez obtenir la sortie suivante :
```
        0: 0 1 2 3
        1: 1 3 0 2
        2: 2 3 0 1
        3: 3 0 1 2
        4: 4 5
        5: 5
```

Déposer les fichiers Graph.java, MyGraph.java, et BFS.java:

Solution : Graph / MyGraph / BFS

4. Implémentation de l'interface FIFO à base de listes chaînées

But : écrire une classe LinkedQueue qui implémente l'interface FIFO à l'aide de listes chaînées.

L'utilisation de tableaux dans ArrayQueue contraint le programmeur à fixer une taille maximale initialement. Nous allons lever cette contrainte en utilisant des listes chaînées.

Une file est une liste chaînée dont la tête est l'élément le plus ancien (donc celui qui sera supprimé au prochain appel à la méthode get). On maintient aussi un pointeur sur la dernière cellule de la liste chaînée, de manière à pouvoir ajouter de nouveaux éléments à la fin de la liste.

Dans le paquet intfifo, ajouter une classe ListCell pour représenter une liste non vide, avec deux champs value et next. La valeur null sera utilisée pour représenter la liste vide.
Écrire dans le paquet intfifo une implémentation LinkedQueue de l'interface FIFO à l'aide de la classe ListCell.

N'oubliez pas de tester votre code à l'aide de la classe Main (décommenter les lignes que vous souhaitez activer).

Dans la classe BFS, remplacer l'utilisation de ArrayQueue par LinkedQueue. Relancer les tests. Vous devez observer les mêmes résultats.

Pour permettre à l'utilisateur de choisir entre ArrayQueue et LinkedQueue, munir la classe BFS d'une méthode abstraite FIFO newQueue() et l'implémenter dans deux sous-classes distinctes, d'un côté par return new ArrayQueue(128) et de l'autre par return new LinkedQueue ().

Déposer les fichiers ListCell.java et LinkedQueue.java :

Solution : ListCell et LinkedQueue

Votre opinion sur le cours de ce matin :	Votre opinion sur le TD de la semaine dernière :