# -*- coding: utf-8 -*-
"""
Created on Wed Feb 15 18:19:48 2023

@author: dconduche
"""

#### Exercice 7
##Q1
print("QUESTION 1")


"""Prenons un graphe"""
G0 = [[1, 4],
     [2, 4],
     [3],
     [2, 0],
     [1, 2, 3]]
"""on rajoute des positions"""
pos = [(0, 0), (1, 1), (6, 2), (6, -2), (-1, -1)]

"""On transforme en le dictionnaire demandé -- on peut modifier Dijkstra
dans un premier temps pour utiliser G0 et pos."""

G = {}
for i in range(len(pos)):
    G[pos[i]] = [pos[j] for j in G0[i]]

print(G)

##Q2a
print("QUESTION 2a")


def dist(a, b):
    return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5


##Q2b
print("QUESTION 2b")
"""relacher est inchangée, et choix_sommet aussi.
Les listes G, d, p sont désormais des dictionnaires.
Mais la syntaxe des dictionnaires est telle qu'il n'y a pas une
virgule à changer !"""


def relacher(u, a, poids, d, p):
    if d[a] == 'inf' or d[a] > d[u] + poids:
        d[a] = d[u] + poids
        p[a] = u


def choix_sommet(d, E):
    s0 = E[0]
    dmin = d[s0]
    for s in E[1:]:
        if dmin > d[s]:
            s0 = s
            dmin = d[s0]
    E.remove(s0)
    return s0


def dijkstra(G, s):
    # Initialisation : désormais, des dictionnaires vide, c'est plus simple !
    d = {s: 'inf' for s in G.keys()}
      # Les clefs sont les sommets, i.e. les clefs de G, valeur 'inf' partout.
      # On peut se débarrasser de 'inf' en modifiant le test
      # « d[s] == 'inf' » en « s not in d »
    p = {}
    E = []
    # Initialisation : s
    E.append(s)
    d[s] = 0
    while len(E) > 0:
        u = choix_sommet(d, E)  # On laisse choix_sommet choisir le sommet.
        for a in G[u]:          # On parcourt les sommets voisins de u.
            poids = dist(a, u)  # Le poids est désormais la distance dist(a,u)
            if d[a] == 'inf':  # S'il est blanc
                E.append(a)  # on le rajoute à la « liste des gris »
            if a in E:  # S'il est gris (désormais), ou l'était,
                relacher(u, a, poids, d, p)  # père et distance : relacher
#        print('Nous venons de visiter le sommet', u)
#        print('p:', p)
#        print('d:', d)
    return (p, d)

p, d = dijkstra(G, (0, 0))
print('p:', p)
print('d:', d)


##Q2c
print("QUESTION 2c")
"""relacher est inchangée, et choix_sommet aussi : on ne les réécrit pas.
seule une ligne change dans Dijkstra : si on est arrivé au sommet cible
(qu'il va devenir noir), on s'arrête --- c'est-à-dire,
on sort de la fonction."""


def dijkstra_cible(G, s, sc):
    # Initialisation : désormais, des dictionnaires vide, c'est plus simple !
    d = {s: 'inf' for s in G.keys()}
    p = {}
    E = []
    # Initialisation : s
    E.append(s)
    d[s] = 0
    while len(E) > 0:
        u = choix_sommet(d, E)  # On laisse choix_sommet choisir le sommet.
        if u == sc:
            return p, d
        for a in G[u]:          # On parcourt les sommets voisins de u.
            poids = dist(a, u)  # Le poids est désormais la distance dist(a,u)
            if d[a] == 'inf':  # S'il est blanc
                E.append(a)  # on le rajoute à la « liste des gris »
            if a in E:  # S'il est gris (désormais), ou l'était,
                relacher(u, a, poids, d, p)  # père et distance : relacher
    return False
"""Si on sort de la boucle while, le sommet sc n'a pas été atteint."""


p, d = dijkstra_cible(G, (0, 0), (-1,-1))
print('p:', p)
print('d:', d)


##Q3
print("QUESTION 3")
"""Aetoile est identique à dijkstra_cible :
seul choix_sommet devient choix_sommet_Ae."""


def choix_sommet_Ae(d, E, sc):
    s0 = E[0]
    dmin = d[s0] + dist(s0, sc)
    for s in E[1:]:
        distance = d[s] + dist(s, sc)
        if dmin > distance:
            s0 = s
            dmin = distance
    E.remove(s0)
    return s0


def Aetoile(G, s, sc):
    # Initialisation : désormais, des dictionnaires vide, c'est plus simple !
    d = {s: 'inf' for s in G.keys()}
    p = {}
    E = []
    # Initialisation : s
    E.append(s)
    d[s] = 0
    while len(E) > 0:
        u = choix_sommet_Ae(d, E, sc)  # seule modification
        if u == sc:
            return p, d
        for a in G[u]:
            poids = dist(a, u)
            if d[a] == 'inf':
                E.append(a)
            if a in E:
                relacher(u, a, poids, d, p)
    return False

p, d = Aetoile(G, (0, 0), (-1, -1))
print('p:', p)
print('d:', d)


##Q4
print("QUESTION 4")
"""S'il y a un obstacle dans la direction du sommet cible.
Cf Wikipedia : 
https://commons.wikimedia.org/wiki/File:Schema_Astar_labyrinthe.png
https://fr.wikipedia.org/wiki/Algorithme_A*
"""