:: Enseignements :: ESIPE :: E4INFO :: 2018-2019 :: Java Avancé ::

Trop Graph

Le but de ce TD est d'implanter diverses représentations 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 deux implantations différentes de l'interface Graph ci-dessous. Il s'agit de graphes orientés qui ont un nombre de nœuds fixe (numérotés de 0 à nodeCount - 1). Les arcs sont valués (par des objets, dont le type est type est indiqué par T). Les nœuds ne contiennent pas d'information.

Le constructeur prend le nombre de nœuds du graphe en paramètre.
La méthode getWeight(src, dst) renvoie le poids de l'arc entre src et dst. On utilisera un Optional pour modéliser l'absence possible d'arc.
La méthode addEdge(src, dst, weight) ajoute un arc avec un poids ou remplace le poids de l'arc s'il existait avant.
La méthode edges(src, consumer) qui prend un nœud en paramètre et appelle le consumer avec chaque arc qui a ce nœud comme source.

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 * nodeCount telle que l'on stocke le poids d'un arc (src, dst) dans la case (src, dst).
En fait, habituellement, on ne représente 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 seule dimension de taille nodeCount * nodeCount et on se balade dedans en faisant des additions et des multiplications.

Les tests unitaires qui vérifient que votre implantation est bien conforme sont là: GraphTest.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, en Java, il n'est pas possible de créer des tableaux de variables de type.
Implanter le constructeur. Pouvez-vous supprimer le warning? Pourquoi?
On peut remarquer que la classe MatrixGraph n'apporte pas de nouvelles méthodes par rapport aux méthodes de l'interface Graph donc il n'est pas nécessaire que la classe MatrixGraph soit publique.
Ajouter une méthode factory nommée createMatrixGraph dans l'interface Graph et déclarer la classe classe MatrixGraph non publique.
Afin d'implanter correctement la méthode getWeight, rappeler à quoi sert la classe java.util.Optional en Java.
Implanter la méthode getWeight.
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 nœuds ayant un arc dont la source est src.
Note: ça pourrait être une bonne idée de calculer quel est le prochain arc valide AVANT que l'on vous demande si il existe.
Pourquoi le champ nodeCount ne doit pas être déclaré private (avant Java 11) ?
Est-ce qu'il y a 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 nœuds ayant un arc sortant par 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 va falloir redéfinir.
Écrire la méthode neighborStream sachant que l'on implantera le Spliterator en utilisant l'itérateur défini 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 on fait 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 (optionnel)

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

Les tests unitaires sont les mêmes que précédemment car NodeMapGraph est une autre implantation de l'interface Graph, il suffit de dé-commenter la méthode référence dans graphFactoryProvider.

Écrire dans Graph la méthode static createNodeMapGraph et implanter la classe NodeMapGraph (non publique).
Note: chaque méthode est sensée ne pas prendre plus de 2 ou 3 lignes, tests des préconditions compris.