TNSI : TD PARCOURS EN PROFONDEUR - DFS - ITÉRATIF D'UN GRAPHE⚓︎

Ce TD détaille le Parcours en Profondeur, ou DFS - Depth First Search :uk:, en version ITÉRATIF, avec une Pile : on réutilisera la classe Graphe Non Orienté 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 Itératif en Pseudo-Code⚓︎

Créer une méthode profondeur_iteratif(depart:int)->None qui réalise un parcours en profondeur itératif du graphe, en partant d'un sommet de depart. Ce parcours en profondeur itératif utilise une Pile() nommée voisins

ALGORITHME ITÉRATIF, EN PSEUDO-CODE, DE PARCOURS EN PROFONDEUR D'UN GRAPHE, GRÂCE À UNE PILE

procédure profondeur_iteratif(depart):
  voisins est une Pile()
  voisins.empile(depart)
  initialiser le parcours avec la méthode initialise_parcours() précédente
  Tant que la Pile voisins n'est pas vide:
    explore = voisins.depile()
    si le sommet 'explore' n'a jamais été visité:
      ajouter explore à la liste self.parcourus
      Marquer le sommet explore comme visité avec une couleur NOIR
      Pour tout sommet v voisin de explore:
        si v n'a pas été visité:
          voisins.empile(v)
  # A la fin de cette procédure, la variable d'instance 'self.parcourus' 
  # contient la liste des sommets parcourus en profondeur, dans le bon ordre

Connexité⚓︎

Créer une méthode est_connexe() qui renvoie:
- True si le graphe est connnexe : (Rappel) Définition : un graphe est connexe \(\Leftrightarrow\) il existe une chaîne depuis n'importe quel sommet u vers n'importe quel sommet v \(\Leftrightarrow \) le graphe est en un seul tenant / morceau, càd qu'aucun sommet ou sous-graphe n'est isolé du reste du graphe
- False sinon
Créer une méthode composante_connexe(s:int)->list qui renvoie la composante connexe contenant s :
càd la liste de tous les sommets atteignables (en profondeur itérativement) à partir du sommet de départ s càd la liste de tous les sommets v pour lesquels il existe une chaîne s -- s1 -- s2 -- ... -- v (de s à v)
Créer une méthode meme_composante(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_connexes()->list qui renvoie la liste de toutes les composantes connexes du graphe : [composante_1, composante_2, ..., composante_k] où composante_x désigne la liste de tous les sommets parcourus en profondeur dans la composante_x (avec un départ depuis n'importe quel sommet de composante_x)

Pères et Arbre Couvrant⚓︎

Modifier la méthode profondeur_iteratif(depart:int)->None de sorte que la variable self.Pere soit totalement peuplée à la fin du parcours en profondeur (itératif)
Créer une méthode arete_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'arête s -- v et qui renvoie en sortie, si OUI ou NON, l'arête s -- v appartient à l'arbre couvrant obtenu en parcourant en profondeur le graphe à partir du sommet depart (en fait l'arbre couvrant de la composante connexe contenant depart) :
Autrement dit, la méthode arete_dans_arbre_couvrant() renvoie :
- True si l'arête s -- v (ou v -- s) appartient à l'ensemble des arêtes suivantes : 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 arêtes de l'Arbre Couvrant obtenu lors du Parcours en Profondeur commençant en depart (en fait l'arbre couvrant de la composante connexe contenant depart).
- en NOIR, toute autre sommet ou arête du graphe N'appartenant PAS à l'Arbre Couvrant précédent

Pères et Chaînes⚓︎

Créer une méthode chaine_vers_racine(self, s:int)->list qui :
- reçoit en entrée un sommet s
- renvoie en sortie une chaîne de l'arbre couvrant, qui part du sommet s vers la racine du parcours en Profondeur
  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, sur les deux chaînes (d'origne s, et v) de l'arbre couvrant qui mènent vers la racine du parcours en Profondeur
  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 chaine_vers_racine_jusqua(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 la sous-chaîne (une liste) de la chaîne de l'arbre couvrant, qui part de s vers la racine du parcours en Profondeur mais qui s'arrête au sommet_commun inclus (donc s'arrête à son aïeul sommet_commun, avant d'atteindre la racine du parcours)
  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 chaine_entre(self, s:int, v:int)->list qui :
- reçoit en entrée deux sommets s et v
- renvoie en sortie une chaîne entre s et v sous forme de liste

Cycles⚓︎

Modifier la méthode profondeur_iteratif(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_iteratif(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 en existe)
- [] sinon
Créer une méthode cycles_composante(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⚓︎

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.