Trop Graph

Exercice 1 - Maven

  <project xmlns="http://maven.apache.org/POM/4.0.0"
           xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
           xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
      <modelVersion>4.0.0</modelVersion>
      <groupId>fr.uge.graph</groupId>
      <artifactId>sed</artifactId>
      <version>0.0.1-SNAPSHOT</version>

      <properties>
          <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
      </properties>

      <dependencies>
          <dependency>
              <groupId>org.junit.jupiter</groupId>
              <artifactId>junit-jupiter-api</artifactId>
              <version>5.13.4</version>
              <scope>test</scope>
         </dependency>
      </dependencies>

      <build>
          <plugins>
              <plugin>
                  <groupId>org.apache.maven.plugins</groupId>
                  <artifactId>maven-compiler-plugin</artifactId>
                  <version>3.14.0</version>
                  <configuration>
                      <release>25</release>
                  </configuration>
              </plugin>

              <plugin>
                  <groupId>org.apache.maven.plugins</groupId>
                  <artifactId>maven-surefire-plugin</artifactId>
                  <version>3.5.3</version>
              </plugin>
         </plugins>
    </build>
</project>
          

Exercice 2 - Graph

Notre but va être d'écrire une classe MatrixGraph, dans le package fr.uge.graph, une implantation par tableau d'adjacence de l'interface Graph.
La structure de données est conceptuellement 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, ce qui est lent. On alloue un tableau à une seule dimension de taille nodeCount * nodeCount et on se balade dedans en faisant des additions et des multiplications.

1. On souhaite écrire la classe MatrixGraph qui est seule implantation possible de l'interface Graph.
   L'interface Graph est définie par le fichier Graph.java.
   Vous pouvez 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 attendue mais on documente aussi les exceptions susceptibles d'être levées.
   Dans un premier temps, on va seulement implanter la méthode nodeCount(). Pour l'instant, mettez en commentaires les autres méthodes de l'interface Graph.
   On souhaite que la classe MatrixGraph, qui est une classe d'implantation, ne soit pas visible de l'extérieur. Comme il faut une façon de créer une instance de MatrixGraph pour l'utilisateur, nous allons déclarer dans l'interface Graph une factory method of(nodeDount) qui renvoie une instance de MatrixGraph. Quelle méthode doit faire les vérifications sur nodeCount ? Le constructeur ou la factory ?
   Écrire la classe MatrixGraph, ses champs, son constructeur et la méthode nodeCount.
   Vérifier que les tests marqués "Q1" passent.
   Note : au niveau du @SuppressWarnings, indiquez en commentaire pourquoi on peut supprimer le warning.


2. On veut maintenant permettre de créer des graphes avec une autre valeur que null comme valeur par par défaut pour les cases de la matrice.
   À cette fin, on va créer dans Graph une nouvelle méthode of à deux paramètres, of(nodeCount, defaultValue) qui prend le nombre de noeuds ainsi que la valeur par défaut des cases.
   On va de plus implanter la méthode getWeight(src, dst) qui renvoie la valeur de poids d'un arc (src, dst) ou defaultValue si l'arc n'existe pas. Pour cela, indiquer comment trouver la case (i, j) dans un tableau à une seule dimension de taille nodeCount * nodeCount.
   Implanter les méthodes of et getWeight.
   Vérifier que les tests marqués "Q2" passent.
   Note : il existe une méthode Arrays.fill() qui permet d'initialiser un tableau.
   Rappel : Java initialise déjà les tableaux à null. Initialiser un tableau est TRÈS lent (plein d'écritures), donc faites-le uniquement si c'est nécessaire.


3. On souhaite écrire la méthode addEdge(src, dst, weight) qui permet d'ajouter un arc (src, dst) avec le poids weight. Le poids ne peut pas être null et ne peut pas être le poids par défaut.
   Vérifier que les tests marqués "Q3" passent.


4. On souhaite maintenant écrire une méthode edges(src) qui renvoie un itérable sur les arcs du graphe qui ont pour source src.
   Pour cela, nous allons définir une classe Edge à l'intérieur de l'interface Graph qui contient les deux nœuds de l'arc (src et dst) et le poids (weight).
   Rappeler ce qu'est un itérable ? Combien de méthodes abstraites y a-t-il dans l'interface Iterable ? Comment allons-nous implanter notre Itérable ?
   Comment allons-nous implanter l'interface Iterator ? Quels sont les champs ?
   On ne veut pas visiter les arcs qui n'existent pas (ceux qui ont un poids égal à la valeur par défaut). Cela veut dire que notre itérateur doit visiter les voisins d'un nœud en sautant les arcs qui n'ont pas de poids. Pour ça, le plus simple est d'écrire une fonction qui le voisin courant en paramètre et renvoie le voisin suivant, avec une boucle pour passer les arcs qui n'ont pas de poids.
   Écrire la méthode edges(src).
   Vérifier que les tests marqués "Q4" passent.


5. On souhaite pouvoir supprimer des arcs du graphe et on va implanter cette méthode au niveau de l'itérateur (ainsi la sémantique est bien définie).
   Quelle méthode doit-on implanter ? Comment fonctionne-t-elle ?
   Modifier votre implantation et vérifier que les tests "Q5" passent.


6. On souhaite maintenant écrire une méthode edgeStream(src) qui renvoie un Stream des arcs du graphe qui ont pour source src.
   Pour l'instant, on ne va implanter que la partie séquentielle (non parallèle) de l'API, donc on peut écrire le Spliterator en utilisant la syntaxe des classes anonymes.
   Quelles sont les champs dont on a besoin ? Comment écrire la méthode tryAdvance ? Comment écrire la méthode trySplit ? Comment écrire la méthode estimateSize ? Quelles sont les caractéristiques ? Comment écrire la méthode characteristics ?
   Écrire la méthode edgeStream(src).
   Vérifier que les tests marqués "Q6" passent.


7. Pour les plus balèzes, on veut maintenant que lorsque l'on demande la version parallèle du Stream, il utilise plusieurs threads. Pour cela, il faut implanter la méthode trySplit. Et pour cela, comme chaque Spliterator ne va visiter qu'une partie des arcs, on a besoin d'un index de début et d'un index de fin.
   On se propose d'implanter la méthode d'aide (helper method) edgeSpliterator(src, start, end) qui renvoie un Spliterator qui va visiter les arcs du graphe entre start et end.
   Écrire la méthode edgeSpliterator et modifier edgeStream pour obtenir un Stream parallélisable.
   Vérifier que les tests marqués "Q7" passent.