TD 3 - Le plan du métro de Paris, suite


Le minimum à faire est de terminer la partie du TD 1 qui est explicitée ici comme exercice 0 et de traiter ensuite l'exercice 1.

À 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_3 [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_3 18

Éléments fournis

Pour un rappel, voir le TD 1.

Exercice 0. Terminer le début du TD 1

Si ce n'est pas fait, traitez en priorité les exercices 1 et 2 du TD 1.

Exercice 1. Composantes connexes

À partir de cette question, jusqu'à la fin de ce TD et aussi pour le DM 1 à venir, le graphe du métro est maintenant supposé non orienté.

On partira donc d'une copie Metro2.java du fichier Metro.java afin de ne pas mélanger les deux approches.

Maintenant, dans le fichier décrivant le plan du métro, les lignes ne sont donc plus dédoublées selon chacune des directions. On utilisera le fichier lignes3.data qui correspond à un réseau sérieusement perturbé.

1.1 Construction des listes de successeurs

Adapter la procédure ajouterArc(Graphe g, int ori, int dst, String ligne) de sorte qu'à chaque appel une arête est maintenant ajoutée, c'est-à-dire un arc dans les deux sens : de ori à dst et réciproquement.

Pour vérifier, on peut réutiliser la procédure dfsTrace du TD 1. Par exemple, avec le fichier lignes3.data, dfsTrace(g, 1); doit afficher :

Abbesses
Lamarck - Caulaincourt
Jules Joffrin
Marcadet - Poissonniers
Marx Dormoy
Porte de la Chapelle
Château Rouge
Barbès - Rochechouart
Anvers
Simplon
Porte de Clignancourt

1.2 Calcul de la taille d'une composante connexe

Écrire une fonction récursive static int tailleComposante(Graphe g, int i) qui permet de compter le nombre de stations dans la composante connexe de la station de numéro i.
On pourra se servir du tableau dejaVu qu'on n'oubliera pas d'initialiser par la procédure initialisationParcours.

Par exemple, avec le fichier lignes3.data,

System.out.println(tailleComposante(g, 1));  // num 1  = Abbesses
System.out.println(tailleComposante(g, 93)); // num 93 = Eglise d'Auteuil

vont donner :

11
1

1.3 Énumération des composantes connexes

Écrire une procédure static void listerCompConnexes(Graphe g) qui écrit une liste des composantes connexes avec leurs tailles respectives.
Au passage on pourra utiliser Station.marquer(i, 4); pour dessiner d'un gros rond la station racine i de la chaque composante.
Dans le cas des stations isolées, on évitera de calculer la taille de la composante connexe triviale.

Ainsi, avec le fichier lignes3.data, on devra afficher quelque chose qui ressemble à :

Taille de la composante de Abbesses (1) = 11
Taille de la composante de Alésia (2) = 144
Taille de la composante de Alma - Marceau (5) = 71
Taille de la composante de Anatole France (6) = 4
Taille de la composante de Argentine (8) = 34
Taille de la composante de Bastille (19) = 19
Taille de la composante de Bd Masséna (20) = 2
Taille de la composante de Carrefour Pleyel (49) = 7
- Eglise d'Auteuil (93) : isolée
Taille de la composante de Esplanade de La Défense (95) = 4
Taille de la composante de Gabriel Péri (105) = 2
Taille de la composante de Gallieni (107) = 3
Taille de la composante de Jourdain (131) = 8
- La Plaine - Voyageurs (141) : isolée
- Maisons-Alfort - Alfortville (167) : isolée
- Porte d'Auteuil (222) : isolée
- Saint-Denis (268) : isolée
- Saint-Ouen (282) : isolée
- Saint-Sulpice (287) : isolée

On a mis entre parenthèses les numéros des stations racines. On rappelle que le nom d'une station s'obtient par la fonction Station.leNom(int numero).

Exercice 2. Cycles

2.1 Détection de cycles

Écrire une fonction récursive static boolean dfsCycle(Graphe g, int i, int j) qui détecte la présence d'un cycle dans la composante connexe de la station de numéro i, alors que l'on vient de la station j.
On fera attention au fait qu'il s'agit ici d'un graphe non orienté. Par conséquent, il faut éviter les cycles triviaux formés d'un aller-retour entre deux stations et on ne suivra donc pas les arcs de retour de i vers j.
On pourra s'inspirer de la fonction cycleEn vue à l'Amphi 2, en se servant d'un tableau int[] etat et de trois constantes final static int NON_VU=0, EN_COURS=1, FINI=2; pour coder les états d'un noeud durant la dfs. On notera cependant que la recherche d'un cycle ne peut pas rencontrer de sommet dans l'état FINI.
On n'oubliera pas d'initialiser le tableau etat dans la procédure initialisationParcours.

Avec le fichier lignes3.data, dfsCycle(g, 1, 0) et dfsCycle(g, 93, 0) doivent renvoyer false alors que dfsCycle(g, 8, 0) et dfsCycle(g, 19, 0) doivent renvoyer true (il s'agit respectivement des stations Abbesses, Eglise d'Auteuil, Argentine et Bastille).

2.2 Construction d'un cycle

Exercice 3. Points d'articulation

Cet exercice consiste à implémenter progressivement la recherche des points d'articulation selon une méthode légèrement différente de celle vue en Amphi 2.

3.1 Ordre de la dfs

On va utiliser un tableau int[] num pour mémoriser les numéros d'ordre des sommets par la dfs. Ainsi, ce tableau nous dira que la station i est la num[i]ième visitée durant le parcours. On utilisera aussi un tableau int[] invNum pour réaliser la fonction inverse, c'est-à-dire que invNum[k] donnera le numéro de la kième station visitée.
On n'oubliera pas d'initialiser ces deux tableaux dans la procédure initialisationParcours.

Écrire une fonction static int dfsNum(Graphe g, int i, int n) qui remplit les deux tableaux en explorant le graphe à partir de la station i alors que les numéros d'ordre jusqu'à n sont déjà attribués (on n'utilisera pas de compteur en variable globale pour cette information). Cette fonction doit donc ranger n+1 dans num[i] et i dans invNum[n+1] puis continuer récursivement sur le reste de la composante connexe de i. La fonction retourne finalement le plus grand numéro d'ordre utilisé.

Le tableau num est fondamental pour le calcul des points d'articulation. Le tableau invNum sera un auxilliaire utile, notamment pour énumérer une composante connexe sans relancer une dfs. Par exemple, avec le fichier lignes3.data,

int n = dfsNum(g, 1, 0);  //  station 1 = Abbesses
for ( int i = 1 ; i <= n ; ++i )
  if ( g.num[g.invNum[i]] != i )
    System.out.println("ERREUR");
  else
    System.out.println(Station.leNom(g.invNum[i]));

doit donner le même résultat que dfsTrace(g, 1); dans l'exemple de l'exercice 1.1.

3.2 Points d'attache

En prenant modèle sur dfsNum, écrire une fonction static int dfsAttache(Graphe g, int i, int n) qui calcule les points d'attache de tous les sommets accessibles depuis i.
On va utiliser un tableau int[] numAttache pour mémoriser les numéros d'attache. Plus précisément, numAttache[i] sera le numéro d'ordre dfs du point d'attache de la station i. On peut le calculer comme le minimum de :

Le paramètre n et la valeur de retour servent à gérer la numérotation, comme dans dfsNum.
On n'oubliera pas d'initialiser les trois tableaux (num, invNum et numAttache) dans la procédure initialisationParcours.

Par exemple, sachant que le numéro de la station qui est le point d'attache d'une station j, est donné par invNum[numAttache[j]],

int n = dfsAttache(g, 147, 0); //  station 147 = Ledru Rollin
for ( int i = 1 ; i <= n ; ++i )
  System.out.println( Station.leNom(g.invNum[i]) + " -> " + Station.leNom(g.invNum[g.att[g.invNum[i]]]) );

doit montrer qu'il y a 3 points d'attache Ledru Rollin, Bastille et République (avec le fichier lignes3.data) :

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

3.3 Points d'articulation


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

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