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

Trop Graph

Le but de ce TD est d'implanter diverses implantations des graphes orientés 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). Les arcs sont valués (par un entier). Les noeuds ne contiennent pas d'information.

Vous pouvez aussi noter que l'interface Graph est correctement documentée en utilisant le format javadoc.

Exercice 1 - 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 tableau à une seul dimension de taille verticesCount x verticesCount et on se balade dedans en faisant des additions et des multiplications.

Verifier avec les tests unitaires suivant que votre implantation est bien conforme. MatrixGraphTest.java

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.
Rappeler le fonctionnement d'un itérateur et de ses méthodes hasNext et next.
Que renvoie next si hasNext retourne false ?
Expliquer pourquoi il n'est pas nécessaire dans un premier temps d'implanter la méthode remove qui fait pourtant partie de l'interface.
Implanter la méthode neighbors.
Note, pour vous aidez, écrire une méthode nextEdge qui à partir d'un noeud start et du noeud vertex trouve de prochain edge (vertex, index) en parcourant la ligne de la matrice.
Pourquoi le champs verticesCount ne doit pas être déclaré private ?
Y a t'il d'autre(s) champ(s) qui ne doivent pas être déclarés private ?
Modifier votre code.
Expliquer, le fonctionnement précis de la méthode remove.
Implanter la méthode remove de l'iterateur.

Exercice 2 - NodeListGraph

On souhaite maintenant fournir une autre implantation de l'interface Graph dite par "listes d'adjacence".
On va stocker pour chaque noeud une liste des arcs sortants sous forme d'une liste de paires (noeud destination, poids de l'arc) appelée liste d'ajacence.
De plus, comme chaque noeud est numéroté, le graphe sera donc un tableau de listes d'adjacence, l'arc entre s et d de poid w étant rangé sous forme de la paire (d, w) dans la liste d'ajacence stocké dans la case s du tableau.

Verifier avec les tests unitaires suivant que votre implantation est bien conforme. NodeListGraphTest.java

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.
Quelle type de classe interne doit-on utiliser ici ?
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é puis en castant celui-ci en tableau de liste de paires (noeud destination, poids).
Comment faire pour gérer le warning levé par le compilateur à cette occasion ?
Quelles sont les opérations que l'on va effectuer sur une liste d'adjacence.
En déduire quelle est la structure de données à utiliser.
Quel est le nom de la classe Java que l'on va utiliser pour implanter les listes d'adjacence.
Implanter le constructeur de NodeListGraph sachant que dans le but de simplifier le code, le tableau des listes d'adjacences sera initialisé avec des listes vides.
Implanter les méthodes hasEdge, getWeight, addEdge et removeEdge de la classe NodeListGraph.
Implanter la méthode neighbors ainsi que la méthode remove de l'itérateur correspondant.
Note: une java.util.List possède déjà une méthode iterator().

Exercice 3 - Factorisation

On remarque que quelque soit l'implantation, il est possible d'écrire la méthode hasEdge et utilisant la méthode getWeight.

Quelles sont les deux façons de faire en sorte que le code de hasEdge soit écrit une fois pour les 2 implantations.
Quelle solution doit être choisie, ici ?
Implanter la solution retenue.
De plus, le code pour tester les pré-conditions est commun au deux implantations, comment faire pour partager se code ?
Implanter la solution retenue.

Exercice 4 - NodeMapGraph

On souhaite fournir une troisième implantation de l'interface Graph par "table associatives". Comme pour l'implantation par listes d'adjacence, un tableau dont chaque index correspondant à un noeud source est utilisé mais au lieu d'utilisé une liste pour stocker les arcs sortants, l'implantation utilise une table de hachage qui associe au noeud destination le poid de l'arc correspondant.

Verifier avec les tests unitaires suivant que votre implantation est bien conforme. NodeMapGraphTest.java

Implanter la classe NodeMapGraph.
Note: chaque méthode n'est pas censé prendre plus de 2 ou 3 lignes, tests des préconditions compris.
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.

Verifier avec les tests unitaires suivant que votre implantation est bien conforme. GraphEdgesTest.java

Faire en sorte que toutes les implantations utilisent le code d'une seule méthode edges().
Question super bonus top moumoute (optionelle)
Si on regarde l'implantation de la classe NodeListGraph, les méthodes hasEdge, getWeight, addEdge et removeEdge utilisent toutes la même boucle, factoriser le code pour que toutes ces méthodes délèguent leur traitement à une seule méthode privée.
Note: chaque méthode doit maintenant être écrite en une ligne si on ne compte pas les préconditions.
Indication: lettre grec entre kappa et mu.