library(ggplot2);
## Warning: package 'ggplot2' was built under R version 3.3.3
create_ligne<-function(nb_sommet){

  
  ligne<-matrix(0,nb_sommet,nb_sommet)
  
  #Premier sommet relié au deuxième
  ligne[1,2]=1
  #Dernier sommet 
  ligne[ nb_sommet, nb_sommet-1 ]=1
  
  for(i in 2:(nb_sommet-1)){
    ligne[i,i-1]=1/2
    ligne[i,i+1]=1/2
  }
  
  return(ligne)

}

create_anneau<-function(nb_sommet){

  anneau<-matrix(0,nb_sommet,nb_sommet)
  
  anneau[1,nb_sommet]=1/2

  anneau[nb_sommet,1]=1/2
  anneau[nb_sommet,nb_sommet-1]=1/2
  
  # %% : modulo
  for(i in 1:(nb_sommet-1)){
    anneau[i,(i-1)]=1/2
    anneau[i,(i+1)]=1/2
  }
  
  return(anneau)

}

create_sucette<-function(nb_sommet){

  sucette<-matrix(0,nb_sommet,nb_sommet)
  
  #base de la sucette : 1/3 des sommets
  milieu<-trunc(nb_sommet/3)
  
  #Premier sommet relié au deuxième
  sucette[1,2]=1
  
  
  for(i in 2:(milieu-1)){
    sucette[i,i-1]=1/2
    sucette[i,i+1]=1/2
  }
  
  #milieu sucette
  sucette[milieu,milieu-1]=1/3
  
  #gauche
  sucette[milieu,milieu+1]=1/3
  
  #droite
  sucette[milieu,nb_sommet]=1/3
  sucette[nb_sommet,milieu]=1/2

  
  #anneau de la sucette
  for(i in (milieu+1):(nb_sommet-1)){
    sucette[i,(i-1)]=1/2
    sucette[i,(i+1)]=1/2
  }
  
  sucette[nb_sommet,nb_sommet-1]=1/2
  
  
  return(sucette)

}

#renvoie la séquence, avec un nombre de pas : nb_pas et dans le graphe : graphe, démarrage dans un sommet aléatoire
marche_aleatoire<-function(graphe,nb_pas){
  taille_graphe=nrow(graphe)
  
  #premier sommet au hasard
  #indice_next_sommet=(taille_graphe+1)*runif(1)
  
  #après un probleme je tente de fixer le premier indice
  indice_next_sommet=5
  
  #vecteur qui contient le chemin
  chemin<-numeric(nb_pas)
  
  for(i in 1:nb_pas){
    
    somme_proba=0
    next_sommet=runif(1)

    #on somme les probas et on choisit le sommet à partir duquel on depasse la valeur aléatoire générée
    for(j in 1:taille_graphe){
      somme_proba=somme_proba+graphe[indice_next_sommet,j];
      if(somme_proba>=next_sommet){
        indice_next_sommet=j
        chemin[i]=j
        
        #on a trouvé le prochain sommet on sort du for
        break
      }
    }
    
  }
 
    return(chemin)
      
}

#on donne la séquence de la marche aléatoire pour calculer les probas de chaque état
proba_sommets <- function(cheminParcouru, size, pas){
 
  #probaEtats<-vector(mode="numeric",length=size)
  #???probaEtats=rep(0,size)
  probaEtats=matrix(0, 1, size)
  for(i in 1:size)
  {
    probaEtats[1,i]=(sum(cheminParcouru==i)/pas)
  }

  return(probaEtats)
}




#calcul dispersion entre les deux matrices
L2 = function(x,y){ 
        sqrt(sum((x-y)**2))
    }


#taken from the DTMCPack
calcul_probas <- function(graphe){
    one <- round(matrix(1, nrow(graphe), ncol(graphe)))
    I <- diag(nrow(graphe))
    d <- rep(1, nrow(graphe))
    t(d) %*% solve(I - graphe + one)
}

