TNSI : TD PARCOURS EN PROFONDEUR - DFS - RÉCURSIF D'UN GRAPHE⚓︎

Ce TD détaille le Parcours en Profondeur, ou DFS - Depth First Search :uk:, en version RÉCURSIF, avec une Pile d'appels récursifs : on réutilisera la classe Graphe Orienté Non Pondéré.

Initialisation du Parcours en Profondeur⚓︎

Créer une méthode initialise_parcours() qui définit et initialise les variables d'instance suivantes, pour un graphe d'ordre n :
- BLANC = 0, GRIS = 1, NOIR = 2 sont des constantes d'état de chaque sommet
- self.Pere[s] :
  - Définition : contient le Père du sommet s durant le parcours du graphe
  - Initialisation : le Père de chaque sommet est initialisé à None
- self.admet_cycle :
  - Définition : variable contenant la réponse booléenne à la question: ce graphe contient-il un cycle?
  - Initialisation : self.admet_cycle = False
- self.cycles :
  - Définition : variable contenant une liste de cycles éventuels (eux-mêmes des listes) détectés lors du parcours en profondeur
  - Initialisation : self.cycles = []
- self.Couleur[s] :
  - Définition : contient la Couleur du sommet s dans le parcours du graphe
  - Initialisation : la Couleur de chaque sommet est initialisé à BLANC
- self.parcourus:
  - Définition : contient une liste ordonnée des sommets parcourus durant le parcours
  - Initialisation : self.parcourus = [] cette liste est initialement vide
- self.temps :
  - Définition : contient le temps/date qui passe lors du parcours
  - Initialisation : self.temps = 0 au début des temps, de sorte que self.temps = 1 lorsque le parcours se situe sur le premier sommet
- self.debut[s] :
  - Définition : contient la date de début de traitement pour le sommet s durant le parcours
  - Initialisation : Chaque sommet s contient la valeur self.debut[s] = 0 initialement
- self.fin[s] :
  - Définition : contient la date de fin de traitement pour le sommet s durant le parcours
  - Initialisation : Chaque sommet s contient la valeur self.fin[s] = 0 initialement

Algorithme Récursif en Pseudo-Code⚓︎

Créer une méthode profondeur_recursif(depart:int)->None qui réalise un parcours en profondeur récursif du graphe, en partant d'un sommet de depart.

ALGORITHME RÉCURSIF, EN PSEUDO-CODE, DE PARCOURS EN PROFONDEUR D'UN GRAPHE

initialiser le graphe avec la méthode initialise_parcours()
procédure profondeur_recursif(depart):
  Marquer le sommet u en GRIS
  Ajouter 1 à la variable temps
  le debut de traitement du sommet u vaut temps
  Pour tout voisin v de u :
    Si la couleur de v est BLANC:
      u est le Père de v
      Marquer le sommet u comme parcouru
      profondeur_recursif(v)
  La couleur de u est NOIR
  ajouter 1 à la variable temps
  la fin de traitement du sommet u est temps
  # A la fin de cette procédure, la variable d'instance 'parcourus'
  # contient la liste des sommets parcourus en profondeur, dans le bon ordre

Connexité Forte⚓︎

Créer une méthode est_fortement_connexe() qui renvoie:
- True si le graphe est fortement connexe :
  (Rappel) Définition : Un graphe est fortement connexe \(\Leftrightarrow \) s'il existe un chemin orienté depuis n'importe quel sommet u vers n'importe quel sommet v
- False sinon
Créer une méthode composante_fortement_connexe(s:int)->list qui renvoie la composante fortement connexe contenant s :
- càd la liste de tous les sommets v atteignables (en profondeur récursivement) à partir du sommet de départ s, et réciproquement tels que s soit aussi atteignable à partir de v
- càd la liste de tous les sommets v pour lesquels il existe un chemin orienté de s à v : s -> s1 -> s2 -> ... -> v,
  et réciproquement tels que il existe aussi un chemin orienté de v à s : v -> v1 -> v2 -> ... -> s
Créer une méthode meme_composante_forte(s:int, v:int)->bool qui :
- reçoit en entrée deux sommets s et v entiers
- renvoie en sortie :
  - True si s et v sont dans la même composante connexe
  - False sinon
