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

@author: dconduche
"""

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

G = [[(1, 10), (4, 5)],
     [(2, 1), (4, 2)],
     [(3, 4)],
     [(2, 6), (0, 7)],
     [(1, 3), (2, 9), (3, 2)]]

# le graphe, sans les poids: vérifions qu'il n'y a pas d'arête oubliée :
L = [[x[0] for x in adj] for adj in G]
print(L)


##Q2
print("QUESTION 2")
s = 0
# Initialisation
n = len(G)
c = ['b'] * n
d = ['inf'] * n
p = [-1] * n
E = []
# Initialisation : s
c[s] = 'g'
E.append(s)
d[s] = 0


##Q3
print("QUESTION 3")


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

# On teste :
relacher(0, 1, 10, d, p)
relacher(0, 4, G[0][1][1], d, p)
print('p:', p)
print('d:', d)
relacher(4, 1, 3, d, p)
print('p:', p)
print('d:', d)


##Q4
print("QUESTION 4")
"""C'est une recherche de minimum :
il suffit d'adapter l'algorithme bien connu de vous.
Bien identifier
 * Ce que l'on doit retourner : un sommet s de E
 * Selon quel critère : d[s] est minimale dans d
C'est donc une recherche d'indice du min à peine modifiée"""


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

E = [1, 4]  # ce n'est plus vrai à cette étape, mais ça permet de tester
print('test :', choix_sommet(d, E))

##Q5
print("QUESTION 5")


def dijkstra(G, s):
    # Initialisation
    n = len(G)
    c = ['b'] * n
    d = ['inf'] * n
    p = [-1] * n
    E = []
    # Initialisation : s
    c[s] = 'g'
    E.append(s)
    d[s] = 0
    while len(E) > 0:
        u = choix_sommet(d, E)  # On laisse choix_sommet choisir le sommet.
        for a, poids in G[u]:   # on parcourt les sommets voisins de u.
            if c[a] == 'b':  # S'il est blanc
                c[a] = 'g'   # on colorie a en gris
                E.append(a)  # et on le rajoute à la « liste des gris »
            if c[a] == 'g':  # S'il est gris (désormais), ou l'était,
                relacher(u, a, poids, d, p)  # père et distance : relacher
        c[u] = 'n'       # on a fini de visiter u (et les arêtes partant de u)
#        print('Nous venons de visiter le sommet', u)
#        print('p:', p)
#        print('d:', d)
    return (p, d)

p, d = dijkstra(G, 0)
print('p:', p)
print('d:', d)
"""Cohérent : c'est la meme liste que la présentation de l'algorithme de
Dijkstra."""


##Q6
print("QUESTION 6")
"""Réfléchissons :
* les sommets blancs sont exactement ceux à distance infinie
* les sommets gris sont ceux qui sont dans E
* les sommets noirs ne sont ni blancs ni gris 
     (il suffit que d[s] != 'inf' et s pas dans E pour qu'il soit noir)
"""

def dijkstra(G, s):
    # Initialisation
    n = len(G)
    d = ['inf'] * n
    p = [-1] * n
    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, poids in G[u]:   # on parcourt les sommets voisins de 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 (p, d)

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

##Q6
print("QUESTION 7")

"""Comme pour un parcours en largeur, chaque sommet entre dans E au plus 
une fois, donc la boucle while effectue, au plus, n=|S| itérations. 

La boucle for est identique, là aussi, au parcours en largeur.

Par contre, on fait appel à choix_sommet, qui parcours E à chaque itération
du while. Et, dans le pire cas, on peut avoir |E|=n-1 après le premier passage:
si le sommet de départ s est voisin de tous les sommets du graphe.
On aura alors |E| = n-k au k-ième passage, donc une complexité en 
(n-1) + (n-2) + ... + 2 + 1 = (n-1)n/2 = O(n^2)

Il faut donc toujours faire bien attention aux boucles cachées dans des
fonctions.

relacher(u, a, poids, d, p) ne contient pas de boucle : complexité en O(1)

Ainsi, dans le pire cas, la complexité est en O(n^2)

Si choix_sommet(d, E) est en O(log|S|), alors la complexité de l'algorithme
est en O(|A|+|S|*log|S|) :
 * boucles for mises bout à bout : |A|+|S|
 * appels à choix_sommet : |S|*log|S|
Comme |S| = o(|S|*log|S|), on trouve O(|A|+|S|*log|S|)"""