<jupyter_start><jupyter_text>Ce notebook nécessite de disposer du logiciel [graphviz](https://graphviz.org/download/) ainsi que du module graphviz pour python (`pip install graphviz`).  Installation de graphviz sous Windows (méthode 1)- On se rendra sur la page dédiée : [Downloads](https://graphviz.org/download/) de Graphviz.	- Normalement le lien pour l'installeur de la version stable (parfois rompu lors des MAJ des dépôts) vous conduit sur cette page :	- (https://www2.graphviz.org/Packages/stable/windows/). Il faudra ensuite suivre les liens pour parvenir à 	- (https://www2.graphviz.org/Packages/stable/windows/10/cmake/Release/)- Lors de l'installation du logiciel, demandez bien à actualiser le PATH Windows.- Une fois le logiciel installé, il vous faut installer le module permettant à Python de communiquer avec le logiciel Graphviz :	- `pip install graphviz`	 Installation de graphviz sous Windows (méthode 2)- Si ce qui est indiqué sur la page [Downloads](https://graphviz.org/download/) de Graphviz conduit au dépôt Github (cela arrive parfois lorsque Graphviz effectue une MAJ sur ses serveus de dépôt) on préférera l'installeur .msi de la version 2.38 qui est toujours disponible ici :  **[installeur MSI pour Windows](https://graphviz.gitlab.io/_pages/Download/Download_windows.html)** - Une fois l'installation du logiciel effectuée, on ajoutera alors graphviz au Path Windows (pour que python puisse le trouver) manuellement car la 2.38 ne le propose pas lors de l'installation :	- Paramètres > Propriétés Système > Variables d'environnement > Variables système > Path > Modifier > Nouveau 		- copier le chemin vers l'installation de graphviz (sans doute "C:\Program Files (x86)\Graphviz2.38\bin")	- Il suffira ensuite d'installer le module permettant à Python de communiquer avec le logiciel Graphviz :	- `pip install graphviz`<jupyter_code>from random import random
from xile import Pile, File
from generateurs import maillage, soleil, etoiles_reliees
from vizu_graphe import VizuGraphe #nécessite graphviz (pip install graphviz)<jupyter_output><empty_output><jupyter_text>Parcours de graphes & Plus courts chemins et Détections de cycles Les détails techniques sont donnés ci-dessous dans le code. On retiendra que si l'algorithme de parcours récursif et l'algorithme de parcours itératif 1 s'adaptent facilement pour détecter les cycles, il n'en est pas de même pour le parcours itératif 2. En résumé, et avec les précautions d'implémentation disséminées dans ce notebook :```              largeur     profondeur    cycles       plus court chemin recursif        N             O          O                 N iteratif 1      O             O          O (L/P)           N iteratif 2      O             O          N                O (L)```**Remarque 1:**Ici il s'agit de recherche de cycles sur des graphes **non-orientés**.**Remarque 2:**La recherche de cycles sur un graphe orienté ne peut pas se baser sur le parcours en profondeur ou en largeur. Il faut utiliser d'autres algorithmes (par exemple ici : http://perso.ens-lyon.fr/eric.thierry/Graphes2007/adrien-panhaleux.pdf)<jupyter_code>##############################
# explorer = "explorer les successeurs" 
# visiter = "faire ce qu'il y a à faire avec le sommet" (ici relever la date de visite)
# marquer = "empecher le sommet d'être ultérieurement rajouté à la xile"
# ici on marque et visite en même temps


#########################  algorithme récursif ############################
# Pour le récursif, la variante où l'on teste si le sommet 
# est marqué en début de fonction (avant #*) et pas avant l'appel de fonction #**
# est contraignante pour la découverte de cycle 
#
# En effet pour les cycles, en cas de successeur déjà marqué en #** , on a besoin de savoir s'il 
# s'agit d'un faux-cycle "A -> B -> A". On utilisera donc (pour les détections de cycles) 
# une fonction dfs modifiée comme suit : dfs(sommet, predecesseur)
#
# En mettant le test au niveau de #**, on aura accès pour le test à 
# la fois à prédécesseur et successeur --> facile de tester "A -> B -> A"
#
# Dans le cas de la variante avec le test en #*, on n'aurait pas accès à prédécesseur et successeur
# et cela imposerait d'utiliser la visite pour stocker le prédécesseur du prédécesseur ce qui serait
# possible mais moins élégant


def parcours_recursif(graphe, depart):
    '''
    - graphe liste ou matrice d'adjacence
    - depart : sommet de depart
   
    La visite consiste à noter la date de visite du sommet.
    On renvoie un dictionnaire {sommet : date_de_visite for sommet in graphe}
    '''
    
    dates = { 'en_cours':0, 'historique':dict() }    
    def visiter(sommet):
        dates['historique'][sommet] = dates['en_cours']
        dates['en_cours'] = dates['en_cours'] + 1
        
    def dfs(sommet):
        dejavu[sommet] = True                       #*
        visiter(sommet)
        for successeur in graphe[sommet]:
            if successeur not in dejavu.keys():     #**
                dfs(successeur)
    
    dejavu = dict()
    dfs(depart)
    return dates['historique']


####################### algorithmes itératifs ############################
# Il y a deux versions.
# 1 :
#    - un sommet vient d'être découvert depuis un(des) prédecesseur(s)
#    - si pas marqué, on enxile (éventuellement plusieurs fois, depuis des prédecesseurs différents)
#    - plus tard on déxile, 
#    - on marque/visite (si non déjà marqué auparavant)
#    - on explore ses successeurs
#
# 2 :
#    - un sommet vient d'être découvert depuis un prédecesseur
#    - si pas marqué on marque/visite
#    - si pas marqué, on enxile (une seule fois donc)
#    - plus tard on déxile
#    - on explore les successeurs
#
# Dans le 2 un sommet ne peut être mis q'une fois dans la xile 
# car il est marqué avant d'y être introduit.
#
# Dans 1 ce n'est plus vrai : un sommet peut être mis plusieurs fois dans la xile
# Cela se produit si :
# - un premier prédecesseur a mis S dans la pile
# - le parcours a continué sans dépiler S
# - un second prédécesseur a remis S dans la pile
# - (puisque S n'a pas été dépilé, on ne peut pas être dans le cas du demi-tour)
#
# 1 et 2 donnent les mêmes dates de visite en largeur
# mais pour le parcours en profondeur 2 ratisse plus large, c'est
# à dire moins profond.

def parcours_1(graphe, depart, larg_ou_prof): 
    '''
    - graphe liste ou matrice d'adjacence
    - depart : sommet de depart
    - larg_ou_prof : 'prof' : en profondeur, 'larg' en largeur.
    
    La visite consiste à noter la date de visite du sommet
    On renvoie un dictionnaire {sommet : date_de_visite for sommet in graphe}  
    '''
    
    dates = { 'en_cours':0, 'historique':dict() }
    def visiter(sommet):
        dates['historique'][sommet] = dates['en_cours']
        dates['en_cours'] = dates['en_cours'] + 1
                                    
    a_explorer = Pile() if larg_ou_prof == 'prof' else File()
    a_explorer.ajouter(depart)    #<sss
    deja_vu = dict()
    while not a_explorer.est_vide():
        sommet = a_explorer.extraire()
        if sommet not in deja_vu.keys(): #<---------- # n'est pas en trop même si on a le if plus
            deja_vu[sommet] = True                    # bas en effet un sommet peut être enxilé
            visiter(sommet)                           # plusieurs fois avant déxilage
            for successeur in graphe[sommet]:         
                if successeur not in deja_vu.keys():  #<-------- # nécessaire si on veut étendre 
                    a_explorer.ajouter(successeur)               # à la recherche de cycle               
    
    return dates['historique']

def parcours_2(graphe, depart, larg_ou_prof):
    '''
    - graphe liste ou matrice d'adjacence
    - depart : sommet de depart
   
    La visite consiste à noter la date de visite du sommet.
    On renvoie un dictionnaire {sommet : date_de_visite for sommet in graphe}
    '''
    
    dates = { 'en_cours':0, 'historique':dict() }
    def visiter(sommet):
        dates['historique'][sommet] = dates['en_cours']
        dates['en_cours'] = dates['en_cours'] + 1
        
    a_explorer = Pile() if larg_ou_prof == 'prof' else File()
    deja_vu = dict()
    deja_vu[depart] = True       #<sss
    visiter(depart)              #<sss
    a_explorer.ajouter(depart)
    while not a_explorer.est_vide():
        sommet = a_explorer.extraire()
        for successeur in graphe[sommet]:       
            if successeur not in deja_vu.keys():
                deja_vu[successeur] = True
                visiter(successeur)
                a_explorer.ajouter(successeur)

    return dates['historique']<jupyter_output><empty_output><jupyter_text>Une fois qu'on a les dates de visite du parcours en profondeur, on peut facilement rajouter ces informations sur le graphe représenté grâce à l'attribut `etiquettes_secondaires`.    On peut ensuite "convertir" ce dictionnaire des dates de parcours en dictionnaire de couleurs `(H, S, V)` avec `H, S` et `V` de type `float` entre 0 et 1. Et demander à représenter le graphe avec ces couleurs.<jupyter_code>from vizu_graphe import VizuGraphe

ma_liste_adjacence = maillage(11, 11, 0.65)

dates = parcours_1(ma_liste_adjacence, 'CC', 'larg')

date_max = max(dates.values())
dates_en_couleur = dict()
for key, val in dates.items():
    dates_en_couleur[key] = (val/date_max, 0.6, 1) 

mon_vizualisateur = VizuGraphe('liste', ma_liste_adjacence, 
                                        etiquettes_secondaires = dates,
                                        couleurs = dates_en_couleur)<jupyter_output><empty_output><jupyter_text>Pour un graphe en étoile :<jupyter_code>ma_liste_adjacence = etoiles_reliees('M')

dates = parcours_1(ma_liste_adjacence, 0, 'larg')

date_max = max(dates.values())
dates_en_couleur = dict()
for key, val in dates.items():
    dates_en_couleur[key] = (val/date_max, 0.6, 1) 

mon_vizualisateur = VizuGraphe('liste', ma_liste_adjacence, 
                                        etiquettes_secondaires = dates,
                                        couleurs = dates_en_couleur,
                                        moteur = 'circo')<jupyter_output><empty_output><jupyter_text>Pour un graphe en soleil :<jupyter_code>ma_liste_adjacence = soleil(10, 5)

dates = parcours_1(ma_liste_adjacence, 0, 'prof')

date_max = max(dates.values())
dates_en_couleur = dict()
for key, val in dates.items():
    dates_en_couleur[key] = (val/date_max, 0.6, 1) 

mon_vizualisateur = VizuGraphe('liste', ma_liste_adjacence, 
                                        etiquettes_secondaires = dates,
                                        couleurs = dates_en_couleur)<jupyter_output><empty_output><jupyter_text>Applications  Plus courts chemins On se base sur le parcours en largeur. Il va s'agir de modifier la visite pour passer d'une date calculée comme suit :- date du dernier sommet visité + 1  à un calcul comme suit :- date du prédécesseur lors du parcours + 1Il faut avoir compris que l'avant-dernier sommet visité n'est en général pas le prédécesseur (pendant le parcours) du dernier sommet en cours de visite (à cause de la xile qui fait tampon).  Pour cela, un bref regard sur les algorithmes nous montre que le parcours 2 est plus adapté que le 1 puisque lors de l'appel au marquage/visite on a accès à la fois au sommet et à son prédécesseur : en passant les deux à la fonction visite, on doit pouvoir s'en sortir en modifiant à la marge le dictionnaire `dates` que l'on renommera en `distances` pour l'occasion.A contrario, le parcours 1 ne permet pas cet accès lors de la visite puisque dans l'algorithme, encore une fois, ce qui est écrit comme `successeur` en fin de boucle n'est PAS le `sommet` en début de tour de boucle suivant (toujours à cause du rôle tampon de la xile).<jupyter_code>def parcours_2_bis(graphe, depart, larg_ou_prof):
    '''
    - graphe liste ou matrice d'adjacence
    - depart : sommet de depart
   
    La visite consiste à noter la distance depuis le départ.
    On renvoie un dictionnaire {sommet : distance depuis le départ for sommet in graphe}
    '''
    
    distances = dict()
    def visiter(successeur, sommet):                       #<sss
        distances[successeur] = distances[sommet] + 1
        
    a_explorer = Pile() if larg_ou_prof == 'prof' else File()
    deja_vu = dict()
    deja_vu[depart] = True
    distances[depart] = 0                    #<sss
    a_explorer.ajouter(depart)
    while not a_explorer.est_vide():
        sommet = a_explorer.extraire()
        for successeur in graphe[sommet]:       
            if successeur not in deja_vu.keys():
                deja_vu[successeur] = True
                visiter(successeur, sommet)    #<sss
                a_explorer.ajouter(successeur)

    return distances
ma_liste_adjacence = maillage(11, 11, 0.55)    #mettre 'CC' par exemple en départ
#ma_liste_adjacence = soleil(10, 5)            #mettre 0 par exemple en départ
#ma_liste_adjacence = etoiles_reliees('M')     #mettre 0 par exemple en départ

distances = parcours_2_bis(ma_liste_adjacence, 'CC', 'larg')

distance_max = max(distances.values())
distances_en_couleur = dict()
for key, val in distances.items():
    distances_en_couleur[key] = (val/distance_max, 0.6, 1) 

mon_vizualisateur = VizuGraphe('liste', ma_liste_adjacence, 
                                        etiquettes_secondaires = distances,
                                        couleurs = distances_en_couleur)<jupyter_output><empty_output><jupyter_text>Plus court chemin d'un sommet au départ En modifiant très légèrement le code ci-dessus on va pouvoir s'en sortir. Lors de la visite, on peut directement stocker le prédécesseur à la place de la distance. Ainsi, en "remontant" les prédécesseurs, on pourra reconstituer le chemin qui a abouti à un sommet donné depuis le départ.On a donc deux modifications à opérer :- modifier légèrement le code de la visite pour qu'elle donne le dictionnaire des prédécesseurs- ajouter une fonction de post-traitement capable de reconstituer un chemin `depart --x--x--x--x--> sommet` à partir du dictionnaire des paires `sommet:predecesseur` (ou `successeur:sommet` selon le point de vue) obtenus lors du parcours.**Attention :** la clef est bien le successeur qui a un unique prédécesseur lors du parcours (alors que l'unicté est perdue dans l'autre sens).**Question :** si sommet est mutable (plateau de jeu), a-t-on des effets de bord ?<jupyter_code>def parcours_2_ter(graphe, depart, larg_ou_prof):
    '''
    - graphe liste ou matrice d'adjacence
    - depart : sommet de depart
   
    La visite consiste à noter le prédécesseur du sommet dans le parcours en largeur.
    On renvoie un dictionnaire {sommet : predecesseur for sommet in graphe}
    '''
    
    parents = dict()
    def visiter(successeur, sommet):      #<sss
        parents[successeur] = sommet
        
    a_explorer = Pile() if larg_ou_prof == 'prof' else File()
    deja_vu = dict()
    deja_vu[depart] = True
    parents[depart] = None                  #<sss
    a_explorer.ajouter(depart)
    while not a_explorer.est_vide():
        sommet = a_explorer.extraire()
        for successeur in graphe[sommet]:       
            if successeur not in deja_vu.keys():
                deja_vu[successeur] = True
                visiter(successeur, sommet)    #<sss
                a_explorer.ajouter(successeur)

    return parents



# on donne le chemin sous forme d'un dictionnaire avec les distances
# depuis le départ pour pouvoir l'afficher ensuite 
# on pourrait faire plus léger mais c'est l'occasion d'utiliser une pile
def donner_chemin(depart, sommet, parents):
    if sommet not in parents.keys():
        return dict()
    chemin_inverse = Pile()
    chemin_inverse.ajouter(sommet)
    longueur = 0
    while parents[sommet] != None:
        sommet = parents[sommet]
        chemin_inverse.ajouter(sommet)
        longueur = longueur + 1
    
    longueur_chemin = longueur
    chemin = dict()
    while longueur>=0:
        sommet = chemin_inverse.extraire()
        chemin[sommet] = longueur_chemin - longueur
        longueur = longueur - 1
    
    return chemin
ma_liste_adjacence = maillage(11, 11, 0.55)    #mettre 'CC' par exemple en départ
#ma_liste_adjacence = soleil(10, 5)           #mettre 0 par exemple en départ
#ma_liste_adjacence = etoiles_reliees('M')    #mettre 0 par exemple en départ

parents = parcours_2_ter(ma_liste_adjacence, 'CC', 'larg')
chemin = donner_chemin('CC', 'JJ', parents)

chemin_en_couleur = dict()
for key in chemin.keys():
    chemin_en_couleur[key] = (0.7, 0.3, 1) 

mon_vizualisateur = VizuGraphe('liste', ma_liste_adjacence, 
                                        etiquettes_secondaires = chemin,
                                        couleurs = chemin_en_couleur)<jupyter_output><empty_output><jupyter_text>Découverte de cycles (uniquement pour les graphes non orientés - limité à une composante connexe)L'idée fondamentale est que, si l'on si prend bien (c'est à dire en réussissant à écarter *simplement* le cas du cycle "A --> B --> A"), le fait d'explorer un sommet déjà marqué signifie que l'on a réussi à accéder à un sommet depuis deux chemins différents qui partent du départ. On a donc nécessairement un cycle.Si on regarde en détail ce qui suit, on s'aperçoit que contrairement au cas des plus courts chemins, cette fois-ci ce sont les algorithmes récursifs et itératifs n°1 qui sont les plus adaptés (alors que l'itératif n°2 demanderait des adaptations peu élégantes).<jupyter_code>#############################################################################
##   Recherche de cycles en récursif 
#############################################################################

def parcours_recursif_bis(graphe, depart):
    '''
    - graphe liste ou matrice d'adjacence
    - depart : sommet de depart
   
    La visite consiste à noter la date de visite du sommet.
    On renvoie :
       - un booléen indiquant si le graphe possède un cycle
       - un dictionnaire {sommet : date_de_visite for sommet in {sommets parcourus}}
    '''    
    
    dates = { 'en_cours':0, 'historique':dict() }    
    def visiter(sommet):
        dates['historique'][sommet] = dates['en_cours']
        dates['en_cours'] = dates['en_cours'] + 1
        
    def dfs(sommet, predecesseur):
        dejavu[sommet] = True
        visiter(sommet)                          
        for successeur in graphe[sommet]:
            if successeur in dejavu.keys() :
                if predecesseur != successeur:   #<sss # pas un demi-tour --> on a un cycle
                    return True
            else:
                 if dfs(successeur, sommet):     #<sss # cycle plus haut dans pile d'appels 
                    return True                        # --> on sort
        return False                              
    
    dejavu = dict()
    
    return dfs(depart, None), dates['historique']                               


##############################################################################
##   recherche de cycle sur parcours 1
##############################################################################
#
# Le cas du cycle "sommetA --> sommetB --> sommetA" - possible en récursif - 
# est ici exclu puisque si un successeur (B) est mis dans la xile, son parent (A) 
# dans le parcours est déjà marqué donc ne pourra pas être empilé en tant 
# que successeur de successeur de lui même.
#
#------------------------------------
# renvoie True => il existe un cycle
#------------------------------------
# On renvoie True si un sommet sort de la pile et a déjà été marqué
# Cela se produit si on arrive à la situation où un sommet est
# passé deux fois dans la xile.
# 
# Cela n'est possible que si la xile contient *à un instant donné* deux fois
# le même sommet. En effet, une fois déxilé/marqué une première fois un sommet ne peut 
# plus être réintroduit dans la xile (d'où l'importance du if en bas d'algo).
# C'est donc que le second exemplaire a été réintroduit dans la xile AVANT 
# la sortie du premier exemplaire
#
# Cette situation se produit uniquement si :
#  - un premier prédecesseur a mis S dans la xile
#  - le parcours a continué sans déxiler S 
#  - un second prédécesseur a remis S dans la xile
#  - (puisque S n'a pas été déxilé, on ne peut pas être dans le cas du demi-tour)
# Donc uniquement si S a au moins deux prédécesseurs différents
# ce qui signifie qu'on a un cycle (car on est dans le cas d'un graphe non orienté)
#
# Remarque : sans le if additionnel, on pourrait visiter un sommet S, visiter un de ses successeurs 
# et revisiter S (cas du cycle "A -> B -> A") => entrainerait une détection de cycle erronée
#--------------------------------------
# Il existe un cycle => renvoie True
#--------------------------------------
# Puisque tous les sommets du cycle finiront par être visités 
# (sauf si la fonction renvoie True avant)
# notons Sb le dernier sommet du  cycle à être marqué.
# *Juste avant* de sortir de la xile pour être marqué, les deux sommets adjacents à Sb 
# (notons les Sa et Sc) dans le cycle ont déjà été marqués 
# (puisque Sb est par définition le dernier à l'être).
# Ces deux sommets Sa et Sc ont donc chacun envoyé un exemplaire de Sb dans la xile
# Juste avant de sortir de la xile pour être marqué, Sb se trouve donc en double 
# exemplaire dans la xile
# ---> renvoie True

def parcours_1_bis(graphe, depart, larg_ou_prof): 
    '''
    - graphe liste ou matrice d'adjacence
    - depart : sommet de depart
   
    La visite consiste à noter la date de visite du sommet.
    On renvoie :
       - un booléen indiquant si le graphe possède un cycle
       - un dictionnaire {sommet : date_de_visite for sommet in {sommets parcourus}}
    '''    
    dates = { 'en_cours':0, 'historique':dict() }
    def visiter(sommet):
        dates['historique'][sommet] = dates['en_cours']
        dates['en_cours'] = dates['en_cours'] + 1
    
    a_explorer = Pile() if larg_ou_prof == 'prof' else File()
    a_explorer.ajouter(depart)     
    deja_vu = dict()
    
    while not a_explorer.est_vide():
        sommet = a_explorer.extraire()
        if sommet not in deja_vu.keys(): 
            deja_vu[sommet] = True                    
            visiter(sommet)                           
            for successeur in graphe[sommet]:         
                if successeur not in deja_vu.keys():  
                    a_explorer.ajouter(successeur)
        else:
            return True, dates['historique']        #<sss
    return False, dates['historique']               #<sss

################################
# On regardera avec profit ce qui se passe sur le parcours 1 dans cette configuration
# pour pouvoir comparer avec la méthode 2 (qui elle sera mise en défaut)
# 
#          *--*--*
#         /
# >>--*--x
#         \
#          O--*--*
#
# si on parcourt de la gauche vers la droite
# d'abord vers le haut, quand on arrivera
# sur O il n'y aura pas de détection de cycle "x -> O -> x"
                                           
                                    
######################################################################
##  recherche de cycle sur parcours 2 : Ne fonctionne pas
##  sauf à implémenter une visite avec mémorisation du prédécesseur
######################################################################
#
# La xile casse le lien prédecesseur --> suivant
# Lien de filiation dont on peut avoir besoin pour détecter les cycle "A -> B -> A"
# Alors qu'en récursif il est facile d'avoir ce lien puisque c'est le lien
# appelant ---> appelé
# Donc en récursif, détection de cycle "sommetA --> sommetB --> sommetA"
# facilement écartée.
#
# La détection du cycle "A -> B -> A" est également exclue en méthode 1 puisque 
# si un successeur (B) est mis dans la xile, son parent (A) dans le parcours 
# est déjà marqué donc ne pourra pas être enxilé par (B).
# (Si (A) est une seconde fois dans la xile, c'est en tant que successeur d'un
# sommet (C). C'est donc qu'il y a un cycle).
   
def parcours_2_quattro(graphe, depart, larg_ou_prof):
    
    def visiter(sommet):
        pass
        
    a_explorer = Pile() if larg_ou_prof == 'prof' else File()
    deja_vu = dict()
    deja_vu[depart] = True       #<sss
    visiter(depart)              #<sss
    a_explorer.ajouter(depart)
    while not a_explorer.est_vide():
        sommet = a_explorer.extraire()
        for successeur in graphe[sommet]:       
            if successeur not in deja_vu.keys():
                deja_vu[successeur] = True
                visiter(successeur)
                a_explorer.ajouter(successeur)
            else: #<-----------------<####
                return True              #
    return False                         #
                                         #
                                         #
##########################################                         
# Comment savoir qu'on est pas dans le cas du cycle "A -> B -> A" ?
# garder en mémoire le dernier sommet visité n'est pas 
# suffisant puisqu'on fait parfois des sauts en arrière
# où le dernier sommet visité n'est pas le prédécesseur
# (dans le parcours) du sommet sur lequel on est
#          *--*--D
#         /
# >>--*--x
#         \
#          O--*--*
# sur cet exemple, si on parcourt de la gauche vers la droite
# d'abord vers le haut, que se passera-t-il quand on arrivera
# sur O ? Comment éviter de détecter le cycle "x -> O -> x" ?
# Alors que quand on arrive sur O, c'est D qui a été visité en dernier (pas x) ?
# Cette difficulté doit nous pousser à privilégier le parcours 1
# pour la recherche de cycle.
from vizu_graphe import VizuGraphe

ma_liste_adjacence = maillage(3, 3, 0.45)
existe_cycle, cycle = parcours_1_bis(ma_liste_adjacence, 'BC', 'larg')

print(existe_cycle)

mon_vizualisateur = VizuGraphe('liste', ma_liste_adjacence, etiquettes_secondaires = cycle)

from vizu_graphe import VizuGraphe

ma_liste_adjacence = maillage(5, 5, 0.45)
existe_cycle, cycle = parcours_recursif_bis(ma_liste_adjacence, 'BC')

cycle_en_couleur = dict()
for key in cycle.keys():
    cycle_en_couleur[key] = (0.8, 0.6, 1) 

print(existe_cycle)

mon_vizualisateur = VizuGraphe('liste', ma_liste_adjacence, etiquettes_secondaires = cycle,
                                                            couleurs = cycle_en_couleur)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11028797203859889, 'fraction_numerical': 0.0055086999468125526, 'mean_word_length': 2.749181028343541, 'pattern_counts': {'":': 0, '<': 52, '<?xml version=': 0, '>': 76, 'https://': 6, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 29, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '383717', 'license': 'Unlicense', 'n_tokens_mistral': 8744, 'n_tokens_neox': 8574, 'n_words': 2892, 'path': 'VizuGraphe/Algos_Graphes_en_NSI/algos_graphes_en_nsi.ipynb', 'repo_name': 'jidv/outils_graphiques', 'size': '26322'}