:: Enseignements :: ESIPE :: E4INFO :: 2026-2027 :: Java Avancé ::
![[LOGO]](http://monge.univ-eiffel.fr/ens/resources/mlv.png) |
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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
© Université de Marne-la-Vallée