TD 1 - Le plan du métro de Paris


Le but du TD est de commencer à manier les graphes et de mettre en pratique le parcours en profondeur. Le minimum à faire en deux heures sont les exercices 1 et 2.

À la fin du TD, vous devrez déposer vos programmes en tapant dans une fenêtre shell une commande :

/users/profs/info/Depot/INF_431/deposer [pgm] TD_1 [gpe]

[pgm] doit être remplacé par la liste des noms des fichiers contenant vos programmes et [gpe] doit être remplacé par votre numéro de groupe. Par exemple, pour déposer des fichiers Liste.java et Graphe.java qui sont dans le répertoire courant, un élève du groupe 18 doit taper :

/users/profs/info/Depot/INF_431/deposer Liste.java Graphe.java TD_1 18

Éléments fournis

Voici, un plan du métro de Paris qui va nous servir d'application. On dispose d'une liste des stations par ordre alphabétique dans le fichier stations.data. Ce fichier doit être installé dans le répertoire de travail, il sert à localiser les stations pour la représentation graphique.
D'autre part, les lignes du métro sont décrites dans le fichier lignes.data. Il s'agit là du fichier le plus complet, on utilisera aussi un fichier lignes2.data qui décrit un réseau sérieusement perturbé.

Le programme qui est fourni en deux fichiers, MetroUtil.java et Metro.java, réalise déjà la lecture des données. Il n'est pas utile d'en lire le détail pour faire le TD.
Le fichier MetroUtil.java contient 2 classes, Station et Graphique. Les indications pour les utiliser seront données au fur et à mesure des besoins.

Une station sera identifiée par un numéro, commençant à 1, c'est son rang dans le fichier stations.data et on peut facilement trouver le numéro d'une station en regardant ce fichier avec un éditeur de texte.

Le fichier Metro.java contient la classe Graphe qui est donnée dans un état embryonnaire. C'est là que l'on va placer l'essentiel du travail demandé.
Pour l'instant, le constructeur Graphe(int taille) ne fait rien et la procédure ajouterArc(Graphe g, int ori, int dst, String ligne) se contente de dessiner un arc entre deux stations.

La première chose que l'on fera dans l'exercice 1, c'est de modifier tout cela pour construire effectivement le graphe du métro.
Les exemples donnés dans l'énoncé seront à placer dans la procédure test de la classe Graphe.

On peut exécuter ce programme en l'état par la commande java Graphe lignes.data
On obtient un schéma comparable au plan fourni. On fera de même java Graphe lignes2.data pour utiliser l'autre fichier.

Exercice 1. Construction du graphe et tests

1.1 Graphe par listes d'adjacence

Nous allons définir le graphe par un tableau listeSucc de listes de successeurs dont chaque élément listeSucc[i] sera la liste des numéros des stations qui suivent directement la station numéro i en empruntant une des lignes du métro. Chaque élément de la liste mémorisera également le nom de la ligne empruntée pour joindre la station de destination. Un nom de ligne sera une chaîne de caractères qui code aussi le sens de parcours, par exemple "1-a" et "1-b" pour les deux sens de la ligne 1.

Écrire une classe Successeur pour représenter les éléments de listes de successeurs. Compléter le constructeur Graphe(int taille) qui doit initialiser le tableau listeSucc avec des listes de successeurs vides. Attention, les numéros de stations iront de 1 à taille-1 et, en particulier, listeSucc[0] restera vide.

1.2 Création des listes de successeurs

Modifier la procédure ajouterArc(Graphe g, int ori, int dst, String ligne) pour qu'elle ajoute, seulement, la paire (dst,ligne) en tête de la liste des successeurs de ori dans le graphe g.

Remarques

On pourrait penser qu'il s'agit d'un graphe non orienté mais il y a quelques cas de stations qui ne sont desservies que dans un seul sens, sur les lignes 7bis et 10. La construction d'un arc et celle de son réciproque sont donc dissociées (dans le fichier lignes.data) et font ainsi l'objet de deux appels à ajouterArc.

Il arrive aussi que des stations soient déservies par des lignes parallèles, par exemple les lignes 8 et 9 entre Richelieu - Drouot et République. Dans ce cas, un numéro de station figurera plusieurs fois dans une liste de successeurs, mais avec des désignations de lignes différentes.

1.3 Tests

Il s'agit de petits tests faciles à programmer qui permettent de vérifier que la structure est correcte et que l'on sait l'utiliser.

Exercice 2. Parcours en profondeur

Le but de cet exercice est de mettre au point le parcours en profondeur qui est la base de nombreux algorithmes sur les graphes. On utilisera surtout le fichier de test lignes2.data qui donne des résultats plus facilement vérifiables.

2.1 Préparation

Pour faire un parcours en profondeur, nous avons besoin de mémoriser pour chaque station si elle a déjà été visitée. On utilisera pour cela un tableau boolean[] dejaVu.

