Programme Officiel
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.
Présentation du module 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:
- Sommet/Noeud: node
- Arête/lien: edge
- Graphe: graph
- Voisins: neighbors
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!
Parcourir un graphe
Tous comme pour les arbres, il est possible de réaliser deux types de parcours d'un arbre:
- le parcours en profondeur(Depth-First Search)
- le parcours en largeur(Breadth First Search)
Cependant, contrairement aux arbres
- il n'y a pas de racine, donc on doit choisir à partir de quel noeud on part: le noeud source.
- il peut y avoir un nombre quelconque d'arêtes, et il faut donc marquer les chemins déjà empruntés lors du parcours.
Parcours en profondeur
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)Utilisation de 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
---------------------------------
Implémentation en Python
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é.
- Reproduire le graphe est l'annoter avec des flèches numérotées pour indiquer l'ordre de viste.
- Faire apparaitre les demi-tours(backtrack en anglais).
- Proposer un autre parcours en profondeur au départ de Nice.
Parcours en largeur
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);Utilisation de 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
---------------------------------
Implémentation en Python
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.
- Reproduire le graphe est l'annoter avec des flèches numérotées pour indiquer l'ordre de viste.
- Proposer un autre parcours en largeur au départ de Nice.
Repérer la présence d'un cycle
- cycle
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.
Principe
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_).
Implémentation
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
----------------------------
Chercher un chemin dans un 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
------------------------------
