# -*- coding: utf-8 -*-
"""
Created on Tue Nov 26 09:30:14 2024

@author: arnau
"""

import numpy as np
from random import choice
import matplotlib.pyplot as plt

#%% Structure de dictionnaire, exemple
Pattes = {"Chat" : 4 , "Poule" : 2 , "Boa" : 0}
Pattes["Lapin"]=4
for k in Pattes.keys(): print("un",k,"possède", Pattes[k], "patte(s)")

#%% Représentation d'un graphe par liste d'adjacence/dictionnaire
# Exercice 1

L1=[[2],[0,1],[0,3],[0,1,3]]

G1 = {0: [2], 1:[0,1], 2 :[0,3],3 :[0,1,3]}

#%% Exercice 2

G2={0: [1,2], 1 :[0,1,3], 2:[2], 3:[0,1]}

G3=[[2],[1,2,3],[],[0,1]]

#%% Exercice 3
def G(d,n):
    '''
    Entrée : deux entiers non nuls avec d qui divise n
    Sortie : matrice d'adjacence du graphe G à n sommets
             0 à n-1 avec une arête entre i et j ssi d divise j-i et j !=i

    '''
    M = np.zeros([n,n])
    for i in range(n):
        for j in range(i):
            if (i-j)%d==0:
                M[i,j]=1 
                M[j,i]=1
    return M

#%% Parcours en largeur
def Parcours(G,x):
    '''
    Entrée : graphe non orienté G sous forme matrice d'adjacence
    Sortie : liste des sommets accessibles depuis x

    '''
    n = np.shape(G)[0]
    L = [x]
    i = 0
    while i<len(L):
        for j in range(n):
            if G[L[i],j]==1 and not(j in L):
                L.append(j)
        i = i+1
    return L

M = np.array([[0,1,0,0,0,0],[1,0,1,0,0,0],[0,1,0,0,0,0],[0,0,0,0,1,0],[0,0,0,1,0,0],[0,0,0,0,0,1]])
#%% Marche aléatoire sur un graphe

def trajet(G,x,n):
    '''
    Entrée : un graphe G, un sommet x et un entier naturel n
    Sortie : simule une trajectoire aléatoire de longueur n sur G partant de x
    '''
    trajectoire = [x]
    for k in range(n):
        trajectoire.append(choice(G[trajectoire[-1]]))
    return trajectoire

# Dictionnaire représentant le graphe du comportement de Bidule
hamsterG={ 0 : [0,1,2], 1 : [0,2], 2 : [0,1]}

def premierDodo():
    '''
    Renvoie le temps du premier passage à l'état 0 ("dormir")
    '''
    n=0
    trajet = [1]
    while trajet[-1] != 0:
        trajet.append(choice(hamsterG[trajet[-1]]))
        n = n+1
    return n

# Calcul d'une valeur approchée du temps moyen avant le premier dodo
s = 0
for _ in range(100000) : 
    s+=premierDodo()/100000
print("le temps moyen avant le premier dodo est:",s)

# Loi stationnaire : 3/7, 2/7 , 2/7

def frequence(n):
    '''
    Entrée : entier naturel n
    Sortie : proportion de chaque activité après la simulation d'une trajectoire de longueur n
    '''
    L = trajet(hamsterG,1,n)
    freq =[0,0,0]
    for l in L:
        freq[l]+=1/n
    return freq



#%% Alogrithme de Dijkstra

Inf = np.inf

def Dijkstra(G,s):
    n = np.shape(G)[0]
    L = G[s, :]  
    Ltemp = [[j,L[j]] for j in range(n)]# initialisation liste des longueurs initialisées
    SommetsVisités = [s]
    u = s
    Ltemp.pop(s)
    while len(SommetsVisités) <n:
        print(SommetsVisités)
        k =np.argmin([Ltemp[i][1] for i in range(len(Ltemp))])
        u = Ltemp[k][0]
        SommetsVisités.append(u)
        for j in range(n):
            if L[u]+G[u,j]<L[j]:
                L[j]=L[u]+G[u,j]
        Ltemp.pop(k)
    return L


def Loic(G,s):
    d =[]
    for i in range(len(G)):
        if i == s :
            d.append(0)
        elif i !=  s and G[i][s] == 0:
            d.append(np.inf)
        else:
            d.append(G[i][s])
    L = [s]
    for j in range(len(d)-1):
        u = 0
        for k in range(len(d)):
            if not(k in L):
                if d[k]<d[u]:
                    u = k
        L.append(u)
        for i in range(len(d)):
            if d[u]+G[u][i]<d[i] and G[u][i] !=0:
                d[i] = d[u]+G[i][u]
    return d
    

#%%
test = np.array([[0,Inf,3,Inf,Inf,1], [Inf,0,2,3,1,Inf], [3,2,0,Inf,3,1],[Inf,3,Inf,0,1,Inf], [Inf,1,3,1,0,5], [1,Inf,1,Inf,5,0]])
test2 = [[0,0,3,0,0,1], [0,0,2,3,1,0], [3,2,0,0,3,1],[0,3,0,0,1,0], [0,1,3,1,0,5], [1,0,1,0,5,0]]

#%%

from scipy.sparse import csr_array
from scipy.sparse.csgraph import dijkstra


print(dijkstra(csr_array(test2)))