TNSI : TD PARCOURS EN LARGEUR - BFS - ITÉRATIF D'UN GRAPHE⚓︎

Ce TD implémente le Parcours en Largeur, ou BFS - Breadth First Search :uk:, en version ITÉRATIF, avec une File : on réutilisera la classe Graphe Non Orienté Non Pondéré.

Initialisation du Parcours en Largeur - BFS⚓︎

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 largeur
  - 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
- INF = nbSommets+1 qui est une variable, servant à représenter une distance infinie. En effet, dans un graphe à n sommets, la longueur maximale d'une chaîne de s à v (avec éventuellement s=v), mais ne passant jamais deux fois par le même sommet au milieu de la chaîne, vaut n. En particulier, n+1 peut donc bien représenter l'infini.
- self.Dist[s]:
  - Définition : LA Distance minimale au sens du nombre d'arêtes, du sommet de depart au sommet s, à la fin du parcours en largeur, de départ depart. C'est donc un nombre entier. LA distance minimale d'un sommet à un autre est unique. > ATTENTION : ce TD NE s'intéresse PAS aux graphes pondérés. La détermination du plus court chemin dans des graphes pondérés (à poids positifs) fera l'objet du TD sur l'Algorithme de Dijkstra.
  - Initialisation : la distance de depart à tout sommet s vaut initialement INF

Remarque : les autres variables, utilisées seulement pour l'initialisation du parcours en profondeur, peuvent être laissées telles quelles sans problème dans l'initialisation, même si elles ne sont pas utilisées dans le parcours en largeur : self.temps, self.debut, self.fin

Algorithme Itératif en Pseudo-Code⚓︎

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

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

procédure largeur_iteratif(depart):
  # initialisations
  voisins est une File()
  voisins.enfile(depart)
  Initialiser le parcours avec la méthode initialise_parcours() précédente
  Ajouter depart aux sommets parcourus
  Marquer le sommet depart comme GRIS
  La Distance à depart vaut  0

  Tant que la File voisins n'est pas vide:
    explore = voisins.tete()
    Pour tout voisin v de explore:
        Si le voisin v n'a jamais été visité (s'il est BLANC)
            Marquer v comme déjà visité (en GRIS)
            Ajouter v aux sommets parcourus
            La Distance à v vaut (Distance à explore) + 1
            Le Pere de v vaut explore
            voisins.enfile(v)
    voisins.defile()
    Marquer explore comme totalement traité (en NOIR)
  # A la fin de cette procédure, la variable d'instance 'parcourus' 
  # contient la liste des sommets parcourus en largeur, 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 largeur 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 largeur dans la composante_x (avec un départ depuis n'importe quel sommet de composante_x)

Pères et Arbre Couvrant⚓︎

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 largeur 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 largeur 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 Largeur 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(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 Largeur
  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(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 Largeur
  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(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 Largeur 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(s:int, v:int)->list qui :
- reçoit en entrée deux sommets s et v
- renvoie en sortie une chaîne de l'arbre couvrant, entre s et v sous forme de liste
  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 plus_court_chemin_entre(s:int, v:int) qui :
- accepte en entrée deux sommets s et v
- et qui renvoie en sortie UN plus court chemin entre s et v. (Il n'y a pas forcément unicité)
  Remarque : On pourra commencer par réaliser un nouveau parcours en largeur depuis le sommet depart = s. Juste avant de sortir de cette méthode, on veillera à revenir à l'ancien parcours en largeur, s'il y en avait un (afin de ne pas créer de conflits entre l'ancien parcours et le parcours courant de cette méthode).

Cycles⚓︎

Modifier la méthode largeur_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 largeur_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 largeur, 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 Largeur: 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.