Implémentation des graphes en Python – Exemple BFS

Implémentation des graphes en Python par l’exemple : Le parcours en largeur python d’un graphe (BFS) est un algorithme utilisé pour parcourir les structures de donnée de graphe. BFS met en œuvre une stratégie spécifique pour visiter tous les sommets d’un graphe.

Introduction – Implémentation des graphes en Python

BFS commence par un sommet, puis il vérifie les voisins du sommet initial, puis les voisins des voisins, etc.

En entrée de l’algorithme il y a le graphe G et un sommet de départ D pour lequel on considère que la distance est 0.

En sortie de l’algorithme sont calculées toutes les distances entre le sommet D et chaque sommet du graphe G ainsi que l’arbre couvrant si le graphe G est connexe (c’est à dire que pour toute paire de sommet il existe un chemin entre eux dans le graphe).

Description de l’algorithme

On utilise les tableaux suivants :

  • Distance[.] : Stocke la distance entre D (sommet de départ) et un autre sommet du graphe.
  • Father[.] : Stocke le sommet père d’un sommet du graphe parcouru.
  • Visite[.] : Stocke l’état de visite du sommet, liste des valeurs possible 0:pas encore visité,1:Visite en cours,2:Visité

On utilise les fonctions suivantes pour une file F :

  • First(F) : Retourne l’élément en tête de la file F sans le supprimer.
  • Dequeue(F) : Retourne l’élément en tête de la file F en le supprimant.
  • Append(F, A) : Mettre l’élément A dans la file F en queue de la file.

Les étapes de l’algorithme :

  • Phase d’initialisation
    • 1. Pour tous les sommets faire
      • Visite = 0 (Pas encore visité)
      • Pere = null (Initialise le tableau)
      • Distance = -1
    • 2. Append(F,D) (ajoute l’élément de départ)
    • 3. Distance[R] = 0 (postulat de départ)
  • Phase d’action (parcours du graphe G)
    • Tant que la file F n’est pas vide
      • t = First(F)
      • Pour tous les voisins v de t faire
        • Si Visite[v] = 0 (sommet non visité) alors
          • Visite[v] = 1 (Visite en cours)
          • Distance[v] = Distance[t] + 1
          • Father[v] = t
          • Append(F,v)
      • Dequeue(F)
      • Visite[t] = 2

Si on détaille les étapes avec le cas du graphe exemple ci-dessous.

Phase d’initialisation :

Implémentation des graphes en python par l'exemple : Le parcours en largeur python d'un graphe, algorithme utilisé pour parcourir les graphes.

Initialisation l’élément A est l’élément de départ à distance 0, il est coloré en orange pour indiquer que la visite est en cours.

Visite des voisins du sommet A (Visite du sommet B)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet B passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

implémentation des graphes en python – Visite des voisins du sommet A (Visite du sommet C)

Implémentation des graphes en python par l'exemple : Le parcours en largeur python d'un graphe, algorithme utilisé pour parcourir les graphes.
Le sommet C passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

Marquage de A comme visité et suppression de la file

Parcours en largeur Python - Algorithme sur les Graphes
A est marqué comme visité (couleur bleue) et retiré de la tête de la file

Visite des voisins du sommet B (Visite du sommet D)

Le sommet C etant marqué comme en cours de visite il ne sera pas visité, on visite le sommet D on calcule sa distance = 2 et on note le sommet B comme père du sommet B.

Marquage de B et C comme visité et suppression de la file

B est marqué comme visité (couleur bleue) et retiré de la tête de la file
C est marqué comme visité (couleur bleue) et retiré de la tête de la file (son voisin D est marqué en cours de visite)

Marquage de D comme visité et fin de l’algorithme

D est marqué comme visité (couleur bleue) et retiré de la tête de la file.
Fin de l’algorithme

Construction de l’arbre couvrant si le graphe est connexe

Si le graphe est connexe on déplie le résultat du parcours et on obtient l’arbre couvrant du graphe qui contient tous les sommets.

Application : Le parcours en largeur d’un graphe (BFS) est utile pour :

  • Vérifier si un graphe est connexe (tous les sommets sont alors marqués comme visités à la fin de l’algorithme).
  • Calculer les distances à partir d’un sommet donné
  • Construire un arbre couvrant du graphe
