TP — Séance 5 — Graphes

Écrire, tester et mesurer les parcours, le tri topologique, Dijkstra et Kruskal en Java

TP de la séance 5 de Structures de données et algorithmes avancés : parcourir, ordonner, trouver le plus court chemin et l’arbre couvrant minimal.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Écrire les algorithmes du cours sur des graphes en listes d’adjacence : le parcours en largeur, le tri topologique et la détection de cycle par parcours en profondeur, l’algorithme de Dijkstra avec le tas binaire de la Séance 4, l’algorithme de Kruskal ; les faire passer par les tests JUnit fournis, les appliquer à un réseau de routes du Nord et du Centre du Sénégal, puis mesurer leur coût sur des graphes au hasard. Durée : une séance de TP.

À rendre. Le dépôt Git du projet (les classes complétées, les tests au vert) et un compte rendu d’une à deux pages qui répond aux questions marquées Observer, Expliquer et Modifier, en recopiant les sorties obtenues.

Préparation

Le TP se fait dans l’environnement Docker du cours (Java 17, Gradle 8, JUnit 5). Sur la machine, décompresser le code de départ, TP_S05_code_depart.zip, dans ~/dsa : le dossier TP_S05_code_depart/ apparaît. Le conteneur se lance depuis ce dossier :

cd ~/dsa
docker run -it --rm -v "$(pwd):/workspace" elbachirtoure/dsa-java:v2.0

Sous Windows (Git Bash), la commande docker run est précédée de MSYS_NO_PATHCONV=1. Dans le conteneur :

cd /workspace
new-project tp-s05
cd tp-s05
cp -r ../TP_S05_code_depart/. .
rm src/test/java/MainTest.java

Le code de départ contient quinze fichiers, quatorze dans src/main/java/ et GraphesTest.java dans src/test/java/ : la copie les range dans le projet, en remplaçant le Main.java créé par new-project, et rm supprime le MainTest.java créé par new-project. Le dépôt Git du projet se crée dans tp-s05 : git init -b main et l’identité locale, comme à l’étape 7 du TP-1.

Fichier Rôle
Graphe.java graphe en listes d’adjacence : addEdge et degre à écrire à l’étape 1
ParcoursLargeur.java parcours en largeur : bfs et chemin à écrire à l’étape 2
OrdreTopologique.java tri topologique : dfs à écrire à l’étape 3
CycleOriente.java détection d’un cycle orienté : dfs à écrire à l’étape 3
Dijkstra.java plus courts chemins : boucle et relacher à écrire à l’étape 4
Kruskal.java arbre couvrant minimal : construire et relies à écrire à l’étape 5
Arete.java, GraphePondere.java arête pondérée et graphe pondéré en listes d’arêtes, fournis
Entree.java, BinaryMinHeap.java entrée du tas de Dijkstra et tas binaire de la Séance 4, fournis
CarteRoutiere.java 12 villes, 15 tronçons (km) et des distances de référence, fourni
Dependances.java les classes du TP et leurs dépendances (11 sommets, 18 arcs), fourni
Generateur.java, Main.java graphes connexes au hasard et programmes d’observation, fournis
GraphesTest.java quinze tests JUnit, fournis

Les méthodes à écrire contiennent une consigne en commentaire et lèvent UnsupportedOperationException ; tout le reste est fourni. Les deux commandes du TP sont gradle --no-daemon test et gradle --no-daemon run --args="mode", où mode vaut villes, ordre, dijkstra, kruskal ou mesures. Le réseau de CarteRoutiere.java :

Observer. Lancer les tests avant d’écrire la moindre ligne : combien échouent, et avec quelle exception ?

Étape 1 : le graphe en listes d’adjacence

Graphe range, pour chaque sommet, la liste de ses voisins (List<Integer>[] adj) ; le booléen oriente est fixé à la construction. Écrire addEdge et degre en suivant les consignes en commentaire.

  1. Observer. Les tests grapheNonOriente, grapheOriente et sommeDesDegres doivent passer. Écrire les listes d’adjacence du graphe du test grapheNonOriente.
  2. Expliquer. Le test sommeDesDegres attend 30 pour la somme des degrés du réseau : relier ce nombre aux 15 tronçons. Quelle ville a le plus grand degré ?
  3. Modifier. Supprimer provisoirement, dans addEdge, l’ajout de v à la liste de w pour un graphe non orienté. Quels tests échouent, avec quels messages ? Pourquoi les deux tests de Kruskal échouent-ils aussi ? Revenir au code correct.

Étape 2 : le parcours en largeur

ParcoursLargeur remplit marque, edgeTo et distTo, et compte dans examines les entrées de listes lues et dans atteints les sommets marqués. Écrire bfs, puis chemin.

  1. Observer. Les quatre tests dont le nom commence par largeur doivent passer. Lancer le mode villes et recopier sa sortie.
  2. Expliquer. Le chemin rendu de Dakar à Bakel passe par Saint-Louis. Donner sa longueur en kilomètres, puis celle du chemin par Diourbel, Mbacké, Dahra, Linguère et Matam. Pourquoi le parcours rend-il le premier ?
  3. Expliquer. Pourquoi le nombre d’entrées lues vaut-il exactement \(2E\) ?
  4. Modifier. Remplacer provisoirement la file par une pile (push et pop d’ArrayDeque au lieu de add et remove). Quels tests échouent ? Relancer le mode villes : les nombres de tronçons sont-ils encore les plus petits ? Revenir à la file.

