:: Enseignements :: Master :: M1 :: 2023-2024 :: 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.java. 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 indiqué par T). Les nœuds ne contiennent pas d'information.

Vous pouvez aussi noter que l'interface Graph est correctement documentée en utilisant le format javadoc. Non seulement, on indique pour chaque méthode publique ce que fait la méthode, à quoi correspond chaque paramètre, la valeur de retour attendu mais on documente aussi les exceptions susceptibles d'être levées.

Exercice 1 - Maven

Pour préparer le TP noté, on va apprendre à utiliser les tests unitaires JUnit en dehors d'un projet Maven en utilisant Eclipse. Dans la configuration de votre projet Java classique, il faut ajouter la librarie JUnit 5 correctement.
Vous avez 2 options :

Soit à partir du fichier MatrixGraphTest.java : sur la première annotation @Test, utiliser le quickfix "Fixup project ..."
Soit en sélectionnant les "Properties" du projet (avec le bouton droit de la souris sur le projet) puis en ajoutant la Library JUnit 5 (jupiter) au ClassPath.

Exercice 2 - MatrixGraph

La classe MatrixGraph, dans le package fr.uge.graph, 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

On souhaite créer la classe paramétrée (par le type des valeurs des arcs) MatrixGraph comme seule implantation possible de l'interface Graph définie par le fichier Graph.java
La classe MatrixGraph contient
- Un champ array, un tableau des valeurs des arcs comme expliqué ci-dessus,
- Un constructeur qui prend en paramètre le nombre de nœuds du graphe,
- Une méthode nodeCount qui renvoie le nombre de nœuds du graphe.
Pour l'implantation du constructeur, rappeler pourquoi, en Java, il n'est pas possible de créer des tableaux de variables de type.
Écrire la classe MatrixGraph, ses champs, son constructeur et la méthode nodeCount.
Vérifier que les tests marqués "Q1" passent.
Note : Pouvez-vous supprimer le warning à la construction ? 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 MatrixGraph non publique.
Vérifier que les tests marqués "Q2" passent.

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 ! Afin d'implanter correctement la méthode getWeight, rappeler à quoi sert la classe java.util.Optional en Java.
Implanter la méthode addEdge en utilisant la javadoc pour savoir quelle est la sémantique exacte.
Implanter la méthode getWeight en utilisant la javadoc pour savoir quelle est la sémantique exacte.
Vérifier que les tests marqués "Q3" passent.

On souhaite maintenant implanter une méthode mergeAll qui permet d'ajouter les valeurs des arcs d'un graphe au graphe courant.
Dans le cas où on souhaite ajouter une valeur à un arc qui possède déjà une valeur, on utilise une fonction prise en second paramètre qui prend deux valeurs et renvoie la nouvelle valeur.
Implanter la méthode mergeAll en utilisant la javadoc pour savoir quelle est la sémantique exacte.
Vérifier que les tests marqués "Q4" passent.
Rappel: on peut tester si un Optional est vide avec la méthode isEmpty et récupérer la valeur si l'Optional n'est pas vide avec la méthode orElseThrow.
Note : si vous vous sentez balèze aujourd'hui, on peut écrire la mise à jour d'une case en une seule expression, en utilisant des méthodes comme map, ou ifPresent sur Optional. Cela rend le code bien moins lisible, mais c'est un bon exercice.

En fait, on peut remarquer que l'on peut écrire le code de mergeAll pour qu'il soit indépendant de l'implantation et donc écrire l'implantation de mergeAll directement dans l'interface.
Déplacer l'implantation de mergeAll dans l'interface et si nécessaire modifier le code pour qu'il soit indépendant de l'implantation.
Vérifier que les tests marqués "Q5" passent.

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.
Vérifier que les tests marqués "Q6" passent.
Note : ça pourrait être une bonne idée de calculer quel est le prochain arc valide AVANT que l'on vous demande s'il existe.

Expliquer le fonctionnement précis de la méthode remove de l'interface Iterator.
Implanter la méthode remove de l'itérateur.
Vérifier que les tests marqués "Q7" passent.

On souhaite ajouter une méthode forEachEdge qui prend en paramètre un index d'un nœud et une fonction qui est appel cette fonction avec chaque arc sortant de ce nœud.
Pour cela, nous allons, dans un premier temps, définir le type Graph.Edge à l'intérieur de l'interface Graph. Un Graph.Edge est définie par un entier src, un entier dst et un poids weight.
Écrire la méthode forEachEdge en utilisant la javadoc pour savoir quelle est la sémantique exacte.
Vérifier que les tests marqués "Q8" passent.

Enfin, on souhaite écrire une méthode edges qui renvoie tous les arcs du graphe sous forme d'un stream.
L'idée ici n'est pas de réimplanter son propre stream (c'est prévu dans la suite du cours) mais de créer un stream sur tous les nœuds (sous forme d'entier) puis pour chaque nœud de renvoyer tous les arcs en réutilisant la méthode forEachEdge que l'on vient d'écrire.
Écrire la méthode edges en utilisant la javadoc pour savoir quelle est la sémantique exacte.
Vérifier que les tests marqués "Q9" passent.
Rappel : il existe une méthode mapMulti sur un stream.

Exercice 3 - NodeMapGraph

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 l'interface Graph la méthode createNodeMapGraph et implanter la classe NodeMapGraph (toujours non publique).
Note : chaque méthode est sensée ne pas prendre plus de 2 ou 3 lignes, tests des préconditions compris.