## TP n°15 - Graphes - Parcours en largeur (BFS)

CGRAS  = '\033[1m'
CEND   = '\x1b[0m'
CGREEN = "\x1b[36m"
CRED   = "\x1b[35m"

from collections import deque


## Initialisation des graphes représentés par des dictionnaires

G1 = {
 's0':['s1', 's3'],
 's1':['s0', 's2', 's4'],
 's3':['s0', 's4', 's6', 's7'],
 's4':['s1', 's2', 's3', 's5'],
 's5':['s2', 's4', 's7'],
 's6':['s3'],
}

O1 = ['s1', 's0', 's2', 's4', 's3', 's5', 's6', 's7', 's8']    # Ordre : parcours en largeur
P1 = {'s0': 's1', 's1': None, 's2': 's1', 's3': 's0', 's4': 's1', 's5': 's2', 's6': 's3', 's7': 's3', 's8': 's7'}
C1 = ['s1', 's0', 's3', 's7', 's8']

G2 = dict()
G2['a'] = ['b','c']
G2['b'] = ['a','d','e']
G2['c'] = ['a','d']
G2['d'] = ['b','c','e']
G2['e'] = ['b','d','f','g']


O2 = ["b","a","d","e","c","f","g","h"]
P2 = {'a': 'b', 'b': None, 'c': 'a', 'd': 'b', 'e': 'b', 'f': 'e', 'g': 'e', 'h': 'g'}
C2 = ['c', 'd', 'e', 'g', 'h']

## Question 1 : la fonction BFS pour repr. par des dictionnaires

def BFS(G, depart):
    statut = {}       # Initialisation
    attente = deque()

                        # Sortie de la file pour traitement des voisins

                        # Parcours des voisins v du sommet s

                        # Voisins traités, on peut passer au sommet
    print("Sommet traité :", s) # en tête de file

## Question 1 : Test de BFS sur G1
"""
print(CGRAS+CRED+"|||            |||"+CEND)
print(CGRAS+CRED+"||| Question 1 |||"+CEND)
print(CGRAS+CRED+"|||            |||"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)
print(CRED+"Test du parcours en largeur (BFS) avec le graphe G1 :"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)

for s in G1:
    print(s,":",G1[s])

BFS(G1,"s1")
print(CRED+"Réponse attentue ci-dessous!"+CEND)

for n in O1:
    print("Sommet traité : s"+str(n))

## Question 1 : Test de BFS sur G2

print(CGRAS+CGREEN+"-"*70+CEND)
print(CRED+"Test du parcours en largeur (BFS) avec le graphe G2 :"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)
for s in G2:
    print(s,":",G2[s])

BFS(G2,"b")
print(CRED+"Réponse attentue ci-dessous!"+CEND)

for n in O2:
    print("Sommet traité : "+str(n))
"""

## Question 2 : la fonction BFS version 2 : ordre de parcours des sommets, pere

def BFS(G, depart):
    statut = {s:0 for s in G}       # Initialisation
    attente = deque()

    ordre = []                     # Va contenir, dans l'ordre, les sommets visités
    pere = {s:None for s in G}

    return ordre, pere        # renvoie la listes des sommets visités et le dictionnaire
                                    # des pères.

## Tests Question 2 sur les grpahes G1 et G2

## Exemple de G1
"""
print(CGRAS+CRED+"|||            |||"+CEND)
print(CGRAS+CRED+"||| Question 2 |||"+CEND)
print(CGRAS+CRED+"|||            |||"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)
print(CRED+"Test du parcours en largeur (BFS) avec ordre des visites et pères :"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)
print("Pour le graphe G1:")
ordre1, pere1 = BFS(G1,"s1")
assert (ordre1==O1 and pere1==P1),"Une erreur sur ordre1 et/ou pere1"

print(CGRAS+"Ordre des sommets visités dans BFS"+CEND)
print(ordre1,"\n")
print(CGRAS+"dictionnaire des pere dans BFS"+CEND)
for s in G1:
    print(s,":",pere1[s])

## Exemple de G2

print(CGRAS+CGREEN+"-"*70+CEND)
print("Pour le graphe G2:")
ordre2, pere2 = BFS(G2,"b")
assert ordre2==O2 and pere2==P2, "Une erreur sur ordre2 et/ou pere2"

print(CGRAS+"Ordre des sommets visités dans BFS"+CEND)
print(ordre2,"\n")
print(CGRAS+"dictionnaire des pere dans BFS"+CEND)
for s in G2:
    print(s,":",pere2[s])
"""
## Question 3 : UN plus court chemin par BFS complet

def plusCC(G, depart, arrivee):
    ordre, pere = BFS(G, depart)
    if pere[arrivee] == None:  # Sommet arrivee non atteignable depuis le sommet depart
        return []
    else:               # Le sommet arrivee étant atteignable, on construit un chemin
                        # en remontant les pères jusqu’au sommet depart


        return chemin[::-1]     # On inverse la liste pour aller de depart à arrivee

## Tests question 3 : UN plus court chemin par BFS complet
"""
print(CGRAS+CRED+"|||            |||"+CEND)
print(CGRAS+CRED+"||| Question 3 |||"+CEND)
print(CGRAS+CRED+"|||            |||"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)
print(CRED+"Test du plus court chemin par BFS complet :"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)
print("Pour le graphe G1, depart = s1 / arrivee= s8")
chemin = plusCC(G1,"s1","s8")
assert chemin==C1,"votre chemin : "+str(chemin)+" n'est pas le bon, "
print(CGREEN+CGRAS+"Bravo, vous avez le chemin le plus court :"+CEND,C1)
print("Il faut parcourir"+CRED+f" {len(C1)-1} arêtes "+CEND+" pour aller de s1 à s8")
print(chemin)
print(CGRAS+CGREEN+"-"*70+CEND)
print("Pour le graphe G2, depart = a / arrivee= h")
chemin = plusCC(G2,"c","h")
assert chemin==C2,"votre chemin : "+str(chemin)+" n'est pas le bon, "
print(CGREEN+CGRAS+"Bravo, vous avez le chemin le plus court :"+CEND,C1)
print("Il faut parcourir"+CRED+f" {len(C2)-1} arêtes "+CEND+" pour aller de b à h")
print(chemin)
"""
## Question 4 : test de connexité
"""
L'idée est d'utiliser les informations recueillies sur le parcours et notamment la liste des
sommets découverts. Si cette liste a autant d'éléments que le nombre de sommets du graphe, alors le graphe est connexe et réciproquement ...
"""

def connexite(G):
    depart = 0
    ordre  = []

    return len(ordre)==len(G)  #Tous les sommets ont été visités


"""
print(CGRAS+CRED+"|||            |||"+CEND)
print(CGRAS+CRED+"||| Question 4 |||"+CEND)
print(CGRAS+CRED+"|||            |||"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)
print(CRED+"Test deconnexité par BFS :"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)

print("Etude du graphe G1 :")
connexe = connexite(G1)
assert connexe==True,"Vous voyez bien que le graphe 1 est connexe."
print(CGREEN+CGRAS+"Bravo, le graphe G1 est bien connexe !"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)
print("Etude du graphe G1 :")
connexe = connexite(G2)
assert connexe==True,"Vous voyez bien que le graphe 2 est connexe."
print(CGREEN+CGRAS+"Bravo, le graphe G2 est bien connexe !"+CEND)
print(CGRAS+CGREEN+"-"*70+CEND)

"""