:: Enseignements :: Master :: M1 :: 2015-2016 :: 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, les lambdas, les itérateurs et les streams.

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 à nodeCount - 1). Les arcs sont valués (par un objet). Les noeuds ne contiennent pas d'information.

Un constructeur qui prend le nombre de noeuds du graph.
La méthode getWeight(src, dst) renvoie le poids de l'arc entre src et dst ou NO_EDGE s'il n'y a pas d'arc.
La méthode addEdge(src, dst, weight) ajoute un arc avec un poids ou change le poids de l'arc s'il existait avant.
La méthode edges(src, consumer) qui prend un noeud et appel le consumer avec chaque arc qui a pour source le noeud pris en paramètre.

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'adjacence de l'interface Graph. La structure de données est une matrice nodeCount x nodeCount 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 nodeCount * nodeCount et on se balade dedans en faisant des additions et des multiplications.

Les tests unitaires vérifiant que votre implantation est bien conforme sont là: MatrixGraphTest.java

Indiquer comment trouver la case (i, j) dans un tableau à une seule dimension de taille nodeCount * nodeCount.
Si vous n'y arrivez pas, faites un dessin !
Rappeler pourquoi il n'est pas possible en Java de créer des tableaux de variable de type.
Implanter le constructeur en utilisant un tableau d'Object.
Afin d'implanter correctement la méthode getWeight, rappeler à quoi sert la classe java.util.Optional en Java.
Implanter la méthode getWeight sans warning SVP.
Implanter la méthode addEdge.
Implanter la méthode edges.
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 neighborsIterator(src) qui renvoie un itérateur sur tous les noeuds ayant un arc dont la source est src.
Note, vous avez déjà écrit la méthode edges et cela ressemble beaucoup si vous avez eu la bonne idée de calculer quel est l'arc valide AVANT que l'on vous demande si il existe.
Pourquoi le champ nodeCount ne doit pas être déclaré private ?
Y a t'il d'autres champs qui ne doivent pas être déclarés private ?
Modifiez votre code.
On souhaite écrire la méthode neighborStream(src) qui renvoie un IntStream contenant tous les noeuds ayant un arc sortant pas src.
Pour créer le stream nous allons utiliser StreamSupport.intStream qui prend en paramètre un Spliterator.OfInt. Rappeler ce qu'est un Spliterator, à quoi sert le OfInt et quelles sont les méthodes qu'il faut redéfinir.
Ecrire la méthode neighborStream sachant que l'on implantera le spliterator en utilisant l'iterateur définie précédemment.
On peut remarquer que neighborStream dépend de neighborsIterator et donc pas d'une implantation spécifique. On peut donc écrire neighborStream directement dans l'interface Graph comme ça le code sera partagé.
Rappeler comment fait-on pour avoir une méthode avec du code dans une interface.
Déplacer neighborStream dans Graph
Expliquer le fonctionnement précis de la méthode remove de l'interface Iterator.
Implanter la méthode remove de l'itérateur.
On peut remarquer que l'on peut ré-écrire edges en utilisant neighborsStream, en une ligne :), et donc déplacer edges dans Graph.
Déplacer le code de la méthode edges dans Graph.

Exercice 2 - NodeMapGraph

On souhaite fournir une implantation de l'interface Graph par table de hachage qui pour chaque noeud permet de stocker l'ensemble des arcs sortant. Pour un noeud donné, on utilise une table de hachage qui a un noeud destination associe le poid de l'arc. Si un noeud destination n'est pas dans la table de hachage cela veut dire qu'il n'y a pas d'arc entre le noeud source et le noeud destination.
Le graph est représenté par un tableau dont chaque case correspond à un noeud, donc chaque case contient une table de hachage qui associe à un noeud destination le poid de l'arc correspondant.

Voici les tests unitaires permettant de vérifier que votre implantation est bien conforme. NodeMapGraphTest.java

Implanter la classe NodeMapGraph.
Note: chaque méthode est censée ne pas prendre plus de 2 ou 3 lignes, tests des préconditions compris.