test_topos<-function(graphe,nbSommets,nbPasMarche,taillePas,nbIter){

z=5000
k=1
vari=vector(mode="numeric")
temps=vector(mode="numeric")



  start.time_calcul <- Sys.time()
  vraies_probas=calcul_probas(graphe)
  end.time_calcul <- Sys.time()
  time.taken_calcul <- end.time_calcul - start.time_calcul
  
  marche1=marche_aleatoire(graphe,nbPasMarche)
  

while(z<=nbPasMarche){
  
  start.time <- Sys.time()
  marche_simu_time=marche_aleatoire(graphe,z)
  probas_1=proba_sommets(marche1,nbSommets,z)
  end.time <- Sys.time()
  
  time.taken <- end.time - start.time
  
  
  vari[k]=L2(probas_1,vraies_probas)
  temps[k]=time.taken
  
  k=k+1
  z=z+taillePas
}


#temps de calcul par calcul valeur propre

  y=1
  k=1
  vect_ligne<-vector(mode="numeric",length=nbSommets)
  vect_ligne=rep(1/nbSommets,nbSommets)
  #vect_ligne[1]=1
  vari_iter=vector(mode="numeric")
  temps_iter=vector(mode="numeric")
  
 
  
  #obligé de trick le code il y a un probleme avec le premier calcul, a l'entrée du while?
     vect_ligne=as.vector(vect_ligne)%*%graphe

  while(y<=nbIter){
    
    start.time_iter <- Sys.time()
    
    vect_ligne=as.vector(vect_ligne)%*%graphe

    end.time_iter <- Sys.time()   
  
    
    vari_iter[k]=L2(as.vector(vect_ligne),vraies_probas)
    
    if(k==1){
      temps_iter[1]=0
    }
    else{
      temps_iter[k]= temps_iter[k-1]+(end.time_iter - start.time_iter)
    }

    k=k+1
    y=y+1
    
    
  }

     
    
 print(end.time_iter- start.time_iter)

donnees<-data.frame(temps,vari,vari_iter,temps_iter)


ggplot(donnees,aes(y=vari))+geom_line(aes(x=temps),colour="blue") + geom_vline(xintercept=time.taken_calcul, colour="red") + geom_line(aes(y=as.vector(vari_iter),x=temps_iter),colour="black")

#ggplot(donnees,aes(y=vari_iter))+geom_line(aes(x=temps_iter),colour="blue")+geom_vline(xintercept=time.taken_calcul, colour="red")
}

Test de la marche aléatoire. On retient le temps de calcul et la précision à chaque avancée avec N nombre de pas. Ce qui me semble pertinant est d’afficher la variance entre la matrice résultat et le résultat obtenu à un certain temps. On va pouvoir voir avec quel type de calcul la variance converge le plus vite vers 0. On test sur une topologie en ligne de 20 sommets. Malheureusement je n’ai pas pu utiliser ma fonction de test, les temps ne marchant pas pour une raison inconnu. J’ai du copier coller mon code pour que les temps fonctionnent…

test_ligne1<-create_ligne(20)
z=5000
k=1
vari_ligne1=vector(mode="numeric")
temps_ligne1=vector(mode="numeric")




  start.time_calcul <- Sys.time()
  vraies_probas_ligne1=calcul_probas(test_ligne1)
  end.time_calcul <- Sys.time()
  time.taken_calcul_ligne1 <- end.time_calcul - start.time_calcul
  
  marche_ligne1=marche_aleatoire(test_ligne1,400000)


while(z<=400000){
  
  start.time <- Sys.time()
  marche_simu_time=marche_aleatoire(test_ligne1,z)
  probas_ligne1=proba_sommets(marche_ligne1,20,z)
  end.time <- Sys.time()
  
  time.taken <- end.time - start.time
  
  
  vari_ligne1[k]=L2(probas_ligne1,vraies_probas_ligne1)
  temps_ligne1[k]=time.taken
  
  k=k+1
  z=z+30000
}




