Contenus | Capacités attendues | Commentaires |
---|---|---|
Algorithmes sur les graphes. | Parcourir un graphe en profondeur dâabord, en largeur dâabord. RepĂ©rer la prĂ©sence dâun cycle dans un graphe. Chercher un chemin dans un graphe. | Le parcours dâun labyrinthe et le routage dans Internet sont des exemples dâalgorithme sur les graphes. Lâexemple des graphes permet dâillustrer lâutilisation des classes en programmation. |
Dans ce chapitre, nous allons voir quelques algorithmes classiques sur les graphes. Pour mĂ©moire, un graphe est un ensemble de sommets reliĂ©s entre eux par des arĂȘtes sans aucune contrainte sur la façon dont sont reliĂ©s les sommets par opposition aux arbres qui prĂ©sente une racine, et une relation de descendance.
networkx
Pour travailler sur ce chapitre, nous allons utiliser la librairie networkx
qui permet de facilement créer, manipuler et représenter les graphes en Python.
Nous n'entrerons pas dans les détails de tout ce que l'on peut faire avec cette libraririe, mais nous utiliserons la classe Graph
que nosu instancierons sous la variable G
.
La librairie étant écrite en anglais, il faut connaitre les traductions suivantes:
import networkx as nx
import matplotlib.pyplot as plt # pour les représentations graphiques
def create_graph():
G = nx.Graph()
# Ajout des noeuds nommés
G.add_node("Paris")
G.add_node("Lyon")
G.add_node("Marseille")
G.add_node("Nice")
G.add_node("Montpellier")
G.add_node("Toulouse")
G.add_node("Rennes")
G.add_node("Nancy")
# Ajout des arĂȘtes
G.add_edge("Paris", "Lyon")
G.add_edge("Lyon", "Marseille")
G.add_edge("Nice", "Marseille")
G.add_edge("Nice", "Lyon")
G.add_edge("Montpellier", "Marseille")
G.add_edge("Montpellier", "Toulouse")
G.add_edge("Paris", "Toulouse")
G.add_edge("Rennes", "Toulouse")
G.add_edge("Rennes", "Paris")
G.add_edge("Nancy", "Paris")
G.add_edge("Nancy", "Lyon")
return G
# création du graph
G =create_graph()
# Représenation graphique
nx.draw(G, with_labels=True) # Il s'agit du graphe et non d'une carte!
Tous comme pour les arbres, il est possible de réaliser deux types de parcours d'un arbre:
Cependant, contrairement aux arbres
L'exploration d'un parcours en profondeur depuis un sommet S fonctionne comme suit. Il poursuit alors un chemin dans le graphe jusqu'Ă un cul-de-sac ou alors jusqu'Ă atteindre un sommet dĂ©jĂ visitĂ©. Il revient alors sur le dernier sommet oĂč on pouvait suivre un autre chemin puis explore un autre chemin (voir vidĂ©o ci-contre). L'exploration s'arrĂȘte quand tous les sommets depuis S ont Ă©tĂ© visitĂ©s. Bref, l'exploration progresse Ă partir d'un sommet S en s'appelant rĂ©cursivement pour chaque sommet voisin de S.
Article Wikipédia sur l'Algorithme de parcours en profondeur
Nous allons utiliser l'algorithme proposé sur l'article Wikipedia anglais:
PROCEDURE parcours_en_profondeur(G graph, s sommet)
marquer v comme visté
POUR TOUS les sommets voisins v de s FAIRE
SI v n'est pas marqué comme visité ALORS
APPELER RECURSIVEMENT parcours_en_prfondeur(G, v)
networkx
La librairie networkx
implémente cette traversée avec la méthode dfs_edges
, nous allons examiner sa sortie Ă partir du sommet Nice
, puis nous implémenterons l'algorithme proposé ci-dessus pour comparer les sorties.
print("Liste des chemins suivis")
print("------------------------")
print(list(nx.dfs_edges(G, source="Nice")))
print("\nReprésentation sous forme d'arbre")
print("---------------------------------")
tree = nx.dfs_tree(G, source="Nice")
nx.draw(tree, with_labels=True, pos=nx.spring_layout(G))
Liste des chemins suivis
------------------------
[('Nice', 'Marseille'), ('Marseille', 'Lyon'), ('Lyon', 'Paris'), ('Paris', 'Toulouse'), ('Toulouse', 'Montpellier'), ('Toulouse', 'Rennes'), ('Paris', 'Nancy')]
Représentation sous forme d'arbre
---------------------------------
Nous allons implémenter la procédure parcours_en_profondeur
proposée précedemment.
G = create_graph()
# procedure DFS(G, v) is
def parcours_profondeur(G, s):
# afficher le sommet
print(s)
# marquer le sommet s
node = G.nodes[s]
node["visited"] = True
# POUR TOUT sommet t voisin du sommet s
for t in G.neighbors(s):
node = G.nodes[t]
# SI t n'est pas marqué ALORS
if not(node.get("visited")):
parcours_profondeur(G, t)
print("Liste des noeuds visités par notre algorithme")
print("---------------------------------------------")
print(parcours_profondeur(G, "Nice"))
print("\nPour rappel: Forme du graphe")
print("------------------------------")
nx.draw(G, with_labels=True, pos=nx.spring_layout(G))
Liste des noeuds visités par notre algorithme
---------------------------------------------
Nice
Marseille
Lyon
Paris
Toulouse
Montpellier
Rennes
Nancy
None
Pour rappel: Forme du graphe
------------------------------
L'ordre de parcours des chemins dépend de l'ordre dans lequel les voisins sont visités par la méthode neighbors
. Cependant on observe bien que l'algorithme avance tant qu'il ne trouve pas un noeud déjà visité.
L'algorithme de parcours en largeur (ou BFS, pour Breadth First Search en anglais) permet le parcours d'un graphe ou d'un arbre de la maniĂšre suivante : on commence par explorer un nĆud source, puis ses successeurs, puis les successeurs non explorĂ©s des successeurs, etc. L'algorithme de parcours en largeur permet de calculer les distances de tous les nĆuds depuis un nĆud source dans un graphe non pondĂ©rĂ© (orientĂ© ou non orientĂ©).
Article Wikipédia sur l'Algorithme de parcours en largeur
Nous allons implémenter cet algorithme à l'aide d'une file:
FONCTION parcours_largeur(Graphe G, Sommet s):
f = CreerFile();
f.enfiler(s);
marquer(s);
TANT QUE la file est non vide
s = f.defiler();
afficher(s);
POUR TOUT voisin t de s dans G
SI t non marqué
f.enfiler(t);
marquer(t);
networkx
La librairie networkx
implémente cette traversée avec la méthode bfs_edges
, nous allons examiner sa sortie Ă partir du sommet Nice
, puis nous implémenterons l'algorithme proposé ci-dessus pour comparer les sorties.
print("Liste des chemins suivis")
print("------------------------")
print(list(nx.bfs_edges(G, source="Nice")))
print("\nReprésentation sous forme d'arbre")
print("---------------------------------")
tree = nx.bfs_tree(G, source="Nice")
nx.draw(tree, with_labels=True, pos=nx.spring_layout(G))
Liste des chemins suivis
------------------------
[('Nice', 'Marseille'), ('Nice', 'Lyon'), ('Marseille', 'Montpellier'), ('Lyon', 'Paris'), ('Lyon', 'Nancy'), ('Montpellier', 'Toulouse'), ('Paris', 'Rennes')]
Représentation sous forme d'arbre
---------------------------------
Nous allons implémenter la procédure parcours_en_largeur
proposée précedemment.
# On repart d'un graphe non annoté
G = create_graph()
# FONCTION parcours_largeur(Graphe G, Sommet s):
def parcours_largeur(G, s):
#f = CreerFile();
#f.enfiler(s);
f = [s]
#marquer(s);
node = G.nodes[s]
node["visited"] = True
#TANT QUE la file est non vide
while f:
#s = f.defiler();
s = f.pop()
# afficher(s);
print(s)
#POUR TOUT voisin t de s dauuuuns G
for t in G.neighbors(s):
node = G.nodes[t]
#SI t non marqué
if not(node.get("visited")):
#f.enfiler(t);
f.insert(0, t)
#marquer(t);
# marquer le sommet s
node["visited"] = True
print("Liste des noeuds visités par notre algorithme")
print("---------------------------------------------")
print(parcours_largeur(G, "Nice"))
# je ne sais pas d'ou vient ce dernier None!
print("\nPour rappel: Forme du graphe")
print("------------------------------")
nx.draw(G, with_labels=True, pos=nx.spring_layout(G))
Liste des noeuds visités par notre algorithme
---------------------------------------------
Nice
Marseille
Lyon
Montpellier
Paris
Nancy
Toulouse
Rennes
None
Pour rappel: Forme du graphe
------------------------------
L'ordre de parcours des chemins dépend de l'ordre dans lequel les voisins sont visités par la méthode neighbors
. Cependant on observe bien que l'algorithme explore toujours tous les voisins d'un sommet avant d'avancer d'une profondeur supplémentaire.
Un cycle est une suite d'arĂȘtes consĂ©cutives (chaine simple) dont les deux sommets extrĂ©mitĂ©s sont identiques.
Dans notre graphique Nice - Marseille - Lyon forme un cycle
La dĂ©tection de cycle peut-ĂȘtre interressante par exemple en programmation concurrente dans les systĂšmes d'exploitation pour dĂ©tecter un interblocage(deadlock) qui se produit lorsque des processus concurrents s'attendent mutuellement.
Les processus bloqués dans cet état le sont définitivement, il s'agit donc d'une situation catastrophique.
Pour dĂ©tecter un cycle nous allons simplement parcourir le graphe en profondeur et vĂ©rifier qu'aucune arĂȘte pointe vers un noeud dĂ©jĂ visitĂ©(prĂ©sence d'un backedge_).
Voici le code proposé.
G = create_graph()
def recherche_cycle(G, s):
# marquer le sommet s
node = G.nodes[s]
node["visited"] = True
# POUR TOUT sommet t voisin du sommet s
for t in G.neighbors(s):
node = G.nodes[t]
# SI t n'est pas marqué ALORS
if not(node.get("visited")):
recherche_cycle(G, t)
else:
# si déjà visité c'est un cycle
return True
return False
print("Présence d'un cycle")
print("-------------------")
print(recherche_cycle(G, "Nice"))
# Test de la fonction à partir de tous les noeuds de départ
for node in G.nodes:
# networkx est capable de trouver des cycles
assert nx.find_cycle(G, source=node)
# on teste notre fonction maintenant
assert recherche_cycle(G, node)
print("\nPour rappel: Forme du graphe")
print( "----------------------------")
nx.draw(G, with_labels=True, pos=nx.spring_layout(G))
Présence d'un cycle
-------------------
True
Pour rappel: Forme du graphe
----------------------------
# Nous supprimons quelques arĂȘtes pour
# retirer les cycles et tester la fonction
def create_acyclic_graph():
G = create_graph()
G.remove_edge("Nice", "Lyon")
G.remove_edge("Nancy", "Lyon")
G.remove_edge("Paris", "Rennes")
G.remove_edge("Toulouse", "Montpellier")
return G
G = create_acyclic_graph()
print("Présence d'un cycle")
print("-------------------")
print(recherche_cycle(G, "Paris"))
# Test de la fonction à partir de tous les noeuds de départ
for node in G.nodes:
try:
nx.find_cycle(G, source=node)
assert False
except nx.NetworkXNoCycle:
pass
G = create_acyclic_graph()
assert not(recherche_cycle(G, node))
print("\nPour rappel: Forme du graphe")
print( "----------------------------")
nx.draw(G, with_labels=True, pos=nx.spring_layout(G))
Présence d'un cycle
-------------------
False
Pour rappel: Forme du graphe
----------------------------
La recherche de chemin(pathfinding), et un domaine important de recherche dans le développement de l'intelligence artificielle et de la robotique.
Souvent, on s'interresera pkus prĂ©cisĂ©ment Ă la recherche du plus court chemin sur des graphes pondĂ©rĂ©s, c'est Ă dire sur lesquelles on ajoute un poids Ă l'arĂȘte, dans notre exemple, on pourrait ajouter les temĂčps ou distance des routes entre chaque ville.
Il existe deux principaux algorithmes de plus court chemin, cette vidéo, vous présente l'algorithme de Dijkstra.
Le programme ne demanadant que le recherche d'un chemin dans un graphe, je vous présente un algorithme de recherche de chemin qui indique simplement le chemin s'il existe sans s'assurer qu'il s'agit du plus court chemin.
Utilisons un parcours en largeur pour faire cette recherche qui permettra de minimiser le nombre d'arĂȘtes traversĂ©es par rapport Ă une recherche en profondeur.
------
<div class="card text-white bg-gradient-dark">
<div class="card-header"><small class="text-muted">Entrée</small></div>
```python
# On repart d'un graphe non annoté
G = create_graph()
# FONCTION parcours_largeur(Graphe G, Sommet s):
def recherche_chemin(G, départ=None, arrivée=None):
"""Rechecrche de chemin
On se contente d'indiquer si le chemin existe
Returns
-------
bool
"""
profondeur = 0
#f = CreerFile();
#f.enfiler(s);
f = [départ]
#marquer(s);
node = G.nodes[départ]
node["visited"] = True
#TANT QUE la file est non vide
while f:
#s = f.defiler();
s = f.pop()
#POUR TOUT voisin t de s dans G
for t in G.neighbors(s):
node = G.nodes[t]
if t == arrivée:
return True
#SI t non marqué
elif not(node.get("visited")):
#f.enfiler(t);
f.insert(0, t)
#marquer(t);
# marquer le sommet s
node["visited"] = True
return False
print("Liste des noeuds visités par notre algorithme")
print("---------------------------------------------")
print(recherche_chemin(create_graph(), "Nice", "Paris"))
print(recherche_chemin(create_graph(), "Nice", "Rennes"))
print(recherche_chemin(create_graph(), "Nice", "Massilia"))
# je ne sais pas d'ou vient ce dernier None!
print("\nPour rappel: Forme du graphe")
print("------------------------------")
nx.draw(G, with_labels=True, pos=nx.spring_layout(G))
Liste des noeuds visités par notre algorithme
---------------------------------------------
True
True
False
Pour rappel: Forme du graphe
------------------------------