# -*- coding: utf-8 -*-
"""
Created on Mon Jul 10 20:25:58 2017

@author: domps
"""

# Ce code, inspiré par l'algorithme présenté
# dans le livre de Fournier, fonctionne.
# On peut critiquer l'utilisation de la méthode
# remove sur les listes qui remplace un travail
# que l'on pourrait faire à la main en O(N).
# On peut aussi critiquer l'utilisation du test << in >>.
# Il serait meilleur de tenir à jour un tableau de booléens
# indiquant si chaque noeud a été traité ou non.


# Attention : le graphe est suppposé connexe, sinon plantage.
# Pour l'éviter, il faudrait définir les noeuds à distance infinie.


# Révise les étiquettes à partir
# d'un sommet actif t_0.
# L est la liste d'ajacencedu graphe,
# S_barre la liste des sommets pas encore élucidés
# et pere la liste des peres.
def revision(t_0, L, etiquette, S_barre, pere) :
    ''' Révise la liste des étiquettes et celle des peres à partir d'un sommet
    actif t_0 en modifiant les listes passées en paramètes.
    L est la liste d'ajacencedu graphe, S_barre la liste des sommets
    pas encore élucidés et pere la liste des peres. '''
    info_voisins = L[t_0]
    for a in info_voisins :
        noeud = a[0]
        if noeud in S_barre :
            l_essai = etiquette[t_0] + a[1]
            if l_essai < etiquette[noeud] :
                etiquette[noeud] = l_essai
                pere[noeud] = t_0
                
def choix_sommet_etiquette_minimale(etiquette, S_barre) :
    ''' Renvoi, parmi les sommes de la liste S_barre, l'indice de celui qui 
    possède l'étiquette minimale. '''
    i_min = -1 # valeur bidon
    etiq_min = float('inf')
    for i in S_barre :
        if etiquette[i] < etiq_min :
            etiq_min = etiquette[i]
            i_min = i
    return i_min
            
            
def Dijkstra(L, x_0) :
    n = len(L)
    #print('n',n)
    S_barre = [i for i in range(n)]
    etiquette = [float('inf') for i in range(n)]
    pere = ['*' for i in range(n)]

    etiquette[x_0] = 0
    S_barre.remove(x_0)
    
    #print('S_barre', S_barre)
    #print('Etiquette', etiquette)
    
    t_0 = x_0
    while len(S_barre) > 0 :
        #print('t_0',t_0)
        revision(t_0, L, etiquette, S_barre, pere)
        #print('S_barre', S_barre)
        #print('etiquette', etiquette)
        t_0 = choix_sommet_etiquette_minimale(etiquette, S_barre)
        #print('nouveau t_0',t_0)        
        S_barre.remove(t_0)
    return etiquette, pere
  

# construit le chemin à suivre connaissant
# le tableau des peres 
def construit_chemin(pere, depart, arrivee) :
    chemin = [arrivee]
    j = arrivee
    while j != depart :
        k = pere[j]
        chemin = [k] + chemin
        j = k
    return chemin
    
# version récursive    
def construit_chemin_rec(pere, depart, arrivee) :
    if depart == arrivee :
        return  [depart]
    else :
        precedent = pere[arrivee]
        return construit_chemin_rec(pere, depart, precedent) + [arrivee] # Utiliser append ici 
        # ne marcherait pas car append est une méthode agissant sur une liste, cela ne renvoie rien !!
    
    

#######################################################
#
#   EXEMPLES 
#
#######################################################

# Pour des exemples
# Listes d'adjacence de divers graphes

# Exemples 3 page 54 livre Gondran
# indices partant de zéro pour Python
# J'ai ajouté une arrêt de  1 vers 0 sinon 0 est innateignable
# et l'algo se plante si on l'appique en partant d'un autre noeud
# que 0. Je n'ai pas prévu le cas de graphes non connexes où
# certaines paires de noeuds ne sont pas liée par un chemin.
L_3 = [[(1,7), (2,1)], [(0, 7), (3,4), (5,1)], [(1,5), (4,2), (5,7)],
       [], [(1,2), (3,5)],[(4,3)]]

# Ex 4 page 55 livre Gondran
L_4 = [[(1,3),(2,10)], [(0,3),(2,6),(3,2),(4,7),(5,4)],
        [(0,10),(1,6),(5,3)], [(1,2),(4,1)], [(1,7),(3,1),(5,2)],
       [(1,4),(2,3),(4,2)]]
        
# TD de Laurent Schwald
L_TD = [[(1,2),(2,4),(3,1)],[(3,1),(5,2)],[(3,1),(4,3)],
          [(2,1),(5,2),(6,2)],[(0,2),(6,1),(8,3)],[],[(4,2),(9,2)],
           [(3,2),(5,1),(6,2),(9,2)],[(6,1),(9,2)],[(6,1)]]

# Ex du hors-série du magazine Tangente  page 92 (cd image numérisée )
# A B C D E F G H I J  K  L  M  N  P  Q  R  S 
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 

L_tan = [[(2,3),(13,3),(11,4),(12,3)], # A 0
         [(7,5),(8,3),(9,3),(17,3)],   # B 1
         [(3,2),(12,2)],               # C 2
         [(0,3),(2,3),(4,2)],          # D 3
         [(0,5),(3,4),(5,3),(13,2)],   # E 4
         [(4,4),(6,1),(15,1)],         # F 5
         [(5,4),(7,1)],                # G 6
         [(6,5),(1,3),(8,2), (15,5)],   # H 7
         [(1,2),(7,5),(9,3)],          # I 8
         [(8,5),(10,3),(17,6)],        # J 9
         [(9,5),(11,3),(17,3)],        # K 10
         [(10,7),(12,2),(16,4)],       # L 11
         [(2,2),(0,3),(11,5)],         # M 12
         [(14,18),(16,6)],             # N 13
         [(13,4),(4,3),(1,3)],         # P 14
         [(14,5),(5,2),(6,2),(1,7)],   # Q 15
         [(0,3),(14,6),(10,3)],        # R 16
         [(14,5),(16,5)]]              # S 17



  
dist, pere = Dijkstra(L_3, 0)  
chem = construit_chemin(pere, 0, 4)

dist_tan, pere_tan = Dijkstra(L_tan, 17)
chem = construit_chemin(pere_tan, 17, 1) # Du noeud A au noeud B

# Recherche pour tous les noeuds d'un graphe
n = len(L_tan)
for i in range(n) :
    print(Dijkstra(L_tan, i))