#temps de calcul par calcul valeur propre

  y=1
  k=1
  vect_ligne1<-vector(mode="numeric",length=20)
  vect_ligne1=rep(1/20,20)
  #vect_ligne[1]=1
  vari_iter_ligne1=vector(mode="numeric")
  temps_iter_ligne1=vector(mode="numeric")
  
   #obligé de trick le code il y a un probleme avec le premier calcul, a l'entrée du while
  temps_iter_ligne1[1]=0
  

  while(y<=1250){
    
    start.time_iter <- Sys.time()
    
    vect_ligne1=as.vector(vect_ligne1)%*%test_ligne1

    end.time_iter <- Sys.time()   
  
    
    vari_iter_ligne1[k]=L2(as.vector(vect_ligne1),vraies_probas_ligne1)
    
    if(k==1){
      temps_iter_ligne1[1]=0
    }
    else{
      temps_iter_ligne1[k]= temps_iter_ligne1[k-1]+(end.time_iter - start.time_iter)
    }

    k=k+1
    y=y+1
    
    
  }

     

donnees<-data.frame()

ggplot(donnees,aes(y=vari_ligne1))+geom_line(aes(x=temps_ligne1),colour="blue") + geom_vline(xintercept=time.taken_calcul_ligne1, colour="red") + geom_line(aes(y=as.vector(vari_iter_ligne1),x=temps_iter_ligne1),colour="black")

L’itération de la fonction de transition semble extrêmement plus performante que la marche aléatoire. Affichons la de plus près, avec la méthode du calcul direct.

plot(x=temps_iter_ligne1,y=vari_iter_ligne1)

ggplot(donnees,aes(y=vari_iter_ligne1))+geom_line(aes(x=temps_iter_ligne1),colour="blue")+geom_vline(xintercept=time.taken_calcul_ligne1, colour="red")

Le calcul direct semble à peine plus efficace, mais la méthode de mesure n’est pas très rigoureuse, les mesures de temps ne me semblent pas très sûres, mais les résultats me paraissent plutôt logiques marche Avec plus de sommets la méthode de l’itération (complexité linéaire 20->40 0.01 ->0.03)semble dépasser la méthode du calcul (complexité logarithmique ? car n’a presque pas bougé). La marche aléatoire semble aussi de complexité linéaire.

Essayons une topologie en anneau et 20 sommets.

## Time difference of 0 secs

## Time difference of 0.002929926 secs

Le calcul semble de même complexité avec la topologie en anneau. La méthode de l’itération est déjà la solution … normal on a 1/N dans tout le vecteur. Pour la marche, on a la même chose en anneau et ligne, ça semble assez normal puisqu’il n y a pas d’état presque absorbant (dont il est dur de sortir), qui nécessiterait plus de pas que ça, ici le nombre de pas est suffisamment grand par rapport de sommet, cela suffit. Essayons avec 40 sommets.

## Time difference of 0.002928972 secs

Pour 40 sommets, pas grand chose à dire, tout semble encore linéaire, sauf pour le calcul dont le temps augmente à peine.

Test avec topologie en sucette ( 20 sommets )

Intéressant, avec la sucette, le calcul commence à devenir moins bon que l’itération. On pourrait imaginer que plus la topologie commence à être complexe, moins le calcul devient efficace. On essaye avec une suc

Mhhh… cette dernière mesure me fait bien penser que rien n’est juste et que je ne peux pas tirer de réel analyse des mesures que j’ai fait. Avec une seule mesure à chaque fois, c’est normal, mais je ne peux pas faire autrement c’est bien trop long, il faudrait que je joue avec les échelles. J’ai été totalement limité par la durée extrêmement grande de mes tests et j’ai perdu un temps fou avec ma fonction qui ne marchait pas pour je ne sais quelle raison, la récupération des temps étant assez hasardeuse. Je ne sais pas quel meilleur moyen j’aurais pu utiliser pour mesurer les perfs sur R, peut-être un calcul de mégaflops ? Dommage, j’aurais voulu moins lutter pour coder et plus analyser et mesurer.