## TP 2 sur les graphes: Parcours de graphes non pondérés

from collections import deque

## Exo Parenthésage

def bien_parenthesee(chaine):
    #a completer


chaine1 = '(4+7) * ((4-5)* 3)'
chaine2 = '(4 +(7 * ((4-5) * 3))'
print(bien_parenthesee(chaine1))
print(bien_parenthesee(chaine2))


## BFS Implémentation 1 avec un dictionnaire des états

def est_accessible_BFS1(G, source, cible):
    '''G est un graphe, i et c deux sommets (initial et cible). Teste s'il existe un chemin reliant a et b, i.e. si a et b sont dans la même composante connexe du graphe.'''
    #a completer


## Tests
g0 = {
    0 : [2, 7, 8], # voisins de 0
    1 : [8,3 , 7], # voisins de 1
    2 : [0,3,5,6], # voisins de 2
    3 : [1,2,4], # voisins de 3
    4 : [3,5], # voisins de 4
    5 : [2,4], # voisins de 5
    6 : [2], # voisins de 6
    7 : [0, 1], # voisins de 7
    8 : [0, 1] # voisins de 8
}



g1 = {
    0 : [9,2], # voisins de 0
    1 : [9,3], # voisins de 1
    2 : [0,3,5,6], # voisins de 2
    3 : [1,2,4], # voisins de 3
    4 : [3,5], # voisins de 4
    5 : [2,4], # voisins de 5
    6 : [2], # voisins de 6
    7 : [8], # voisins de 7
    8 : [7], # voisins de 8
    9 : [0, 1], # voisins de 9
}

g2 = {0:[4, 1], 1:[2, 5, 6, 0], 2:[6, 3], 3:[2, 7],4:[5], 5:[], 6:[7], 7:[6]}

est_accessible_BFS1(g1, 0, 2)
est_accessible_BFS1(g2, 3, 0)



## BFS Implémentation 2 avec un dictionnaire dejavu

def est_accessible_BFS2(G, source, cible):
    '''G est un graphe, i et c deux sommets (initial et cible). Teste s'il existe un chemin reliant a et b, i.e. si a et b sont dans la même composante connexe du graphe.'''



est_accessible_BFS2(g1, 0, 2)
est_accessible_BFS2(g2, 3, 0)


## DFS implémentation 1

def est_accessible_DFS1(G, source, cible):
    '''G est un graphe, i et c deux sommets (initial et cible). Teste s'il existe un chemin reliant a et b, i.e. si a et b sont dans la même composante connexe du graphe.'''


est_accessible_DFS1(g1, 0, 2)
est_accessible_DFS1(g2, 3, 0)

## Complexité


## Reconstruction des chemins



def chemin(parents, source, cible):
    liste = [] # liste
    if parents is not None:
        # a completer

parents = {0: None, 9: 0, 2: 0, 1: 9, 3: 2, 5: 2, 6: 2}
chemin(parents, 0, 3)


##

def chemin_BFS(G, source, cible):
    '''G est un graphe, i et c deux sommets (initial et cible). Renvoie s'il existe un chemin reliant a et b'''


chemin_BFS(g1, 1 ,6)
chemin_BFS(g2, 0 ,7)

## Distance

def distance(G, source, cible):
    '''G est un graphe, i et c deux sommets (initial et cible). Renvoie s'il existe un chemin reliant a et b'''

distance(g1, 1 ,8)
distance(g2, 0 ,7)