Créer une méthode premier_sommet_non_parcouru(listeSommetsParcourus:list)->int qui :
- reçoit en argument d'entrée une listeSommetsParcourus liste de sommets déjà parcourus
- renvoie en sortie :
  - le premier sommet du graphe non encore parcouru, c'est-à-dire n'appartenant pas à la variable listeSommetsParcourus
  - None s'il n'en y en a pas
Créer une méthode composantes_fortement_connexes()->list qui renvoie la liste de toutes les composantes connexes du graphe : [composante_forte_1, composante_forte_2, ..., composante_forte_k] où composante_forte_x désigne la liste de tous les sommets parcourus en profondeur dans la composante_forte_x (avec un départ depuis n'importe quel sommet de composante_forte_x)
Créer une méthode arc_dans_composante_forte(s:int, v:int, depart=0)->bool qui :
- reçoit en entrée trois sommets s, v et depart
- renvoie en sortie :
  - True si l'arc s -> v existe dans la composante connexe forte contenant depart
  - False sinon
Créer une méthode toDotComposanteForte(self, filename="testArbreCouvrant.dot", depart=0)->None, directement inspiré de la fonction toDot() que nous avons créée pour générer le fichier .dot pour un graphe, qui génère le fichier .dot (par défaut filename="testComposanteConnexe.dot") tel que la couleur soit :
- ROUGE pour les sommets et les arcs de la composante connexe forte contenant depart
- NOIR sinon : pour les sommets et les arcs du graphe N'appartienant PAS à la composante connexe forte contenant depart
Créer une méthode showComposanteForte(self, depart=0, name="testComposanteConnexeForte"), très inspirée de la méthode show() pour les graphes, qui trace :
- en ROUGE les sommets et les arcs de la Composante Connexe Forte contenant le sommet de depart, lors du Parcours en Profondeur qui commence en depart.
- en NOIR, toute autre sommet ou arc du graphe N'appartenant PAS à la Composante Connexe Forte précédente

Pères et Arbre Couvrant⚓︎

Créer une méthode arc_dans_arbre_couvrant(s:int, v:int, depart:int)->bool qui reçoit en entrée 2 paramètres s et v pour définir l'arc s -> v et qui renvoie en sortie, si OUI ou NON, l'arc s -> v appartient à l'arbre couvrant obtenu en parcourant en profondeur la composante connexe qui contient le, et à partir du, sommet depart : Autrement dit, la méthode arc_dans_arbre_couvrant() renvoie :
- True si l'arc s -> v appartient à l'ensemble des arcs suivants : self.Pere[u] -> u pour u variant dans la liste self.parcourus qui a été renseignée lors du Parcours en Profondeur en partant du sommet depart
- False sinon
Créer une méthode toDotArbreCouvrant(self, depart=0, filename="testArbreCouvrant.dot")->None, directement inspiré de la fonction toDot() que nous avons créée pour générer le fichier .dot pour un graphe, qui génère le fichier .dot (par défaut filename="testArbreCouvrant.dot") tel que la couleur soit :
- ROUGE pour les sommets et les arêtes de l'arbre couvrant
- NOIR sinon : pour les sommets et les arêtes du graphe N'appartenant PAS à l'Arbre Couvrant
Créer une méthode showArbreCouvrant(depart:int), très inspirée de la méthode show() pour les graphes, qui trace :
- en ROUGE les sommets et les arcs d'un Arbre Couvrant de la Composante Connexe contenant le sommet de depart lors du Parcours en Profondeur qui commence en depart.
- en NOIR, toute autre arc du graphe n'appartenant PAS à l'Arbre Couvrant précédent

Pères et Chemins Orientés⚓︎

Créer une méthode chemin_depuis_racine_vers(self, s:int)->list qui :
- reçoit en entrée un sommet s
- renvoie en sortie un chemin orienté (une liste) de l'arbre couvrant depuis la racine du parcours en Profondeur courant vers le sommet s, Remarque : On supposera que les variables du parcours (en particulier self.Pere) sont déjà renseignées lors de l'appel de cette méthode
Créer une méthode get_plus_proche_sommet_commun(self, s:int, v:int)->int qui :
- reçoit en entrée deux sommets s et v
- renvoie en sortie le sommet le plus proche de s - ou de v - (au sens du nombre d'arêtes) qui est un même aïeul commun à s et à v de l'arbre couvrant, sur les deux chemins orientés (menant vers s, et v) de l'arbre couvrant partant depuis la racine/le depart du parcours en Profondeur courant.
  Remarque : On supposera que les variables du parcours (en particulier self.Pere) sont déjà renseignées lors de l'appel de cette méthode
Créer une méthode chemin_depuis_commun_vers(self, s:int, sommet_commun=0)->list: qui :
- reçoit en entrée deux sommets s et sommet_commun (0 par défaut)
- renvoie en sortie le sous-chemin orienté (une liste) de l'arbre couvrant depuis un sommet_commun vers le sommet s pour le parcours en Profondeur courant : ce sous-chemin de l'arbre couvrant est extrait du chemin orienté de l'arbre couvrant depuis la racine/le depart vers le sommet s et passant par le sommet_commun (privé de sa première partie de depart à sommet_commun)
  Remarque : On supposera que les variables du parcours (en particulier self.Pere) sont déjà renseignées lors de l'appel de cette méthode
Créer une méthode chemin_entre(self, s:int, v:int)->list qui :
- reçoit en entrée deux sommets s et v
- renvoie en sortie un chemin orienté entre s et v de l'arbre couvrant sous forme de liste
  Remarque : ATTENTION, cette méthode ne doit pas perturber le parcours en profondeur courant lors de l'entrée dans la méthode (ou bien doit le redéfinir en sortant)

Cycles⚓︎

Modifier la méthode profondeur_recursif(depart:int)->None de sorte que la variable self.admet_cycle renvoie:
- True s'il existe un cycle dans la composante connexe du sommet depart
- False sinon
Modifier la méthode profondeur_recursif(depart:int)->None de sorte que la variable self.cycles :
- contienne une liste des cycles (sous forme de listes) rencontrés lors du parcours en profondeur, depuis depart, s'il existe un cycle dans la composante connexe du sommet depart
- [] sinon
Créer une méthode cycles_composante_forte(s:int) qui renvoie :
- une liste des cycles rencontrés lors du parcours en profondeur, si le graphe contient un cycle inclus dans la composante connexe contenant le sommet s
- None sinon

Une Application du Parcours en Profondeur: Générer des Labyrinthes Orientés⚓︎

On considère un labyrinthe défini comme une grille de cellules. Chaque cellule possède un mur droit et un mur bas, et chaque mur peut être ouvert, ce qui revient à dire qu’il y a un passage, ou pas de mur, ou fermé.
Le passage entre deux cellules adjacentes est possible :

horizontalement si la cellule de gauche à un mur droit ouvert
verticalement si la cellule du haut à un mur bas ouvert.

Le labyrinthe est encadré de murs (pas de passage vers le haut sur la première ligne…). Le labyrinthe est créé avec tous les murs "fermés" (aucun passage entre les cellules), puis une méthode generation() permet d’ouvrir des murs afin qu’il existe toujours un chemin entre deux cellules du labyrinthe.
L’algorithme utilisé est décrit ici : https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe :

class Cellule:
  def __init__(self):
  self.mur_bas = True # True signifie que le mur est fermé
  self.mur_droit = True # False signifie que le mur est ouvert

class Labyrinthe:
  def __init__(self, largeur, hauteur):
    self.hauteur = hauteur
    self.largeur = largeur
    self.grille = [[Cellule() for j in range(largeur)] for i in range(hauteur)]
    self.generation()
 def solution(self, depart_ligne, depart_colonne, arrivee_ligne, arrivee_colonne):
    """
    Renvoie la liste de directions à suivre pour se rendre de la cellule
    (depart_ligne, depart_colonne) à la cellule (arrivee_ligne, arrivee_colonne).
    Exemple de retour : ['n', 'e', 'e', 's', 'o']
    """

Travail à faire
Écrire la méthode solution(self, depart_ligne, depart_colonne, arrivee_ligne, arrivee_colonne) renvoyant un chemin permettant de se rendre d’une cellule de départ à une cellule d’arrivée.
Vous testerez votre code dans le fichier labyrinthe.py.