Rajouter les variables nécessaires dans la classe Graphe et modifier le constructeur en conséquence. Il est bon aussi de prévoir tout de suite une procédure initialisationParcours qui (ré)initialise les données affectées par le parcours.

2.2 Parcours en profondeur : en partant d'un noeud

Écrire une procédure récursive static void dfs(Graphe g, int i) qui parcourt en profondeur le graphe à partir de la station de numéro i. Pour mémoire, cela veut dire qu'on marque cette station comme déjà vue et que l'on inspecte récursivement, une à une, les stations de sa liste de successeurs pour visiter celles qui ne l'ont pas encore été.

Pour suivre l'ordre de parcours, on écrit de la même manière une procédure dfsTrace qui va lister les noms des stations au fur et à mesure de leur visite.
Par exemple, avec le fichier lignes2.data, dfsTrace(g, 19); va donner :

Bastille
Chemin Vert
Saint-Sébastien - Froissart
Filles du Calvaire
République
Goncourt
Belleville
Couronnes
Ménilmontant
Père Lachaise
Saint-Maur
Parmentier
Oberkampf
Richard Lenoir
Bréguet - Sabin
Ledru Rollin
Faidherbe - Chaligny
Reuilly - Diderot
Gare de Lyon

Ce résultat est obtenu en plaçant l'instruction d'impression au début de la visite.

2.3 Existence d'un chemin par un parcours en profondeur

Écrire une fonction static boolean existeChemin(Graphe g, int ori, int dst) qui réalise un parcours en profondeur à partir de la station ori puis regarde si dst a été visité durant ce parcours. Pour l'instant, on ne cherche pas à exprimer le chemin, ce sera l'objet des exercices 3 et 4.

Pour tester :

    int ori = 107; // num 107 = Gallieni
    int dst = 163; // num 163 = Mairie de Montreuil
    System.out.println("chemin de " + Station.leNom(ori) + " à " + Station.leNom(dst) + " : " + existeChemin(g, ori, dst));
    ori = 276; // num 276 = Saint-Lazare
    dst = 195; // num 195 = Opéra
    System.out.println("chemin de " + Station.leNom(ori) + " à " + Station.leNom(dst) + " : " + existeChemin(g, ori, dst));

Avec le fichier lignes2.data, on doit trouver qu'il y a bien un chemin entre Gallieni et Mairie de Montreuil mais il n'y en a pas entre Saint-Lazare et Opéra.

Exercice 3. Calcul de chemins

Le but est maintenant de calculer un chemin d'une station à une autre, s'il en existe un.

3.1 Visualisation de l'arborescence de Trémaux

Pendant le parcours en profondeur, si lors de la visite d'une station i, on part visiter la station j, alors on va dessiner l'arc entre i et j. On obtient ainsi le dessin d'une arborescence de Trémaux.
Écrire une procédure dfsDessin, adaptée de dfsTrace qui dessine l'arborescence de Trémaux à partir d'une station racine. On utilisera Station.relier pour tracer un arc.
Pour tester :

    Graphique.couleur(Color.red);
    initialisationParcours(g);
    dfsDessin(g, 19); // num 19 = Bastille

Écrire ensuite une procédure dessinForet, qui dessine des arborescences de Trémaux recouvrant tout le réseau. Cela veut dire qu'on cherche dans l'ordre une station non encore visitée, qu'on parcourt son arborescence avec dfsDessin et qu'on continue jusqu'à ce que toutes les stations aient été vues. Au passage on utilisera Station.marquer(i, 4) pour dessiner la station racine i avec un gros point de taille 4.

Par exemple, avec le fichier lignes2.data, on doit trouver 7 arborescences dont 3 relativement grosses, commençant respectivement par Abbesses, Alésia et Bastille, et 4 racines isolées : La Plaine - Voyageurs, Maisons-Alfort - Alfortville, Saint-Denis et Saint-Sulpice, voici le détail que donnerait dfsTrace.

3.2 Construction de l'arborescence de Trémaux

Si lors de la visite d'une station i, on part visiter la station j, on peut définir i comme le père de j dans l'arborescence de Trémaux.

Rajouter dans la classe Graphe un tableau int[] pere qui permettra de stocker pour une station d'indice i, l'indice pere[i] de son père dans l'arborescence.
Modifier le constructeur, l'initialisation et adapter une procédure de parcours en profondeur pour réaliser le calcul de l'arborescence de Trémaux à partir d'une station.

3.3 Retrouver le chemin du parcours

Écrire une procédure static void chemin(Graphe g, int ori, int dst) qui affiche la suite des stations constituant le chemin de ori vers dst, s'il en existe un. En construisant l'arborescence de Trémaux à partir de ori, on remarque que le tableau pere nous donne le chemin, mais à l'envers !
Dans le cas d'un graphe non orienté, une astuce consisterait à calculer l'arborescence à partir de dst et il n'y aurait plus qu'à suivre les liens donnés par pere en partant de ori. Dans le cas d'un graphe orienté, on doit calculer l'arborescence à partir de ori. Pour écrire le chemin dans le bon sens, on s'inspirera de la manière d'écrire une liste à l'envers, récursivement.

