TD 2

Le but de ce TD est d'approfondir les utilisations des parcours en profondeur. Il est nécessaire d'avoir traité les deux premiers exercices du TD 01. Le minimum à faire en deux heures est l'un des deux exercices suivants au choix. Le deuxième est nettement plus difficile que le premier.

Exercice 1. Tri topologique

Il s'agit ici de construire une version orientée du graphe du jeu de la lettre qui saute (TD 01) et d'en calculer un tri topologique. Les fonctions demandées ici sont légèrement différentes de celles du cours.

Pour obtenir un graphe orienté, on considère qu'un mot a a un mot b pour successeur s'ils ne diffèrent que d'une lettre et si la lettre de a qui diffère est plus petite que la lettre de b correspondante. Ce graphe définit une sorte de dictionnaire où la définition d'un mot est sa liste de successeurs. Le but de l'exercice est d'écrire le dictionnaire (c'est à dire chaque mot et sa définition) de sorte que les mots utilisés dans la définition aient déjà été définis précédemment. Un tel ordre est l'inverse d'un tri topologique (dans un tri topologique, chaque mot doit apparaître avant ses successeurs).

1.1 Graphe orienté

Modifier lettreQuiSaute () et éventuellement ajouterArete () pour qu'un mot d'indice d ne soit rajouté à la liste de successeurs d'un mot d'indice s que si les deux mots ne diffèrent que d'une lettre et si la lettre par laquelle le mot d'indice d diffère est plus grande que celle de du mot d'indice s. On dira indifféremment que le mot d'indice d est successeur de celui d'indice s ou que le mot d'indice d apparaît dans la définition de celui d'indice s. On pourra modifier diffUneLettre () ainsi :

    static boolean diffUneLettre (String a, String b) { 
	// a et b supposes de meme longueur
	int i=0 ;
	while (i<a.length () && a.charAt (i) == b.charAt (i)) 
	    ++i ;
	if (i == a.length ())
	    return false ;
	if (a.charAt (i) > b.charAt (i))
	    return false ; // version orient'ee
	++i ;
	while (i<a.length () && a.charAt (i) == b.charAt (i)) 
	    ++i ;
	return i == a.length () ;
    }

1.2 Détection de cycle

Un cycle est une suite circulaire de mots telle qu'un mot a toujours le mot suivant dans sa définition. Si jamais le graphe possède un cycle, il ne sera pas possible d'écrire le dictionnaire de sorte qu'un mot apparaissant dans une définition soit toujours défini auparavant. Nous allons donc tout d'abord tester si le graphe contient des cycles.

Écrire une fonction static boolean dfsCycle (Graphe g, int x) qui parcourt en profondeur à partir de x et renvoie true si un cycle est atteignable à partir de x, c'est à dire s'il existe un chemin partant de x qui boucle sur lui-même. Pour cela on pourra utiliser un tableau de booléens visiteEnCours pour marquer les sommets dont la visite est en cours, c'est à dire dont l'appel à dfsCycle est en cours d'exécution.

Remarquons que la suite d'appels récursifs en cours correspond à un chemin dans le graphe (chaque appel récursif se fait sur un successeur du sommet de l'appel précédant). D'autre part, si un cycle est atteint lors du parcours, alors fatalement un des appels récursifs finira par tomber sur un successeur en cours de visite.

Tester la fonction en partant de gag d'indice 0 dans le graphe de dico3court qui ne contient pas de cycle. Un cycle devrait par contre être détecté en rajoutant arc d'indice 22 à la liste de successeurs de guy d'indice 9 :

      g.listeSucc[9] = new Liste (22, g.listeSucc[9]) ;
      System.out.println (dfsCycle (g, 0)) ;

1.3 Tri topologique

Modifier la fonction précédente pour que les mots visités soient affichés dans l'ordre inverse d'un tri topologique s'il n'y a pas de cycle, c'est-à-dire que tous les successeurs d'un mot doivent être affichés avant le mot.

Écrire une fonction static void invTriTopologique (Graphe g) qui affiche tous les mots du graphe g dans l'ordre inverse d'un tri topologique et qui provoque une erreur si jamais il y a un cycle.

Modifier un seul caractère de votre programme de sorte qu'un tri topologique soit affiché. (Indice : on ne construira pas forcément le graphe dont on veut afficher le tri topologique.)

