:: Enseignements :: Master :: M1 :: 2012-2013 :: Java Avancé ::

Trop Graph

Le but de ce TD est d'implanter diverses implantations des graphes orientés (sauf à la fin) et de jouer avec les types paramétrés et les itérateurs.

Le TD a pour but de fournir plusieurs implantations de l'interface Graph ci-dessous. Ce type de graphe représente les graphes orientés qui ont un nombre de noeuds fixe (numerotés de 0 à verticesCount - 1) dont les arcs sont valués et qui ne contienne pas d'information sur les noeuds.

La méthode verticesCount() renvoie le nombre de noeuds spécifié à la création de l'implantation.
La méthode hasEdge(src, dst) renvoie vrai s'il existe un arc entre src et dst.
La méthode getWeight(src, dst) renvoie le poid de l'arc entre src et dst ou NO_WEIGHT s'il n'y a pas de poids.
La méthode addEdge(src, dst, weight) ajoute un arc avec un poids ou change le poids de l'arc s'il existait avant. NO_WEIGHT n'est pas une valeur de poids possible. De plus, la méthode renvoie vrai si un arc a été ajouté.
La méthode removeEdge(src, dst) supprime l'arc entre src et dst ou ne fait rien s'il n'y a pas d'arc. De plus, la méthode renvoie vrai si l'arc a été supprimé.
La méthode neighbors(vertex) renvoie un itérateur sur tous les noeuds ayant un arc dont la source est vertex. L'ordre de parcours de l'itérateur n'est pas imposé.

Exercice 1 - JUnit

Avant de commencer à coder quoi que ce soit, commencez par écrire les tests JUnit pour tester que la classe MatrixGraph que vous écrirez dans l'exercice suivant fonctionne.
Il doit y avoir au moins un test par méthode, plus un pour le constructeur, plus autant de tests qu'il y a de préconditions à vérifier.
Noubliez pas que des int même s'ils représentent des index positifs peuvent être negatifs.

Exercice 2 - MatrixGraph

MatrixGraph est une implantation par matrice d'ajacence. La structure de données est une matrice verticesCount x verticesCount et l'on stocke le poids d'un arc (src, dst) dans la case [src][dst].
En fait, habituellement, on ne répresente pas une matrice sous forme d'un tableau à double entrée car cela veut dire effectuer deux indirections pour trouver la valeur. On alloue un seul tableau de taille verticesCount x verticesCount et on se balade dedans en faisant des additions et des multiplications.

Indiquer comment trouver la case (i, j) dans un tableau à une seule dimension de taille verticesCount x verticesCount.
Si vous n'y arrivez pas, faites un dessin !
Implanter les méthodes de Graph en laissant de côté la méthode neighbors pour l'instant.
Vérifier que vos tests JUnit passent.
Rappeler le fonctionnement d'un itérateur.
Expliquer de plus, le fonctionnement précis de la méthode remove.
Implanter la méthode neighbors.

Exercice 3 - NodeListGraph

On souhaite maintenant fournir une autre implantation de l'interface Graph qui stocke pour chaque noeud, une liste de paires (noeud destination, poids). Comme chaque noeud est numéroté, un graphe sera donc un tableau de listes de paires.

Expliquer pourquoi il est plus judicieux que la classe réprésentant une paire/un couple (noeud destination/poids) soit une classe interne.
Rappeler ensuite la différence entre les classes internes statiques et non-statiques.
Rappeler pourquoi il n'est pas possible d'allouer un tableau de type paramétré en Java.
Pour éviter le problème, l'allocation se fera en allouant un tableau de wildcards non borné qui sera ensuite caster en tableau de listes de paires.
Expliquer pourquoi le compilateur émet un warning.
Implanter la classe NodeListGraph.
Remarquez que certaines méthodes des classes MatrixGraph et NodeListGraph ont la même implantation.
Factoriser le code pour qu'il ne soit pas dupliqué.
Expliquer comment le warning vu plus haut peut être supprimé.
Expliquer s'il est possible ou non de supprimer ce warning sans rendre le code non-sûr.

Exercice 4 - NodeMapGraph

On souhaite fournir une troisième implantation de l'interface Graph qui stocke pour chaque noeud, une table de hachage qui associe à un noeud destination le poids de l'arc correspondant. Comme chaque noeud est numéroté, un graphe sera donc un tableau de table de hachage.

Implanter la classe NodeMapGraph.
Comparer les complexités des méthodes getWeight,addEdge removeEdge et neighbors entre la classe NodeListGraph et la classe NodeMapGraph.

Exercice 5 - [A la Maison]

On souhaite ajouter une méthode edges() à l'interface Graph qui renvoie un itérateur sur chaque arc matérialisé par l'interface Edge.

Faire en sorte que toutes les implantations aient une méthode edges().
Il y a une astuce, vous ne devriez écrire le code qu'une seul fois :)
Ajouter une méthode setWeight à l'interface Edge, qui permet de changer le poid d'un arc retourné par l'itérateur.
Expliquer pourquoi les implantations NodeListGraph et NodeMapGraph ne lèvent pas d'exception ConcurrentModificationException dans ce cas (on modifie la collection pendant son parcours).