### Question 1) 

# Le principe est le suivant : à partir d'un sommet, explorer en premier lieu les chaînes de sommets injectives et de longueur maximale, pour éventuellement revenir en arrière et recommencer. A chaque pas, on marque le sommet explorer pour ne plus jamais le revisiter.

### Implémentation de la fonction DFS


def Enleve(L,M) :
    """ retourn L privé de M """
    return [x for x in L if not(x in M)]
    
def DFS_Recursif(Sommets,Aretes,S_d,S_a) :
    """ fait une recherche en Depth First Search en récursif """
    if S_d==S_a :
        return [S_d]
    else :
        Aretes_Dep=[A for A in Aretes if A[0]==S_d]
        # liste des aretes partant de S_d
        if Aretes_Dep !=[] :
            Sommets_Temp=Enleve(Sommets,[S_d])
            Aretes_Temp=Enleve(Aretes,Aretes_Dep)
            for A in Aretes_Dep :
                Resultat=DFS_Recursif(Sommets_Temp,Aretes_Temp,A[1],S_a)
                if Resultat :
                    return [S_d]+Resultat
                    break
        # si on atteint cette ligne, c'est que l'on a trouvé  aucun chemin possible de S_d vers S_a
            return False
        # à cette ligne, il n'y a aucune arête partant de S_d
        return False 
            
### Question 2)


def Mat_Adj_Graphe(M) :
    return [list(range(len(M[:,0]))),[[i,j] for i in range(len(M[:,0])) for j in range(len(M[:,0])) if M[i,j]>0]]
    
### Question 3) 

import numpy

M=zeros((10,10))

for k in [0,1,2,3,5,6,7] :
    M[k,k+1]=1
M[0,5]=1
M[5,4]=1
M[9,3]=1
M[7,9]=1
M[9,7]=1
M[4,8]=1

# print("Matrice d'adjacence :")
# print(M)

print("Test de l'algorithme DFS ")

Graphe=Mat_Adj_Graphe(M)
Sommets,Aretes,S_d,S_a=Graphe[0],Graphe[1],0,7

# print(DFS_Recursif(Sommets,Aretes,S_d,S_a))

#### Algorithme de DIJKSTRA ####


def Somme_Coeff(M) :
    """ fonction calculant la somme des coefficients d'une matriced'adjacence """
    ### cette fonction s'utilisera pour initialiser les coûts avant les mises à jour ###
    return sum([sum(M[:,k]) for k in range(len(M[0,:]))])

# print(Somme_Coeff(M)) # ok !!


def Dijkstra(M,dep,arr) :
    somme=Somme_Coeff(M)
    M_Temp=M.copy()
    S,A,L=[dep],[],[x for x in range(len(M[:,0])) if x != dep]
    # S = sommets marqués
    # A = arêtes marquées
    # L = sommets non encore marqués
    Test_Mise_A_Jour=True
    # pour tester si on n'a pas d'impasse 
    while S[-1] != arr and Test_Mise_A_Jour :
        Test_Mise_A_Jour=False
        cout_Temp=somme 
        #initialisation du coût à la somme des coûts
        arete_Temp=[]
        for i in S :
            for j in L :
                if M[i,j]>0 and M_Temp[i,i]+M_Temp[i,j]<=cout_Temp :
                    ### problème de mise à jour des coeff de M_Temp
                    # on teste une arête [i,j] avec j non marqué
                    Test_Mise_A_Jour=True
                    arete_Temp=[i,j]
                    cout_Temp=M_Temp[i,i]+M_Temp[i,j]
        # en sortie ici, on a une arête optimale en coût si Test_Mise_A_Jour est vrai
        
        
        
        if Test_Mise_A_Jour :
            S.append(arete_Temp[1])
            Test=False
        
            for index in range(len(A))  :
                if not(Test) :
                    # si on n'a pas encore encore greffé l'arête sur un chemin
                    chemin_Temp=A[index]
                    for l in range(len(chemin_Temp)) :
                        if chemin_Temp[l]==arete_Temp[0] :
                            A.append(chemin_Temp[:l+1]+[arete_Temp[1]])
                            Test=True
                            break
                            # une seule greffe de l'arête
            if not(Test) :
                # l'arête trouvée  n'est pas greffable sur un chemin existant
                A.append(arete_Temp)
            L.remove(S[-1])
            M_Temp[arete_Temp[1],arete_Temp[1]]=cout_Temp
            # mise à jour de l'arête
            
        
    if  dep==arr :
        # départ = arrivée : on sort de la boucle immédiatement
        return [[dep],0]
    elif S[-1]==arr :
        # on trouve une connexion possible
        chemin_optimal=[c for c in A if c[-1]==arr][0] 
        cout_total=M_Temp[arr,arr]
        return [chemin_optimal,cout_total]        
    else :
        # on ne trouve pas de connexion possible
        return "pas de chemin possible"
        
        
## Essai ##

A=zeros((11,11))
A[0,1]=1
A[0,4]=2
A[0,5]=3
A[1,2]=4
A[1,3]=3
A[2,8]=15
A[3,10]=17
A[4,6]=7
A[4,10]=14
A[5,6]=8
A[5,7]=2
A[6,8]=1
A[7,9]=2
A[8,10]=2
A[9,6]=3

# print("Matrice d'adjacence pour Dijkstra")
# print(A)
# Resultat=Dijkstra(A,0,10)
# print("Chemin minimal par Dijkstra :")
# if type(Resultat)==str :# si Resultat est une chaîne de caractères
#     print(Resultat)
# else :
#     print(Resultat[0])
#     print("dont le coût est égal à :",Resultat[1])