Étape 3 : tri topologique et cycle

Dependances décrit les classes du TP : un arc \(u\to v\) signifie que la classe \(v\) utilise la classe \(u\), qui doit donc être compilée avant. Écrire la méthode dfs d’OrdreTopologique, puis celle de CycleOriente.

  1. Observer. Les tests topologiquePostfixeInverse, topologiqueRespecteLesArcs, cycleAbsent et cyclePresent doivent passer. Lancer le mode ordre et recopier sa sortie.
  2. Expliquer. Retrouver à la main l’ordre [3, 0, 2, 1] attendu par topologiquePostfixeInverse : donner les appels de dfs et l’ordre postfixe.
  3. Expliquer. Le mode ordre ajoute ensuite l’arc Kruskal\(\to\)Graphe (Graphe utiliserait Kruskal). Expliquer le cycle écrit : pourquoi n’existe-t-il plus d’ordre de compilation ?
  4. Modifier. Dans OrdreTopologique, empiler provisoirement v avant d’examiner ses successeurs. Quels tests échouent ? Trouver dans la sortie du mode ordre un arc qui n’est pas respecté. Revenir au code correct.
  5. Expliquer. Combien d’appels de dfs sont imbriqués au plus sur une chaîne de \(n\) sommets ? Que risque-t-on pour \(n=100\,000\), et pourquoi ParcoursLargeur n’est-il pas concerné ?

Étape 4 : l’algorithme de Dijkstra

Dijkstra range ses entrées dans un BinaryMinHeap<Entree> ; une entrée (sommet, dist) est comparée par distance. Le constructeur initialise distTo, insère l’entrée de la source et appelle boucle ; chemin est fourni. Écrire boucle et relacher, qui comptent extractions, perimees et insertions.

  1. Observer. Les tests dijkstraDistances et dijkstraEntreesPerimees doivent passer. Lancer le mode dijkstra et recopier sa sortie.
  2. Expliquer. La colonne matrice donne, pour cinq villes, les distances par la route publiées pour le réseau réel. Les distances calculées concordent-elles ? Par où passe le chemin de Dakar à Kaolack, et quelle longueur aurait-il par Diourbel ?
  3. Expliquer. Relier le nombre d’extractions au nombre de villes et d’entrées périmées, puis comparer le nombre d’insertions à \(E+1\).
  4. Expliquer. Retrouver à la main, sur le graphe du test dijkstraEntreesPerimees, les 4 extractions et l’entrée périmée.
  5. Modifier. Supprimer provisoirement le test des entrées périmées dans boucle. Quel test échoue ? Les distances du mode dijkstra changent-elles ? Expliquer pourquoi. Revenir au code correct.

Étape 5 : l’algorithme de Kruskal

Kruskal examine les arêtes par poids croissant, extraites d’un BinaryMinHeap<Arete>, et construit la forêt dans un Graphe ; relies teste, par un parcours en largeur de la forêt, si deux sommets y sont déjà reliés, et compte les sommets atteints dans visites. La Séance 6 remplacera ce test par la structure Union-Find. Écrire construire, puis relies.

  1. Observer. Les tests kruskalPoids et kruskalCarte doivent passer, et les quinze tests au total. Lancer le mode kruskal, recopier sa sortie et dessiner l’arbre sur le réseau.
  2. Expliquer. Quelles sont les 3 arêtes rejetées, et quel cycle chacune aurait-elle fermé ? Quelle arête n’est jamais examinée, et pourquoi ?
  3. Modifier. Supprimer provisoirement le test relies dans construire. Quels tests échouent ? Le mode kruskal écrit-il encore un arbre couvrant ? Revenir au code correct.
  4. Expliquer. Combien de sommets un appel de relies peut-il atteindre au plus ? En déduire un majorant du coût de construire en fonction de \(V\) et \(E\).

Étape 6 : les coûts mesurés

Le mode mesures construit, pour \(V\) de 500 à \(4\,000\), un graphe connexe au hasard de \(E=4V\) arêtes (graine 2026) et y lance les trois algorithmes : il écrit le nombre d’entrées lues par le parcours en largeur, le nombre de comparaisons du tas de Dijkstra rapporté à \((V+E)\log_2 V\), et les sommets atteints par les tests de cycle de Kruskal rapportés à \(V^2\).

  1. Observer. Lancer le mode mesures et recopier le tableau.
  2. Expliquer. Quels rapports restent du même ordre quand \(V\) double ? En déduire l’ordre de grandeur du coût de chaque algorithme sur ces graphes.
  3. Expliquer. Estimer, à partir du tableau, le nombre de sommets atteints par les tests de cycle pour \(V=64\,000\). Pourquoi ce test doit-il être remplacé pour de grands graphes ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet