Correction : algorithme PageRank

Marche aléatoire dans un graphe

from random import randint, choice

g = {
'A': ['B','C'],
'B': ['A'],
'C': ['A', 'B', 'D', 'E'],
'D': ['A'],
'E': ['D']
} # ou création d'un objet Graphe

def pagerank_random(g, n):
    PR = {cle: 0 for cle in g}

    s = choice(list(g.keys()))

    for i in range(n):
        PR[s] += 1
        s = choice(g[s])

    return PR

print(pagerank_random(graphe, 100))
			

Calcul direct du PageRank de chaque page

from graphe import Graphe

d = 0.85

mat = [
[0, 1, 1, 0, 0],
[1, 0, 0, 0, 0],
[1, 1, 0, 1, 1],
[1, 0, 0, 0, 0],
[0, 0, 0, 1, 0]
] # ou : mat = g.matrice()

def nbre_liens_sortants(m, v)->int:
    """
    Fonction qui renvoie le nombre total de liens sortants d'un sommet/
    Entrée : v = le sommet d'origine (int)
    Sortie : le nombre total de liens sortants de v (int)
    """
    return sum(m[v]) # nombre de liens sortants = somme des '1' dans la ligne de la matrice correspondant au sommet v


def pagerank_calcul(m: list[list], n: int)-> list:
    """
    Fonction qui applique l'algorithme de calcul du PageRank des sommets d'un graphe.
    Entrées : m = la matrice d'adjacence
              n = nombre d'itérations de l'algorithme
    Sortie : le tableau des PageRank de chaque sommet
    """
    N = len(m)  # nombre de sommets = nombre de ligne dans la matrice
    PR = [1 for _ in range(N)]
    for _ in range(n):
        for i in range(N):
            s = 0
            for j in range(N):
                if m[j][i] == 1:
                    s += PR[j]/nbre_liens_sortants(m, j)
            PR[i] = (1-d) + d*s
    return PR	
    
pr = pagerank_calcul(m, 10)