# -*- 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=np.array([[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
    while len(SommetsVisités) <n:
        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

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