:: Enseignements :: ESIPE :: E4INFO :: 2026-2027 :: Java Avancé ::
[LOGO]

Enter the matrix (Graph)


Matrice d'adjacence, classe interne, itérateur et spliterator
Le but de ce TP est d'écrire un graphe orienté dont le nombre de sommets est fixé à la création et dont les arcs portent une valeur. Le graphe est implanté avec une matrice d'adjacence stockée dans un tableau à une dimension. Ce TP permet de revoir les notions de classe interne, d'itérateur, de stream et d'écrire son propre Spliterator.

Exercice 1 - Maven

Comme pour les TPs précédents, nous allons utiliser Maven avec une configuration (le pom.xml) très similaire.
    <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>graph</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.14.4</version>
                <scope>test</scope>
            </dependency>
        </dependencies>

        <build>
            <plugins>
                <plugin>
                    <groupId>org.apache.maven.plugins</groupId>
                    <artifactId>maven-compiler-plugin</artifactId>
                    <version>3.16.0</version>
                    <configuration>
                        <release>27</release>
                    </configuration>
                </plugin>
                <plugin>
                    <groupId>org.apache.maven.plugins</groupId>
                    <artifactId>maven-surefire-plugin</artifactId>
                    <version>3.6.0</version>
                </plugin>
            </plugins>
        </build>
  </project>
            
Créer un projet Maven dans Eclipse, au niveau du premier écran, cocher create simple project puis passer à l'écran suivant en indiquant Next.
Pour ce TP, le groupId est fr.uge.graph, l'artefactId est graph et la version est 0.0.1-SNAPSHOT. Puis cliquer sur Finish.

Exercice 2 - Enter the matrix

Un graphe orienté est un ensemble de sommets reliés par des arcs. Ici, les sommets sont les entiers de 0 à vertexCount - 1, et il y a au plus un arc de from vers to pour chaque couple de sommets. Chaque arc porte une valeur dont le type est le paramètre de type E du graphe. Les valeurs ne peuvent pas être null.
Une matrice d'adjacence est une table de taille vertexCount x vertexCount où la case (from, to) contient la valeur de l'arc de from vers to, ou null s'il n'y a pas d'arc.
Dans ce TP, la matrice est stockée dans un tableau à une dimension matrix de taille vertexCount * vertexCount, les lignes étant stockées les unes après les autres : la case (from, to) est à l'index from * vertexCount + to. Par exemple, avec 3 sommets, l'arc de 1 vers 2 est stocké dans matrix[1 * 3 + 2], soit matrix[5].
Dans ce TP, l'interface s'appelle Graph et son unique implantation, MatrixGraph, est une classe interne de l'interface. Les utilisateurs ne doivent pas dépendre de MatrixGraph, ils créent un graphe avec la factory method Graph.of.

