import numpy as np

# Matrice d'adjacence M associée au graphe G

M=np.array([[np.inf,7,np.inf,np.inf,14,np.inf,np.inf,np.inf],
           [np.inf,np.inf,8,np.inf,np.inf,np.inf,np.inf,np.inf],
           [np.inf,np.inf,np.inf,6,np.inf,np.inf,np.inf,np.inf],
           [18,np.inf,np.inf,np.inf,np.inf,11,np.inf,np.inf],
           [np.inf,np.inf,np.inf,np.inf,np.inf,19,np.inf,np.inf],
           [np.inf,np.inf,np.inf,np.inf,np.inf,np.inf,4,13],
           [np.inf,np.inf,5,np.inf,np.inf,np.inf,np.inf,8],
           [np.inf,np.inf,9,np.inf,np.inf,np.inf,np.inf,np.inf]])

print("M=",M)


# Exercice 1

def RFW(M):
    L=M.copy() # Copie profonde L de la matrice M initiale
    n=len(L)
    for k in range(n): # Pour une étape n°k entre 0 et n-1
        for i in range(n): # on parcourt les lignes de L
            for j in range(n):  # on parcourt un à un les termes de la ligne i de M
            # Si le chemin le plus court passe par le sommet k alors on remplace dans L
                if L[i,k]+L[k,j]<L[i,j]:
                    L[i,j]=L[i,k]+L[k,j]
    return L

print("L=",RFW(M))

#%%

# Exercice 2

n=len(M)
S=-np.ones((n,n)) # matrice qui contient initialement que des -1
for i in range(n):
    for j in range(n):
        if M[i,j]<np.inf: # s'il existe une arête de i vers j
            S[i,j]=j # trajet direct de i vers j

#%%

# Exercice 3

def RFW2(M):
    L=M.copy()
    for k in range(n):           
        for i in range(n):
            for j in range(n):
                if L[i,k]+L[k,j]<L[i,j]:
                    L[i,j]=L[i,k]+L[k,j]
                    S[i,j]=S[i,k] # pour aller de i à j, il faut passer
                    # par le premier arrêt du chemin entre i et k
    return L

L=RFW2(M)
print("L=",L)
print("S=",S)

#%%

# Exercice 4

def Itineraire(dep,arr):   
    chemin=[dep] # On initialise le chemin optimal 
    sommet=dep # On part du départ
    while sommet!=arr: # Tant que l'on n'est pas arrivé
        sommet=int(S[sommet,arr]) # On avance sur le chemin optimal
        chemin.append(sommet) # On rajoute l'étape à la liste chemin
    return chemin # On renvoie le chemin optimal

dep=0
arr=7
print("Le chemin pour aller de",dep,"à",arr,"est",Itineraire(dep, arr),"de longueur",int(L[dep,arr]))

#%%

# Exercice 5

# Question 0

D=np.load('Dico_Metro-Numero.npy',allow_pickle=True).flat[0] # Dictionnaire arrêt de Métro:numéro
#Dinv=np.load('Dico_Numero-Metro.npy',allow_pickle=True).flat[0] # Dictionnaire numéro:arrêt de Métro
M=np.load("Matrice_distances_Metro.npy",allow_pickle=True) # Matrice des distances entre stations voisines de métro


#%%

# Question 1

print("Il y a",len(M),"stations de métro.")

# On trouve 376 stations de métro, soit 376**3 itérations dans la triple boucle
# Avec 13 calculs par itération cela fait 13*376**3 = 691 045 888 opérations.
# Si on estime à 10**7 calculs par seconde cela fait environ 69 secondes pour exécuter la commande RFW(M).

#%%

# Question 2

Dinv = {D[d]:d for d in D}

#%%

# Question 3

import time
tac=time.time()

n=len(M)
S=-np.ones((n,n)) # matrice qui contient initialement que des -1
for i in range(n):
    for j in range(n):
        if M[i,j]<np.inf: # s'il existe une arête de i vers j
            S[i,j]=j # trajet direct de i vers j

L=RFW2(M)

tic=time.time()
duree=tic-tac
print("L'algorithme RFW a pris",duree,"s")

#%%

# Question 3

def Itineraire2(dep,arr):   
    chemin=[dep] # On initialise le chemin optimal 
    dep=D[dep]
    arr=D[arr]
    sommet=dep # On part du départ
    while sommet!=arr: # Tant que l'on n'est pas arrivé
        sommet=int(S[sommet,arr]) # On avance sur le chemin optimal
        chemin.append(Dinv[sommet]) # On rajoute l'étape à la liste chemin
    return chemin # On renvoie le chemin optimal

dep="Anvers"
arr="Vavin"
print("Le chemin pour aller de",dep,"à",arr,"est",Itineraire2(dep,arr))

#%%

# Question 4

print("Il dure",int(L[D[dep],D[arr]]),"s soit environ",int(L[D[dep],D[arr]])//60,"min")

#%%

# Question 5

dep="Vavin"
arr="Anvers"
print("Le chemin pour aller de",dep,"à",arr,"est",Itineraire2(dep,arr))
print("Il dure",int(L[D[dep],D[arr]]),"s soit environ",int(L[D[dep],D[arr]])//60,"min")

print("Test pour savoir si le graphe est orienté :",M==np.transpose(M))

#%%

# Question 6

M=0
for i in range(n):
    for j in range(i):
        if L[i,j]>M:
            M=L[i,j]
            i0=i
            j0=j
            
print("Les deux stations les plus éloignees sont",Dinv[i],"et",Dinv[j],"et dure",M//60,"min")
print("Le chemin est",Itineraire2(Dinv[i],Dinv[j]))