:: Enseignements :: ESIPE :: E4INFO :: 2014-2015 :: 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 est à rendre sur la plateforme elearning.

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 - NodeMapGraph

On souhaite fournir une implantation de l'interface Graph par "table associatives". On utilise un tableau dont chaque index correspond à un noeud source et on utilise une table de hachage pour stocker les arcs sortants, cette table associe au noeud destination le poids de l'arc correspondant.

Vérifier 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ée prendre plus de 2 ou 3 lignes, tests des préconditions compris.

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

Vérifier avec les tests unitaires suivants 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 aider, écrire une méthode nextEdge qui à partir d'un noeud start et du noeud vertex trouve le prochain edge (vertex, index) en parcourant la ligne de la matrice.
Pourquoi le champ 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'itérateur.

Exercice 3 - [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.

Vérifier avec les tests unitaires suivants 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)
Il est possible de créer une 3ième implantation NodeListGraph qui fonctionne comme NodeMapGraph mais utilise une liste de couple (noeud destination, poid de l'arc) à la place de la table de hachage. Cette version sera plus lente si il y beacoup de noeud sortants mais consomme moins de mémoire qu'une table de hachage.
Dans ce cas, les méthodes hasEdge, getWeight, addEdge et removeEdge vont toutes utiiser une même boucle pour trouver le couple correspondant à un noeud destination, il est donc possible de 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.