Les tests JUnit 5 de cet exercice sont GraphTest.java.

  1. Dans un premier temps, créer une interface Graph qui ne sait que créer un graphe (avec la méthode of) et donner son nombre de sommets (avec la méthode vertexCount).
    Voici un exemple d'utilisation
      Graph<String> graph = Graph.of(4);  // 4 sommets, numérotés de 0 à 3
      IO.println(graph.vertexCount());    // 4
                    

    Si notre implantation utilisait un tableau à deux dimensions, vertexCount() pourrait renvoyer matrix.length. Pourquoi ce n'est plus possible ici ? Que faut-il ajouter à MatrixGraph ?
    Écrire l'interface Graph avec les méthodes vertexCount() et of(vertexCount) sachant que of renvoie une instance de MatrixGraph, une classe interne à Graph.
    Vérifier que les tests marqués "Q1" passent.

  2. On souhaite maintenant pouvoir ajouter un arc avec addEdge(from, to, value) et lire la valeur d'un arc avec getEdge(from, to).
    Avec notre exemple :
      Graph<String> graph = Graph.of(4);
      IO.println(graph.getEdge(0, 1));       // Optional.empty
      IO.println(graph.addEdge(0, 1, "a"));  // null
      IO.println(graph.getEdge(0, 1));       // Optional[a]
      
      IO.println(graph.addEdge(0, 1, "b"));  // a
      IO.println(graph.getEdge(0, 1));       // Optional[b]
                    

    • getEdge renvoie un Optional qui est vide s'il n'y a pas d'arc.
    • addEdge stocke la valeur et renvoie l'ancienne valeur de l'arc, ou null s'il n'y en avait pas (comme Map.put). Si l'arc existe déjà, sa valeur est remplacée.

    Comme on veut un code propre, n'hésitez pas à écrire des petites méthodes privées pour rendre le code plus lisible.
    Écrire les méthodes addEdge(from, to, value) et getEdge(from, to).
    Vérifier que les tests marqués "Q2" passent.
    Note: il existe plusieurs factory methods dans Optional, à vous d'utiliser la bonne.

  3. On souhaite ajouter la méthode edgeCount() qui renvoie le nombre d'arcs du graphe.
      Graph<String> graph = Graph.of(4);
      IO.println(graph.edgeCount());  // 0
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 3, "b");
      IO.println(graph.edgeCount());  // 2
      graph.addEdge(0, 1, "c");
      IO.println(graph.edgeCount());  // 2
                    

    Ajouter la méthode edgeCount() sachant que l'on veut une implantation ayant une complexité pire cas en O(1).
    Vérifier que les tests marqués "Q3" passent.

  4. On souhaite ajouter à l'interface Graph la méthode neighbors(v) qui renvoie les voisins (les sommets to des arcs sortants) de v sous la forme d'un IntStream.
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 3, "b");
      graph.addEdge(0, 1, "a");
      IO.println(graph.neighbors(0).boxed().toList());  // [1, 3]
                    

    En termes d'implantation, l'idée est de créer un IntStream avec range() et de filtrer pour obtenir les indices des voisins.
    Implanter la méthode neighbors(int v).
    Vérifier que les tests marqués "Q4" passent.

  5. On souhaite maintenant, réécrire le spliterator sous-jacent d'un IntStream à la main. Cela permet de s'entraîner à écrire un spliterateur et aussi de fournir une implantation un peu meilleure.
    Sachant que l'on veut créer un IntStream (pas un Stream), comment s'appelle l'interface du spliterator que l'on doit implanter ?
    Quelle méthode de la classe StreamSupport doit-on utiliser pour créer un IntStream à partir de ce spliterator ? Quels doivent être les arguments ?
    Pour faire simple, on ne vous demande pas que le spliterator puisse se couper en deux (trySplit). Pour le calcul de la taille approchée (estimateSize()), on peut renvoyer le nombre de voisins qu'il reste si v est connecté à tous les sommets.
    Commenter le code de l'ancienne méthode neighbors(int v) et implanter le spliterator sous forme de classe anonyme dans neighbors(int v), avec les méthodes tryAdvance(consumer), trySplit(), estimateSize() et characteristics().
    Pourquoi, pour ce cas précis, doit-on aussi fournir une implantation de la méthode getComparator() ?
    Vérifier que les tests marqués "Q5" passent.

  6. On souhaite maintenant pouvoir parcourir les arcs sortants d'un sommet avec la méthode edges(v). Un arc est représenté par un record interne de Graph
      record Edge<E>(int from, int to, E value) { }
                
    et la méthode edges est déclarée dans l'interface avec le type de retour Iterable<Edge<E>>.
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 3, "b");
      graph.addEdge(0, 1, "a");
      for (Graph.Edge<String> edge : graph.edges(0)) {
        IO.println(edge);  // Edge[from=0, to=1, value=a] puis
                           // Edge[from=0, to=3, value=b]
      }
                

    Dans MatrixGraph, on va implanter une version simple qui renvoie une List. Dans l'interface, le type de retour est Iterable, mais on veut que la classe MatrixGraph déclare que la méthode edges() renvoie une List<Edge<E>>.
    Est-ce possible ?
    Écrire l'implantation de la méthode edges(int v) en utilisant un stream.
    Vérifier que les tests marqués "Q6" passent.

  7. Construire une liste à chaque appel de edges(int v) est coûteux alors que l'on pourrait créer les arcs au fur et à mesure. On souhaite remplacer la liste par un Iterable qui lit la matrice à la demande.
    L'idée est que edges renvoie un Iterable dont la méthode iterator() renvoie un itérateur qui parcourt la ligne de v au fur et à mesure :
    • hasNext() indique s'il y a une prochaine case non null.
    • next() renvoie le prochain Edge

    Pour implanter cet itérateur (un itérateur filtrant), on va créer dans le code de l'itérateur une helper method nextColumn(int column) qui prend en paramètre une colonne de la matrice et renvoie la prochaine colonne qui contient une valeur.
    Implanter la méthode edges(int v).
    Vérifier que les tests marqués "Q7" passent.
    Note : Iterable est une interface fonctionnelle, on peut donc utiliser une lambda.

  8. On souhaite enfin pouvoir supprimer un arc avec removeEdge(from, to) qui supprime l'arc et renvoie sa valeur, ou null s'il n'y avait pas d'arc.
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      IO.println(graph.removeEdge(0, 1));  // a
      IO.println(graph.removeEdge(0, 1));  // null
      IO.println(graph.edgeCount());  // 0
                    

    Implanter la méthode removeEdge.
    Vérifier que les tests marqués "Q8" passent.

  9. Maintenant que l'on a écrit removeEdge, par cohérence, il faut aussi pouvoir supprimer un arc à partir de l'itérateur. La méthode remove() de l'itérateur supprime du graphe l'arc renvoyé par le dernier appel à next().
    Implanter la méthode remove de l'itérateur.
    Vérifier que les tests marqués "Q9" passent