Implémentation Python des algorithmes de parcours de graphes

Algorithmes BFS et DFS

Vous allez maintenant implémenter les algorithmes vus au chapitre précédent.

Préalablement, il faudra que vous disposiez des ressources vous permettant de gérer un graphe bien sûr, mais également les structures de données ( pile et file ) nécessaires aux parcours.

Pour les graphes : vous allez utiliser la classe Graphe que vous avez codée précédemment; une implémentation sous forme de matrice d'adjacence serait mal adaptée ( pourquoi ?? )
Pour la file : vous avez plusieurs possibilités, qui utilisent toutes le paradigme de programmation objet :
- soit utiliser l'implémentation POO de la file que vous aviez écrite à partir d'une liste Python, mais qui présente des limitations en terme de complexité ( même si a priori ici, les files ne seront jamais très grandes, mais sait-on jamais...)
- soit utiliser l'implémentation POO de la file avec deux piles que vous aviez faite en exercice, qui est déjà un peu meilleure en complexité
- soit utiliser une classe Python dédiée spécialement à la gestion des files ( et aussi des piles ), et qui est optimisée pour cela, la classe deque ( voir ci-dessous ).
Pour la pile : là-aussi, plusieurs solutions :
- la classe écrite par vous-même, qui utilise une liste Python ( donc de bonne complexité puisque n'utilisant que les méthodes de liste Python pop() et append() qui sont en O(1). )
- la classe deque, encore plus optimisée.

Les deques sont une généralisation des piles et des files ( deque se prononce "dèque" et est l'abréviation de l'anglais double-ended queue) : il est possible d'ajouter et retirer des éléments par les deux bouts des deques. Celles-ci gèrent des ajouts et des retraits utilisables par de multiples fils d'exécution (thread-safe) et efficients du point de vue de la mémoire des deux côtés de la deque, avec approximativement la même performance en O(1) dans les deux sens.

Il faut importer la classe deque à partir du module collections :


from collections import deque

Pour créer une deque vide :


pile = deque() # ou file = deque() bien sûr...

Il existe plusieurs méthodes pour ajouter/retirer des éléments à chaque "extrémité" d'une deque :

	A gauche	A droite
insertion d'un élément	`appendleft(x)`	`append(x)`
suppression et renvoi d'un élément	`popleft()`	`pop()`

Chaque extrémité d'une deque étant parfaitement équivalente en terme de complexité, à vous de choisir les méthodes adaptées pour la gestion de votre file ou de votre pile.

Enfin, la fonction len() peut être appliquée à une deque pour déterminer le nombre d'éléments qu'elle contient.


len(pile) # renvoie le nombre d'éléments dans la deque

Dans un script qui importe tous les modules nécessaires, écrire le code :

Du parcours de graphe en largeur d'abord ( BFS ) :

from graphe import Graphe from collections import deque def BFS(G: Graphe, r:str)->list: '''Fonction de parcours en largeur d'abord d'un graphe Entrées : G = objet de type Graphe r = racine du parcours ( chaîne de caractères ) Sortie : parcours du graphe sous forme de liste des sommets parcourus ''' pass

Du parcours de graphe en profondeur d'abord ( DFS ) non récursif :

from graphe import Graphe from collections import deque def DFS(G: Graphe, r:str)->list: '''Fonction de parcours en profondeur d'abord d'un graphe Entrées : G = objet de type Graphe r = racine du parcours ( chaîne de caractères ) Sortie : parcours du graphe sous forme de liste des sommets parcourus ''' pass

Du parcours de graphe en profondeur d'abord récursif :

from graphe import Graphe from collections import deque def DFS_recursif(G: Graphe, u:str, marque: list, parcours: list ): '''Fonction de parcours en largeur d'un graphe Entrées : G = objet de type Graphe u = sommet exploré ( chaîne de caractères ), racine du parcours au premier appel marque = dictionnaire des sommets déjà visités, initialisé en dehors de la fonction parcours = liste des sommets parcourus, initialisé en dehors de la fonction Sortie : aucune ''' pass

Pour améliorer l'interface de cette version, on pourra bien entendu utiliser la technique des "2 fonctions", de façon à ce qu'un utilisateur n'ait à passer que les arguments strictement nécessaires au parcours ( le graphe et le sommet de départ )...

SOLUTION

Applications

Détermination de la présence d'un cycle

Un graphe non orienté présente un cycle si il existe une chaîne dont les sommets de début et d'extrémité sont identiques.
Dans le cas d'un graphe orienté, une telle suite d'arcs est appelée un circuit.

La recherche de la présence d'un cycle dans un graphe permet de détecter, par exemple, des situations où des informations tourneraient "en boucle" dans un réseau, et optimiser celui-ci.

Le parcours en profondeur permet de déterminer la présence d’un cycle dans un graphe.

Détecter un cycle dans un graphe non orienté est assez simple :

on garde la trace des sommets non pas simplement "découverts" ( = visités ), mais complètement explorés : on ne marque donc un sommet que lorsqu'il a été sorti de la pile.
le graphe présente alors un cycle tout simplement si on atteint lors du parcours un sommet qui a déjà été exploré auparavant.


fonction cycle(G: graphe, s: sommet (quelconque)):
	p ← pile vide
	empiler(s)
	visites ← dictionnaire initialisé à False pour chaque sommet
	  
  	tant que p n'est pas vide :
  		u ← depiler(p)
    	pour chaque sommet v adjacent au sommet u :
    		si v n'a pas encore été visité :
    			empiler(v)
    		fin si
    	fin pour
    	si u a déja été visité :
    		renvoyer Vrai
    	sinon :
    		marquer u comme visité
    	fin si
	fin tant que
	renvoyer Faux

Puisque l'algorithme parcourt tous les sommets accessibles du graphe, la racine du parcours peut être n'importe quel sommet.

Écrire une fonction contient_cycle qui détecte si un graphe non-orienté comporte un cycle.

tester la fonction avec quelques graphes, en les affichant éventuellement pour vérifier la présence de cycles.
utiliser cette fonction pour détecter un cycle dans un graphe en partant de chaque sommet.
Améliorer la sortie de la fonction de façon à ce qu'elle renvoie le cycle éventuellement détecté.

from graphe import Graphe # à importer comme module dans cet éditeur from collections import deque def contient_cycle(G: Graphe)->bool: '''Fonction qui détermine si un graphe non-orienté contient un cycle. Entrée : G = objet de type Graphe Sortie : booléen True si le graphe contient un cycle, False sinon ''' pass

SOLUTION

Existence d'un chemin

Un chemin dans un graphe orienté est une succession d'arcs qui permet d'aller d'un sommet à un autre; c'est donc l'équivalent d'une chaîne dans un graphe orienté.
Mais pour simplifier nous utiliserons le terme "chemin" aussi bien dans le cas des graphes orientés ou non.

Comment déterminer si il existe un chemin entre deux sommets, et surtout, quel est alors ce chemin ? Voila un problème qui se rencontre par exemple dans la recherche de la sortie d'un labyrinthe ( ce sera traité en application.), ou alors savoir si un routeur donné dans un réseau est accessible de tous les autres.

Le parcours en profondeur permet de trouver un chemin entre deux sommets ( dont l'un constitue la racine du parcours ) : en effet, il suit les sommets de voisins en voisins, et "revient en arrière" si il aboutit à une impasse pour "repartir" d'un nouvel embranchement ( c'est pourquoi on parle parfois de bactracking ou retour en arrière pour cet algorithme ).

Attention, l'algorithme permet simplement de savoir si un chemin existe entre deux sommets, ce n'est pas forcément le plus court !

Le problème est que le parcours du graphe ne garde pas la trace des sommets sur le chemin à suivre : le parcours explore tous les sommets du graphe, mais on ne voudrait "garder" que ceux "par lesquels il faut passer"...

Pour cela, il va donc falloir, pour chaque sommet visité, stocker ( par exemple dans un dictionnaire ) le prédécesseur dans le parcours du graphe de ce sommet, c'est à dire le "sommet d'où l'on vient"; à l'aide de ce dictionnaire, on pourra alors, en "remontant" de "père en père" la liste de ses prédécesseurs jusqu'à la racine du parcours, déterminer le chemin à suivre.

Par exemple, dans le graphe ci-contre, le dictionnaire des prédécesseurs associé à un parcours depuis le sommet 'A' est :


pred = {'A': 'A', 'B': 'A', 'C': 'A', 'D': 'A', 'E': 'D', 'F': 'E'}

A partir de ce dictionnaire, on peut alors "reconstruire" n'importe que chemin depuis le sommet'A', en remplaçant progressivement un sommet par son prédécesseur.
Par exemple, pour le chemin de 'A' à 'F' :


'F' <- 'E' <- 'D' <- 'A'

( non, ce n'est pas le plus court chemin...)

Ce dictionnaire joue même deux rôles, puisqu'il sert également à "marquer" les sommets déjà visités ( et remplace donc le dictionnaire marque du parcours en profondeur ) : un sommet qui n'est pas encore dans le dictionnaire n'a donc pas encore été visité...

Dans ce dictionnaire, la racine du parcours sera le sommet qui est son propre prédécesseur ( à initialiser au début du parcours ).

Utilisation du parcours en profondeur pour trouver un chemin

Qu'est-ce qui dans l’algorithme de parcours en profondeur permettra de savoir si le chemin existe ? n'existe pas ?
A quel point faut-il remplir le dictionnaire des prédécesseurs de chaque sommet ?
Écrire alors une fonction existe_chemin qui renvoie le dictionnaire des prédécesseurs pour un parcours entre deux sommets quelconques depart et fin d'un graphe si un chemin existe effectivement.
Proposer une amélioration de l'efficacité de l'algorithme dans le cas d'un très grand graphe...

from graphe import Graphe # à importer comme module dans cet éditeur from collections import deque def existe_chemin(G: Graphe, depart: str, fin: str)->dict: '''Fonction qui renvoie le dictionnaire des prédécesseurs pour un parcours d'un graphe entre deux de ses sommets, si le chemin entre ces sommets existe. Entrées : G = objet de type Graphe depart = sommet de départ fin = sommet d'arrivée Sortie : le dictionnaire des prédécesseurs des sommets si le chemin existe une information indiquant que le chemin n'existe pas dans le cas contraire ''' pass # Graphe de l'exemple de ce paragraphe g = Graphe(['A', 'B', 'C', 'D', 'E', 'F']) g.ajoute_arete('A', 'B') g.ajoute_arete('A', 'C') g.ajoute_arete('A', 'D') g.ajoute_arete('B', 'D') g.ajoute_arete('C', 'D') g.ajoute_arete('D', 'E') g.ajoute_arete('E', 'F') g.ajoute_arete('B', 'F')

SOLUTION

Une fonction pour reconstruire un chemin

On suppose maintenant disposer du dictionnaire des prédécesseurs complet ( donc, à la fin du parcours ); le chemin sera alors déterminé à partir de ce dictionnaire à l'aide d'une fonction annexe chemin.

Le chemin sera renvoyé sous la forme d'une liste des sommets à suivre depuis le début jusqu'à la fin du chemin : ['A', 'D', 'E', 'F']

Écrire cette fonction, et la tester avec un dictionnaire simple.

Cette fonction peut être codée très simplement sous forme récursive ! Comme d'habitude, réfléchir à son cas de base et à son cas général...

def chemin(fin: str, pred: dict)->list: '''Fonction qui reconstruit le chemin depuis un sommet jusqu'à la racine du parcours, en utilisant le dictionnaire des prédécesseurs de chaque sommet dans le parcours. Entrées : fin = le sommet à atteindre pred = le dictionnaire associant à chaque sommet l'étiquette de son prédécesseur dans le parcours Sortie : la liste ( dans l'ordre ) des sommets à suivre depuis la racine du parcours jusqu'au sommet 'fin' ''' pass # Dictionnaire pour l'exemple de ce paragraphe : pred = {'A': 'A', 'B': 'A', 'C': 'A', 'D': 'A', 'E': 'D', 'F': 'E'}

SOLUTION

Recherche et affichage

Utiliser maintenant les deux fonctions conjointement pour vérifier que la recherche du chemin est effective dans le graphe de l'exemple de ce paragraphe :

from graphe import Graphe # à importer comme module dans cet éditeur from collections import deque def existe_chemin(G: Graphe, depart: str, fin: str)->dict: pass def chemin(fin: str, pred: dict)->list: pass # Graphe de l'exemple de ce paragraphe g = Graphe(['A', 'B', 'C', 'D', 'E', 'F']) g.ajoute_arete('A', 'B') g.ajoute_arete('A', 'C') g.ajoute_arete('A', 'D') g.ajoute_arete('B', 'D') g.ajoute_arete('C', 'D') g.ajoute_arete('D', 'E') g.ajoute_arete('E', 'F') g.ajoute_arete('B', 'F')

Plus court chemin entre deux sommets

Voila un autre problème, mais vous allez voir que ce n'est pas beaucoup plus compliqué...

Vous imaginez bien : cette fois-ci, c'est le parcours en largeur qui va permettre de résoudre ce problème.

En effet, le parcours en largeur parcourt les sommets du graphe en "s'éloignant" progressivement de la racine du parcours; lorsqu'on rencontre le sommet d'arrivée, on est donc assurés d'avoir parcouru le plus petit nombre d'arêtes/arcs.

On doit cependant là aussi garder la trace des sommets à parcourir, c'est pourquoi le stockage des prédécesseurs de chaque sommet dans le parcours sera également nécessaire.

Écrire une fonction plus_court_chemin() de façon à ce qu'elle renvoie le plus court chemin entre deux sommets quelconques, en utilisant également la fonction annexe de reconstruction du chemin.

L'algorithme trouve-t-il cette fois bien le plus court chemin ?

from graphe import Graphe # à importer comme module dans cet éditeur from collections import deque def chemin(s: str, pred: dict)->str: pass def plus_court_chemin(G: Graphe, s1: str, s2:str)->dict: '''Fonction qui renvoie le dictionnaire des prédécesseurs pour un parcours d'un graphe entre deux de ses sommets, si le chemin entre ces sommets existe. Entrées : G = objet de type Graphe depart = sommet de départ fin = sommet d'arrivée Sortie : le dictionnaire des prédécesseurs des sommets si le chemin existe une information indiquant que le chemin n'existe pas dans le cas contraire ''' pass

SOLUTION

recherche d'un chemin → parcours en profondeur
recherche du plus court chemin → parcours en largeur

Pourquoi ne pas toujours utiliser le parcours en largeur pour trouver un chemin dans un graphe, puisque celui-ci nous donne en plus le plus court des chemins ( si il existe bien entendu ) ?

Il faut voir que le parcours en largeur parcours tous les sommets du graphe en "s'éloignant" progressivement du sommet de départ; dans un très grand graphe, il peut se passer un moment avant que l'on ne "tombe" sur le sommet d'arrivée si celui-ci se trouve très éloigné du départ.

Le parcours en profondeur "explore" au contraire un chemin en suivant toutes les possibilités jusqu'à aboutir à une "impasse", auquel cas il "retourne en arrière" pour "explorer une nouvelle piste"; il y a donc beaucoup plus de chances que l'on tombe ainsi plus rapidement sur le sommet d'arrivée, dans la mesure bien sûr où le chemin existe...

Il existe des algorithmes de recherche de plus court chemin plus efficaces que BFS, mais si la seule recherche de l'existence d'un chemin suffit, alors DFS peut suffire...

Distances depuis un sommet

Algorithme pas au programme officiel, mais assez simple : c'est un prolongement de celui du parcours en largeur.

La distance entre deux sommets d’un graphe est la longueur du plus petit chemin possible entre ces deux sommets. Dans un graphe non pondéré, elle est donc égale au nombre minimal d'arêtes/d'arcs à parcourir entre les deux sommets.

Dans le parcours en largeur, on "s'éloigne" petit à petit de la racine du parcours. En tenant le compte du nombre de "niveaux" dont l'algorithme s'est "éloigné" depuis la racine, il permet donc de déterminer la distance entre la racine du parcours et chaque sommet du graphe.

Ceci est une simplification de l'algorithme plus général appelé algorithme de Dijkstra, qui calcule les distances d'un sommet donné à tous les autres dans un graphe pondéré.

Distances dans un graphe — Distances des sommets depuis le sommet A

Distances en nombre d'arcs/d'arètes

Le dictionnaire des prédécesseurs n'est plus nécessaire puisqu'on ne s’intéresse pas ici à un chemin en particulier. A la place, on stockera les distances de chaque sommet à la racine du parcours.

Le principe : on réalise donc un parcours BFS du graphe depuis la racine du parcours.
Pour chaque sommet, on calcule sa distance depuis la racine : pour cela, on a parcouru une arête/un arc de plus depuis le prédécesseur du sommet; la distance de ce sommet à la racine du parcours est donc celle de son prédécesseur augmentée de 1.

Les distances seront donc initialisée à "+∞" pour chaque sommet au début de l'algorithme, indiquant donc un sommet comme "pas encore découvert".

En Python, "+∞" correspond à inf, à importer au préalable depuis le module math.


fonction distances(G: graphe, r: racine du parcours):

	d ← dictionnaire ( par exemple ) associant à chaque sommet sa distance à la racine du parcours, distance initialisée à +∞ pour chaque sommet
	file ← file vide
	
	d[r] ← 0
	enfiler(file, r)

	Tant que file n'est pas vide :
		u ← défiler(file)
		pour chaque sommet v voisin de u :
			si d[v] = +∞ alors :
				enfiler(file, v)
				...............
			fin si
		fin pour
	renvoyer d

a quel moment de l'algorithme change-t-on de "niveau d'exploration" en passant au niveau "suivant" ?
A la ligne 15, quelle est alors l'instruction à écrire pour calculer la distance depuis le sommet v en cours de traitement à la racine r du parcours ?

écrire alors une fonction distances() qui calcule les distances de chaque sommet du graphe à un sommet racine du parcours.


def distances(G: grapheD, r: str)->dict:
	'''Fonction qui calcule les distances du sommet racine du parcours aux autres sommets du graphe
	Entrée :
		G = objet de type GrapheD
		r = étiquette du sommet racine
	Sortie :
		le dictionnaire donnant pour chaque sommet sa distance à la racine.
	'''
	pass

tester la fonction sur un graphe non orienté.
Question subsidiaire : quelle pourrait-être une application de cet algorithme ?

from graphe import Graphe # à importer comme module dans cet éditeur from collections import deque from math import inf def distances(G: Graphe, r: str)->dict: '''Fonction qui calcule les distances du sommet racine du parcours aux autres sommets du graphe Entrée : G = objet de type Graphe r = étiquette du sommet racine Sortie : le dictionnaire donnant pour chaque sommet sa distance à la racine. ''' pass

SOLUTION

Distances dans un graphe pondéré

La situation est plus délicate à traiter : en effet, si il y a plusieurs chemins pour aller jusqu'à un sommet donné, leurs longueurs cumulées ne sont généralement pas les mêmes; il va alors falloir dans ce cas pouvoir déterminer laquelle est la plus petite...

L'algorithme de Dijkstra ( hors programme ) utilise une structure de données appelée file à priorité ( FAP ) pour sélectionner, pour chaque sommet, l'arête/arc de plus faible "poids" dans la longueur totale du chemin à suivre d'un sommet aux autres sommets d'un graphe :

Cet algorithme est étudié en détails ailleurs dans ce cours dans le contexte du routage sur un réseau.

C'est donc un parcours en largeur d'un graphe pondéré avec recherche du plus court chemin; cet algorithme donne un résultat optimal, mais peut être très lent sur de (très) grands graphes.

Une amélioration de l'efficacité de l'algorithme de Dijkstra est l’algorithme A* ( "A-star" ), qui utilise une heuristique pour déterminer à chaque étape, la "direction" vers laquelle aller pour atteindre le sommet d'arrivée.
Cet algorithme ne donne pas forcément un résultat optimal, mais est beaucoup plus rapide; c'est celui qui est utilisé comme IA dans de nombreux jeux.

Visualisation de différents algorithmes de recherche de plus court chemin

https://honzaap.github.io/Pathfinding/