### TP5

## 1) Dictionnaire d'adjacence

g_pkmn = {
    "Feu": ["Plante"],
    "Plante":  ["Eau", "Sol"],
    "Eau": ["Feu", "Sol"],
    "Sol": ["Feu"]
}

aretes_pkmn = [
    ("Feu", "Plante"),
    ("Plante", "Eau"),
    ("Plante", "Sol"),
    ("Eau", "Feu"),
    ("Eau", "Sol"),
    ("Sol", "Feu")
]

def construire_adj(sommets, aretes, oriente):
    """
    Entrée:
    - sommets: liste
    - aretes: liste de couples de sommets
    - oriente: booléen
    Sortie: Dictionnaire d'adjacence du graphe de sommets `sommets`,
    d'arêtes  `aretes`, orienté ou non selon la valeur de `oriente`
    """
    D = {}
    for s in sommets:
        D[s] = []

    for (x, y) in aretes:
        if y not in D[x]:
            D[x].append(y)
        if not oriente and x not in D[y]:
            D[y].append(x)
    return D

def liste_voisins(g, u):
    return g[u][:]

def est_arete(g, u, v):
    return v in g[u]

def degre_moyen(g):
    n = 0
    somme_degres = 0
    for u in g.keys():
        n += 1
        somme_degres += len(g[u])
    return somme_degres/n

sommets = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"]
aretes = [
    ("A", "B"),
    ("A", "C"),
    ("B", "D"),
    ("C", "E"),
    ("C", "B"),
    ("D", "C"),
    ("D", "E"),
    ("E", "A"),
    ("F", "G"),
    ("H", "I"),
    ("I", "J"),
    ("J", "H"),
]

g_o = construire_adj(sommets, aretes, True)  # graphe orienté
g_n = construire_adj(sommets, aretes, False) # graphe non-orienté

## 2) Parcours de graphe

def afficher_sommets_source(g, s):
    """
    Affiche les sommets de g accessibles depuis s, dans l'ordre
    d'un parcours en profondeur. Renvoie l'ensemble des sommets
    visités.
    """
    P = [] #pile
    vu = set()
    P.append(s)
    vu.add(s)

    while len(P) > 0:
        u = P.pop()
        print(u)
        for v in liste_voisins(g, u):
            if v not in vu:
                vu.add(v)
                P.append(v)
    return vu


def afficher_sommets(g):
    """
    Affiche les sommets de g dans l'ordre d'un parcours en profondeur
    """
    vu = set()
    for u in g:
        if u not in vu:
            nouveau_vu = afficher_sommets_source(g, u)
            vu.update(nouveau_vu)


def composantes_connexe(g):
    """
    Renvoie la liste des composantes connexes de g
    """
    vu = set()
    CC = [] #liste des composantes connexes
    for u in g:
        if u not in vu:
            nouveau_vu = afficher_sommets_source(g, u)
            vu.update(nouveau_vu)
            CC.append(nouveau_vu)
    return CC

## 3) Labyrinthes


def lire_labyrinthe(filename):
    """
    Entrée: filename nom de fichier contenant un labyrinthe bien formatté
    Sortie: triplet (lab, e, s) avec
    - lab grille de booléens représentant les cases occupées du labyrinthe
    - e coordonnées de la case d'entrée
    - s coordonnées de la case de sortie
    """
    f = open(filename, "r")
    lignes = f.readlines()
    f.close()

    n = len(lignes) # nb lignes
    m = len(lignes[0]) - 1 # nb colonnes

    # initialisation du labyrinthe
    lab = []
    for i in range(n):
        lab.append([False for j in range(m)])

    # remplissage case par case, et recherche de E et S
    for i in range(n):
        for j in range(m):
            if lignes[i][j] == 'E':
                e = (i, j)
            if lignes[i][j] == 'S':
                s = (i, j)
            if lignes[i][j] == 'X':
                lab[i][j] = True

    return (lab, e, s)

def graphe_labyrinthe(lab):
    """
    Renvoie le graphe correspondant à la grille de booléen lab. Les sommets
    sont les cases libres (contenant des False), et une arête relie deux cases
    libres si elles sont adjacentes dans la grille
    """
    n = len(lab)
    m = len(lab[0])
    sommets = []
    aretes = []

    for i in range(n):
        for j in range(m):
            if not lab[i][j]:
                sommets.append((i, j))
                # ajouter les voisins
                liste_voisins = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
                for (ii, jj) in liste_voisins:
                    # ne garder que les voisins valides
                    if 0 <= ii and ii < n and 0 <= jj and jj < m:
                        if lab[ii][jj] == False:
                            aretes.append(((i, j), (ii, jj)))

    return construire_adj(sommets, aretes, False)


from collections import deque


def predecesseurs(g, u0):
    """
    Renvoie le tableau des prédecesseurs correspondant à l'arborescence
    du parcours en largeur de g à partir de u0
    """

    p = deque() # file pour stocker les sommets
    pred = dict() # pred[x] est le sommet avant x dans un plus court
                  # chemin entre u0 et x

    p.append(u0)
    pred[u0] = None

    while len(p)>0:
        u = p.popleft()
        for v in g[u]:
            if v not in pred:
                p.append(v)
                pred[v] = u
    return pred

def reconstruire_chemin(s, u, p):
    if u not in p:
        # pas de chemin de s à u
        return None
    # construire le chemin à l'envers, en remontant l'arbre vers la source
    chemin = []
    while p[u] is not None:
        chemin.append(u)
        u = p[u]
    chemin.append(u)
    # renverser le chemin et le renvoyer
    chemin_bon_sens = []
    l = len(chemin)
    for i in range(l):
        chemin_bon_sens.append(chemin[l-1-i])
    return chemin_bon_sens


"""
la fonction de test suppose que les fichiers de l'archive ont été mis
dans le même dossier que le code. Vous pouvez vérifier que les cases
affichées par la fonction forment bien un chemin vers la sortie (tracé
en rouge dans labyrinthe_petit_solved.png dans l'archive)
"""
def test_labyrinthe():
    # lecture du labyrinthe et construction du graphe
    lab, e, s = lire_labyrinthe("41x37.txt")
    g = graphe_labyrinthe(lab)
    # calcul du plus court chemin de e à s
    pred = predecesseurs(g, e)
    chemin = reconstruire_chemin(e, s, pred)
    print(f"Chemin de {e} à {s}")
    for (i, j) in chemin:
        print(i, j)