from collections import deque
def bfs(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    pere = {vertex: None}
    while queue:
      t = queue.popleft()
      for voisin in graph[t]:
        if voisin not in distance:
          queue.append(voisin)
          distance[voisin] = distance[t] + 1
          pere[voisin] = t
    return distance, pere
#Liste d'ajacence du graphe
graph = {
  'A': ['B','C'],
  'B': ['A','C', 'D'],
  'C': ['D'],
  'D': ['C','A']
}
distance,pere = bfs(graph,'A')
print("Distances" + str(distance))
print("Pere = " + str(pere))

Parcours en largeur python – Liens externes

https://fr.wikipedia.org/wiki/Python_(langage)

https://www.python.org/

https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur

Implémentation des graphes en python – Liens internes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/2021/01/21/algorithme-glouton-python/

Implémentation Python de l’algorithme de Dijkstra

Cet article fait suite à l’article suivant sur l’algorithme de Dijkstra : http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Voici l’implémentation Python de l’algorithme

from collections import deque

def dijkstra(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    while queue:
        t = queue.popleft()
        print("On visite le sommet " + str(t))
        for voisin in graph[t]:
                queue.append(voisin)
                nouvelle_distance = distance[t] + graph[t][voisin]
                if(voisin not in distance or nouvelle_distance < distance[voisin]):
                    distance[voisin] = nouvelle_distance
                    print("Met à jour le sommet " + str(voisin) + " avec la distance : " + str(nouvelle_distance))
                    
    return distance



#Liste d'ajacence du graphe
graph = {'A':{'B':15,'C':4},'B':{'E':5},'C':{'E':11,'D':2},'D':{'E':3},'E':{}}
distance = dijkstra(graph,'A')
print("Distances" + str(distance))

Implémentation Python du parcours en largeur dans les graphes (BFS)

Cet article fait suite à celui qui porte sur l’algorithme BFS ici : http://128mots.com/index.php/2020/02/11/parcours-en-largeur-dans-les-graphes-bfs/

L’implémentation Python de cet algorithme est la suivante :

from collections import deque

def bfs(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    pere = {vertex: None}
    while queue:
    	t = queue.popleft()
    	for voisin in graph[t]:
    		if voisin not in distance:
    			queue.append(voisin)
    			distance[voisin] = distance[t] + 1
    			pere[voisin] = t
    return distance, pere


#Liste d'ajacence du graphe
graph = {
	'A': ['B','C'],
	'B': ['A','C', 'D'],
	'C': ['D'],
	'D': ['C','A']
}

distance,pere = bfs(graph,'A')
print("Distances" + str(distance))
print("Pere = " + str(pere))

Parcours en largeur Python – Algorithme sur les Graphes

Le parcours en largeur python d’un graphe (BFS) est un algorithme utilisé pour parcourir les structures de donnée de graphe. BFS met en œuvre une stratégie spécifique pour visiter tous les sommets d’un graphe.

Introduction – Parcours en largeur python

BFS commence par un sommet, puis il vérifie les voisins du sommet initial, puis les voisins des voisins, etc.

En entrée de l’algorithme il y a le graphe G et un sommet de départ D pour lequel on considère que la distance est 0.

En sortie de l’algorithme sont calculées toutes les distances entre le sommet D et chaque sommet du graphe G ainsi que l’arbre couvrant si le graphe G est connexe (c’est à dire que pour toute paire de sommet il existe un chemin entre eux dans le graphe).

Description de l’algorithme

On utilise les tableaux suivants :

  • Distance[.] : Stocke la distance entre D (sommet de départ) et un autre sommet du graphe.
  • Father[.] : Stocke le sommet père d’un sommet du graphe parcouru.
  • Visite[.] : Stocke l’état de visite du sommet, liste des valeurs possible 0:pas encore visité,1:Visite en cours,2:Visité

On utilise les fonctions suivantes pour une file F :

  • First(F) : Retourne l’élément en tête de la file F sans le supprimer.
  • Dequeue(F) : Retourne l’élément en tête de la file F en le supprimant.
  • Append(F, A) : Mettre l’élément A dans la file F en queue de la file.

Les étapes de l’algorithme :

  • Phase d’initialisation
    • 1. Pour tous les sommets faire
      • Visite = 0 (Pas encore visité)
      • Pere = null (Initialise le tableau)
      • Distance = -1
    • 2. Append(F,D) (ajoute l’élément de départ)
    • 3. Distance[R] = 0 (postulat de départ)
  • Phase d’action (parcours du graphe G)
    • Tant que la file F n’est pas vide
      • t = First(F)
      • Pour tous les voisins v de t faire
        • Si Visite[v] = 0 (sommet non visité) alors
          • Visite[v] = 1 (Visite en cours)
          • Distance[v] = Distance[t] + 1
          • Father[v] = t
          • Append(F,v)
      • Dequeue(F)
      • Visite[t] = 2

Si on détaille les étapes avec le cas du graphe exemple ci-dessous.

Phase d’initialisation :

Parcours en largeur Python - Algorithme sur les Graphes

Initialisation l’élément A est l’élément de départ à distance 0, il est coloré en orange pour indiquer que la visite est en cours.

Visite des voisins du sommet A (Visite du sommet B)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet B passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

Visite des voisins du sommet A (Visite du sommet C)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet C passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

Marquage de A comme visité et suppression de la file

Parcours en largeur Python - Algorithme sur les Graphes
A est marqué comme visité (couleur bleue) et retiré de la tête de la file

Visite des voisins du sommet B (Visite du sommet D)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet C etant marqué comme en cours de visite il ne sera pas visité, on visite le sommet D on calcule sa distance = 2 et on note le sommet B comme père du sommet B.

Marquage de B et C comme visité et suppression de la file

B est marqué comme visité (couleur bleue) et retiré de la tête de la file
C est marqué comme visité (couleur bleue) et retiré de la tête de la file (son voisin D est marqué en cours de visite)

Marquage de D comme visité et fin de l’algorithme

Parcours en largeur Python - Algorithme sur les Graphes
D est marqué comme visité (couleur bleue) et retiré de la tête de la file.
Fin de l’algorithme

Construction de l’arbre couvrant si le graphe est connexe

Parcours en largeur Python - Algorithme sur les Graphes
Si le graphe est connexe on déplie le résultat du parcours et on obtient l’arbre couvrant du graphe qui contient tous les sommets.

Application : Le parcours en largeur d’un graphe (BFS) est utile pour :

  • Vérifier si un graphe est connexe (tous les sommets sont alors marqués comme visités à la fin de l’algorithme).
  • Calculer les distances à partir d’un sommet donné
  • Construire un arbre couvrant du graphe

Parcours en largeur python – Liens externes

https://fr.wikipedia.org/wiki/Python_(langage)

https://www.python.org/

https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur

Parcours en largeur python – Liens internes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/2021/01/21/algorithme-glouton-python/

Parcours en profondeur python – algorithmes graphes

Implémentons le parcours en profondeur python d’un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.

Introduction

Le principe et d’explorer le graphe à partir d’un sommet donné et on explore tous ses voisins en allant le plus profond possible (càd en répétant l’opération de sommet visité en sommet visité jusqu’à ce qu’on soit coincé, on revient alors via le chemin emprunté jusqu’au point de départ).

Le parcours en profondeur permet de trouver l’arbre couvrant du graphe qui n’est pas le même en général que l’arbre couvrant trouvé via le parcours en largeur du graphe.

L’algorithme en résumé :

Phase de descente :

Partir du sommet choisi pour démarrer et le marquer.

Tant que c’est possible :

  • Aller vers un voisin non visité et le marquer.
  • Mémoriser l’arrête ou l’arc par lequel on est passé.
  • Si tous les voisins sont déjà visités :
    • Revenir vers le sommet par lequel il a été découvert (backtrack phase : de remontée)

Si tous les sommets du graphe sont visités (sont dans l’arbre couvrant) alors le graphe est connexe sinon le graphe n’est pas connexe.

Exemple Python avec 3 graphes :

Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe connexe
Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe non connexe
Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe connexe

Module Python pour le parcours en profondeur :

#Parcours en profondeur d'un graphe
# Algorithme récursif : Le principe est d'explorer le graphe et de revenir sur ses pas lorsuqu'on est coincé.
def parcours_en_profondeur(graphe, sommet_en_cours:str, sommets_visites:[]):
	print('Essai d explorer le sommet :' + str(sommet_en_cours))
	if sommet_en_cours not in sommets_visites:
		sommets_visites.append(sommet_en_cours) #Ajoute le sommet en cours au noeud visité
		print('Exploration du sommet :' + str(sommet_en_cours))
	sommets_voisins_non_visites = []
	for sommet_voisin in graphe[sommet_en_cours]:
		if sommet_voisin not in sommets_visites:
			sommets_voisins_non_visites.append(sommet_voisin) # Constitue la liste des sommets voisins non encore visité

	for sommet in sommets_voisins_non_visites:
		#pour tout les sommets voisins non visités on effectue un parcours en profondeur
		parcours_en_profondeur(graphe, sommet, sommets_visites)

#Fonction de test si le graphe est connexe suite à un parcours en profondeur
def est_un_graphe_connexe(graphe, sommets_visites):
	if len(sommets_visites) == len(graphe):
		print("Le graphe est connexe")
		print(20 * "-")
	else:
		print("Le graphe n'est pas connexe")
		print(20 * "-")


#Liste d'ajacence du graphe
graphe = {
	'A': ['B','C'],
	'B': ['A','C', 'D'],
	'C': ['D'],
	'D': ['C','A']
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#Exemple de graphe non connexe : Le sommet D n'est pas connecté au graphe
graphe = {
	'A': ['B','C'],
	'B': ['A','C'],
	'C': ['A'],
	'D': []
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#Autre exemple
graphe = {
	'A': ['B','D'],
	'B': ['A','C'],
	'C': [],
	'D': ['A']
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#en fin de parcours si tout les sommets sont dans les sommets visités alors le graphe est connexe

#Note
#J'ai rencotré l'erreur IndentationError: unindent does not match any outer indentation level
#Je l'ai simplement résolu en reprenant toute l'indentation en debut de ligne
#et en la remplaçant par des Tabulation plutot que des espaces
http://128mots.com/index.php/en/2021/01/13/quantum-sort-algorithm/

http://128mots.com/index.php/category/non-classe/

Parcours en profondeur python : Liens externes :

https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes

https://www.kartable.fr/ressources/mathematiques/cours/les-graphes/4795

http://math.univ-lyon1.fr/irem/Formation_ISN/formation_parcours_graphes/graphe/1_notion_graphe.html

Cycle hamiltonien dans un Graphe en moins de 128 mots

Un cycle Hamiltonien est un cycle qui contient tous les sommets du graphe.

Il n’y a pas d’algorithme général (càd valable pour n’importe quel graphe) et efficace (càd pas d’algorithme dans le nombre d’étape de calcul soit un polynôme de la taille du graphe) pour trouver si il y a un cycle hamiltonien dans un graphe.

Cycle hamiltonien source wikipedia

Condition de DIRAC : Si pour tous les sommets u du graphe G degré(u) >= n /2 alors G contient un cycle hamiltonien

Condition de ORE : Si pour toute paire u et v de non voisins deg(u) + deg(v) >=n alors G contient un cycle hamiltorien

Si un graphe vérifie la condition de DIRAC alors il vérifie la condition de ORE (la réciproque est fausse).

Couplage dans un Graphe en moins de 128 mots

Un couplage est un ensemble d’arête deux à deux indépendantes : elle ne partagent pas de sommets.

Exemple de couplage dans un graphe : les 2 arrêtes rouges ne partagent pas de sommets (2 à 2 indépendantes)

Couplage parfait : Chaque sommet du graphe est dans exactement une arrête du couplage

Exemple de couplage parfait dans un graphe

Un graphe parfait a un nombre pair de sommets (la réciproque n’est pas vraie)

Un couplage parfait est un couplage de taille maximale (impossible à agrandir, on ne peut pas coupler plus), la réciproque n’est pas vraie.

Exemple de couplage maximal mais pas de taille max (càd il est possible de faire par exemple un couplage avec 3 arrêtes)

Exemple d’utilisation : Dans une entreprises logistique les salariés ont un ou plusieurs permis leur permettant de rouler un certain type de véhicule. On peut représenter le problème dans un graphe avec comme sommet les salariés et les véhicules de l’entreprise. Pour résoudre le problème il faut alors trouver un couplage de taille max.

Algorithme glouton pour trouver un couplage maximal :

Etape 1 : On sélectionne une arrête aléatoirement et on la mémorise dans une copie du graphe (à gauche)

Sélection de l’arrête

Etape 2 : On supprime les arrêtes qui sont incidentes aux deux sommets et on sélectionne une autres arrête aléatoirement

Etape 3 : On supprime les arrêtes qui sont incidentes aux deux sommets, on obtient alors un couplage maximal

PageRank Python – Implémentation de l’algorithme en python

PageRank python est un algorithme utilisé par Google Search pour classer les sites Web dans les résultats de leurs moteurs de recherche. PageRank est un moyen de mesurer l’importance des pages de site Web.

pagerank python

Introduction :

Ce n’est pas le seul algorithme utilisé par Google pour ordonner les résultats des moteurs de recherche, mais c’est le premier algorithme utilisé par la société, il est le plus connu.

Le PageRank d’une page est calculé à partir de la somme du PageRank des pages avec un lien entrant à la page calculée que l’on divise par le nombre de pages sortantes de cette dernière, on applique un facteur d’atténuation pour symboliser la probabilité que l’utilisateur surfe sur une autre page.

Implémentation pagerank python :

J’installe networkx, c’est un package Python pour la création, la manipulation et l’étude de la structure, de la dynamique et des fonctions de réseaux complexes.

Networkx fournit des structures de données et des méthodes pour stocker des graphes que j’utilise pour l’algorithme pagerank.

import networkx as nx
import numpy as np

graphe=nx.DiGraph()

tableauPages = ["A","B","C"] #Exemple de page rank avec 3 pages
graphe.add_nodes_from(tableauPages) #Ajout des sommets du graphe

#on ajoute des arcs, on a :
#la page A a un lien vers B 
#la page B a un lien vers C
#la page C a un lien vers B
#la page C a un lien vers A
# la page B a 2 lien entrant
# la page C a un lien entrant 2 liens sortant
# la page A a un lien entrant un lien sortant
graphe.add_edges_from([('A','B'), ('C','A'),('B','C'), ('C','B')])
print("Sommets du graphe : ")
print(graphe.nodes())
print("Arrêtes du graphe : ")
print(graphe.edges())
#Si on considere un facteur d'attenuation de 0.85 = d
# la formule du page rank est :
#PR(p) = (1-d)/n + d * Somme de toutes les pages(PR(i) des lien entrants à p/nombre de lien sortant de la page qui reference p)
# PR(A) = (1-0,85)/3 + 0,85 * (PR(C)/2)
# PR(B) = (1-0,85)/3 + 0,85 * (PR(A)/1 + PR(C)/2)
# PR(C) = (1-0,85)/3 + 0,85 * (PR(B)/1)

pagerank = nx.pagerank(graphe)
print(pagerank)

Pagerank python liens externes :

https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins

https://www.python.org/

https://www.educative.io/blog/python-algorithms-coding-interview

Liens internes :

http://128mots.com/?s=dijkstra

Glossaire sur les graphes en un peu plus de 128 mots

source wikipedia : Graphe non orienté

Graphe (Graph) : Un ensemble de point reliés entre eux

Sommets (vertices, a vertex) : Les points d’un graphe s’appellent des sommets
Sommets adjacents (adjacent vertices) : Deux sommets sont adjacents si ils sont reliés entre eux
Arête (edge) : La liaison entre deux sommets s’appelle une arête si la relation entre deux sommet n’est pas orientée (pas de notion de précédence, ou d’ordre dans lequel on visite les deux sommets).

source wikipedia : graphe orienté


Arc (arc): La liaison orientée entre deux sommet (c’est une flèche qui indique le sens de la relation orientée, il y a une notion d’ordre d’exécution et de contrainte pour visiter les deux sommets)
Le degré d’un sommet (the degree of a vertex) : Nombre d’arêtes qui partent d’un sommet.
Ordre d’un graphe (order of a graph) : Le nombre de sommet dans un graphe.
Graphe Connexe (connected graph) : Un graphe est connexe si tous les sommets sont reliés par une chaine quelconque.
Chaine Eulerienne (eulerian path) : Une chaine qui prend toutes les arêtes une seule fois du graphe.


Matrice d’adjacente : La matrice d’adjacence d’un graphe est une matrice dont les lignes et les colonnes sont toutes deux indexées par les sommets du graphe, avec un 1 dans la cellule pour la rangée i et la colonne j lorsque les sommets i et j sont adjacents, et un 0 sinon.

source wikipedia : matrice d’adjacence