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

Ce TD implémente le Parcours en Largeur Orienté, ou BFS Orienté - Breadth First Search :uk:, en version ITÉRATIF, avec une File : on réutilisera la classe Graphe 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/après 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'arcs, 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 orientés 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é 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 largeur le graphe à partir du sommet depart :
Autrement dit, la méthode arc_dans_arbre_couvrant() renvoie :
- True si l'arc s -> v (ou v -> s) 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 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 arcs de l'arbre couvrant
- NOIR sinon : pour les sommets et les arcs 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 largeur qui commence en depart.
- en NOIR, toute autre sommet ou 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 Largeur 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 Largeur 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 Largeur 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 Largeur courant lors de l'entrée dans la méthode (ou bien doit le redéfinir en sortant)
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 (pas forcément dans l'arbre couvrant). (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 existe un cycle dans la composante connexe du sommet depart
- [] sinon
Créer une méthode cycles_composante(s:int) qui renvoie :
- une liste des cycles rencontrés lors du parcours en Largeur, 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.