Pour tester :

    int ori = 19;  // num 19 = Bastille
    int dst = 111; // num 111 = Gare de Lyon
    System.out.println("chemin de " + Station.leNom(ori) + " à " + Station.leNom(dst) + " : ");
    chemin(g, ori, dst);
    ori = 107; // num 107 = Gallieni
    dst = 163; // num 163 = Mairie de Montreuil
    System.out.println("chemin de " + Station.leNom(ori) + " à " + Station.leNom(dst) + " : ");
    chemin(g, ori, dst);

Avec le fichier lignes2.data, "le" chemin de Bastille à Gare de Lyon est :

Bastille
Ledru Rollin
Faidherbe - Chaligny
Reuilly - Diderot
Gare de Lyon

Le chemin de Gallieni à Mairie de Montreuil est beaucoup plus long, en voici le détail.
Et si on recommence avec le fichier lignes.data, on trouve un chemin encore plus long !

Exercice 4. Parcours itératifs et plus courts chemins

4.1 Parcours en profondeur itératif

Écrire une procédure static void dfsIteratif(Graphe g, int ori) qui fait un parcours en profondeur à partir de la station de numéro ori de manière itérative (sans appel récursif). On utilisera pour cela une pile contenant les numéros des stations en attente d'être visitées.
Comme en 2.2, on va lister les noms des stations au fur et à mesure de leur visite.

Par exemple, avec le fichier lignes2.data, dfsIteratif(g, 19); va donner :

Bastille
Gare de Lyon
Reuilly - Diderot
Faidherbe - Chaligny
Ledru Rollin
Bréguet - Sabin
Richard Lenoir
Oberkampf
République
Parmentier
Saint-Maur
Père Lachaise
Ménilmontant
Couronnes
Belleville
Goncourt
Filles du Calvaire
Saint-Sébastien - Froissart
Chemin Vert

Expliquer pourquoi l'ordre d'exploration est différent de celui vu en 2.2.

4.2 Parcours en largeur

Écrire une procédure static void bfsIteratif(Graphe g, int ori) qui fait un parcours en largeur à partir de la station de numéro ori. Dans un parcours en largeur, on visite d'abord tous les successeurs et ensuite les successeurs des successeurs non encore visités et ainsi de suite.
Les premiers successeurs rencontrés seront visités en premier, il faut donc utiliser une file "first in first out".

Par exemple, avec le fichier lignes2.data, bfsIteratif(g, 19); va donner :

Bastille
Chemin Vert
Ledru Rollin
Bréguet - Sabin
Gare de Lyon
Saint-Sébastien - Froissart
Faidherbe - Chaligny
Richard Lenoir
Reuilly - Diderot
Filles du Calvaire
Oberkampf
République
Goncourt
Parmentier
Belleville
Saint-Maur
Couronnes
Père Lachaise
Ménilmontant

4.3 Plus court chemin

Adapter ce qui a été fait à l'exercice 3 pour calculer et afficher un plus court chemin (au nombre de stations) plutôt qu'un chemin quelconque.

Pour tester :

    int ori = 19;  // num 19 = Bastille
    int dst = 111; // num 111 = Gare de Lyon
    System.out.println("plus court chemin de " + Station.leNom(ori) + " à " + Station.leNom(dst) + " : ");
    plusCourtChemin(g, ori, dst);
    ori = 107; // num 107 = Gallieni
    dst = 163; // num 163 = Mairie de Montreuil
    System.out.println("plus court chemin de " + Station.leNom(ori) + " à " + Station.leNom(dst) + " : ");
    plusCourtChemin(g, ori, dst);

Entre Bastille et Gare de Lyon, on trouve alors l'arc direct. Entre Gallieni et Mairie de Montreuil, avec le fichier lignes.data, on trouve le plus court chemin :

plus court chemin de Gallieni à Mairie de Montreuil : 
Gallieni
Porte de Bagnolet
Gambetta
Père Lachaise
Philippe Auguste
Alexandre Dumas
Avron
Nation
Buzenval
Maraîchers
Porte de Montreuil
Robespierre
Croix de Chavaux
Mairie de Montreuil

Avec le fichier lignes2.data, on trouve un plus court chemin, du reste assez long, en voici le détail. On remarquera la bizarrerie du parcours entre Miromesnil et Roosevelt.


URL: https://www.enseignement.polytechnique.fr/profs/informatique/Philippe.Chassignet/04-05/INF_431/td_1.html

Pour toutes suggestions, commentaires ou remarques, email : Philippe.Chassignet@polytechnique.fr