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

Trop Graph

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

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

La méthode isOriented() renvoie toujours vrai.
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 poid.
La méthode addEdge(src, dst, weight) ajoute un arc avec un poid ou change le poid de l'arc s'il existait avant. NO_WEIGHT n'est pas une valeur de poid 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 iterateur sur tous les noeuds ayant un arc dont la source est vertex. L'ordre de parcours de l'iterateur n'est pas imposé.

Exercice 1 - JUnit

Avant de commener à coder quoi que cela soit, commençez 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 preconditions à vérifier.
Noubliez pas que des int même s'il représente des index positifs peuvent être negatifs.

Exercice 2 - MatrixGraph

MatrixGraph est une implantation par matrice d'ajacence. La structure de donnée est une matrice verticesCount x verticesCount et l'on stocke le poid d'un arc (src, dst) dans la case [src][dst].
En fait, habituellement, on ne répresente 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 arriver pas faite un dessin !
Implanter les méthodes de Graph en laissant de coter la méthode neighbors pour l'instant.
Vérifier que vos tests JUnit passent.
Rappeler le fonctionnement d'un iterateur.
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 pairs (noeud destination, poid). Comme chaque noeud est numéroté, un graphe sera donc un tableau de liste de pairs.

Expliqueer pourquoi il est plus judicieux que la classe réprésentant une pair/un couple (noeud destination/poid) soit une classe interne.
Rappeler ensuite la différence entre les classes internes statique et non-statique.
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 wildcard non borné qui sera ensuite caster en tableau de liste de pairs.
Expliquer pourquoi le compilateur emet un warning.
Implanter la classe NodeListGraph.
Remarquez que certaines méthodes des classes MatrixGraph et NodeListGraph ont la même implantation.
Factorizer 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 poid 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 ajouter une méthode edges() à l'interface Graph qui renvoie un iterateur sur chaque arc materialiser par l'interface Edge.

Faire en sorte que toute les implantations aient une méthode edges().
Il y a une astuce, vous ne devriez écrire le code qu'une seul fois :)
On souhaiterait ajouter une méthode setWeight à l'interface Edge, qui change le poid d'un arc retourné par l'iterateur. Expliquer pourquoi il n'est pas possible d'avoir une implantation commune pour cette méthode.
Si vous ne voyez pas essayer de l'implanter, lorsque vous aurez réussi testé votre implantation, vous saurez ...