Question réflexion : y a-t-il un tri topologique évident pour le graphe orienté ainsi défini sur les mots ?

1.4 Visualiser les cycles

Visualiser avec dot un cycle du graphe lorsqu'il y en a un. On pourra stocker le fils en cours de visite lors du parcours en profondeur et modifier la fonction d'affichage du graphe. La commande dot est en effet plus adaptée pour dessiner des graphes orientés. Attention la syntaxe pour les graphes orientés (digraph) est différente de celle des graphes non orientés (graph) : l'orientation des arêtes est signifiée par des -> à la place des --. Votre programme doit alors afficher le graphe sous la forme :

digraph dico {
  node [color=red, fontcolor=red, fillcolor=white, style=filled];
  edge [style=bold, color=blue];
  gag -> gaz ;
  gag -> gai ;
  gai -> gui ;
  guy -> arc [color=green];
  ...
}

Le rajout de [color=green] derrière un arc permet d'indiquer à dot de le dessiner en vert plutôt qu'avec la couleur définie par défaut (bleu).

La suite de commandes suivantes est une manière de stocker le graphe sorti par votre programme dans un fichier g.dot (au lieu de l'afficher), puis d'en faire un dessin dans un fichier postscript g.ps avec dot et de le visualiser avec kghostview :

java Graphe > g.dot
dot -Tps g.dot > g.ps
kghostview g.ps

Un aperçu pour dico3court

Une solution.

1.5 Visualiser l'arborescence de Trémaux

Lors d'un parcours en profondeur, si lors de la visite d'un mot d'indice x, un successeur d'indice y est vu par x, on peut définir x comme le père de y (l'appel récursif sur y a été fait depuis celui sur x). On obtient alors une arborescence de Trémaux. Rajouter dans la classe Graphe une variable pere qui permettra de stocker pour le mot d'indice i, l'indice pere[i] de son père dans l'arborescence.

Visualiser l'arborescence de Trémaux produite par un parcours en profondeur. On pourra aussi afficher le numéro de visite d'un sommet avec la syntaxe :

  gag [label="gag 0"] ;

Un aperçu pour dico3court

Une solution.

Exercice 2. Composantes bi-connexes

Le but dans cet exercice est de calculer les composantes bi-connexes du graphe (non orienté) de la lettre qui saute défini au TD 01. Le calcul des composantes bi-connexes est similaire à celui des composantes fortement connexes et mieux adapté à l'exemple du jeu de la lettre qui saute. Il est important de comprendre pourquoi les propriétés utilisées sont vraies pour bien les programmer, n'hésitez pas à poser des questions.

2.1 Point d'attache

Reprendre la version non orientée du graphe de la lettre qui saute et le parcours en profondeur tel que programmé dans le TD 01.

Modifier les deux fonctions de parcours en profondeur pour que la fonction visit calcule pour chaque mot son numéro et le numéro de son point d'attache. On stockera ces deux séries de nombres dans deux tableaux.

Rappel : les sommets sont numérotés au fur et à mesure où ils sont visités. (Le premier sommet visité est numéroté 0, le suivant 1, ...) On appelle ici visite du mot tout ce qui se passe durant l'appel récursif de dfs sur ce mot. On supposera qu'un mot est numéroté dès le début de sa visite. Il faut noter que les successeurs d'un mot visité sont soit déjà visités soit visités récursivement durant la visite du mot. On appelle fils d'un mot, ses successeurs pour lesquels on fait un appel récursif à dfs. Le numéro de point d'attache d'un mot est le plus petit numéro parmi son propre numéro, les numéros de ses successeurs et les numéros de point d'attache de ses fils. Vu autrement, le numéro de point d'attache d'un mot est le minimum de son numéro et des numéros de tous les successeurs de tous les mots visités récursivement pendant sa visite.

2.2 Points d'articulation

Modifier les fonctions précédentes pour qu'elles affichent les points d'articulation.

Rappel : les points d'articulation sont ceux qui déconnectent leur composante connexe si on les retire. Le mot de départ d'un parcours en profondeur est un point d'articulation s'il a au moins deux fils (en effet, les deux fils seront déconnectés l'un de l'autre si on le retire puisque le parcours récursif sur le premier n'a pas atteint le deuxième). Un mot visité ensuite est un point d'articulation s'il a un fils de point d'attache de numéro supérieur ou égal au sien. Dans le cas non orienté, un sommet a un point d'attache de numéro inférieur à celui de son père puisque son père fait partie de sa liste de successeurs. Un point d'articulation différent du sommet de départ du parcours est donc un mot dont un fils l'a pris pour point d'attache. En effet, si on retire le mot, ce fils sera déconnecté des sommets visités avant le mot puisque le parcours récursif sur ce noeud n'a pas atteint de mot visité avant le mot.

Par exemple, les points d'articulation du graphe de dico3court sont ace, air, are, gre, gue, gui, gai et glu.

Question réflexion : quels sont les mot qui apparaissent forcément dans un chemin de lion à peur connaissant le chemin lion pion paon pain paix poix poux pour peur (calculer les points d'articulation du graphe de Dicos.dico4 pour répondre).

2.3 Composantes bi-connexes versus composantes fortement connexes

Le calcul des composantes bi-connexes est similaire à celui des composantes fortement connexes. Nous précisions dans ce paragraphe les similarités et les différences. La principale ressemblance vient du fait que le parcours en profondeur va parcourir les composantes de manière similaire : une fois entré dans une composante, le premier appel récursif va visiter toute la composante. Notons cependant quelques différences fondamentales :

2.4 Calcul des composantes bi-connexes

Modifier les fonctions précédentes pour qu'elles affichent les composantes bi-connexes. Pour cela, remarquons lorsque le premier mot d'une composante bi-connexe est visité, la composante bi-connexe sera entièrement visitée durant les appels récursifs du deuxième mot visité dans la composante (qui sera forcément un successeur du premier mot). En empilant les indices des mots au fur et à mesure de leur visite dans une pile, on peut retrouver les mots de la composante à la sortie de l'appel récursif pour le premier fils dans la composante. (La composante identifiée est donc celle de l'arête reliant le noeud à ce fils.)

Pour le mot de départ d'un parcours en profondeur, on obtiendra une composante bi-connexe pour chacun de ses fils. Pour un mot visité par la suite, on obtiendra une composante bi-connexe pour chacun de ses fils dont le point de d'attache est le mot lui-même.

Pour un sommet donné, on peut détecter plusieurs composantes bi-connexes associées aux arêtes avec plusieurs de ses fils. Il faut donc penser à empiler plusieurs fois le sommet dans la pile au besoin.

Par exemple, les composantes bi-connexes du graphe de dico3court sont :

apr avr air 
acm ace 
ace aie ail air ait arc art are 
are gre 
gre gue 
guy gue gui 
gui gai 
gai gaz gag 
gel 
gks 
gin 
alu glu 
glu gnu 
ami agi 
and 
mur sur 
mat 

En profiter pour regarder quelles sont les composantes bi-connexes de lion et peur.

Une solution.

2.5 Visualisation des composantes bi-connexes

Afficher l'ensemble des arêtes de chaque composante bi-connexe. Le graphe étant orienté symétrique, une arête correspond à deux arcs opposés l'un de l'autre. On pourra empiler les extrémités des arcs rencontrés par le parcours en profondeur de sorte à pouvoir afficher la liste des arêtes de chaque composante bi-connexe (avec deux piles par exemple). Pour ne pas afficher les arêtes en double, on fera attention à n'empiler qu'un seul des deux arcs associés.

Dessiner le graphe des mots avec neato en faisant apparaître les composantes bi-connexes par la couleur des arêtes : toutes les arêtes d'une même composante seront affichées de la même couleur. On pourra aussi afficher les points d'articulation avec un fond spécial. On peut indiquer à neato les choix de couleur par des options entre crochets. On peut indiquer la couleur de chaque arête par trois réels (le premier code le ton, le deuxième la saturation et le troisième la luminosité) avec la syntaxe suivante :

graph dico {
  node [style=filled, fontcolor=red];
  edge [style=bold];
  gai -- gag [color=".1,.5,.6"];
  gag -- gaz [color=".1,.5,.6"];
  gaz -- gai [color=".1,.5,.6"];
  gai -- gui [color=".2,.5,.6"];
  gui -- guy [color=".3,.5,.6"];
  guy -- gue [color=".3,.5,.6"];
  gue -- gui [color=".3,.5,.6"];
  gue [fillcolor=green] ;
  ...
}

Un aperçu pour dico3court

Une solution.


Sujet proposé par Laurent Viennot Last modified: Thu Mar 6 15:51:33 CET 2003