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.

Lien vers le programme complet

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

Entrée
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!

png

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.


Entrée
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))
Sortie
Liste des chemins suivis
------------------------
[('Nice', 'Marseille'), ('Marseille', 'Lyon'), ('Lyon', 'Paris'), ('Paris', 'Toulouse'), ('Toulouse', 'Montpellier'), ('Toulouse', 'Rennes'), ('Paris', 'Nancy')]

Représentation sous forme d'arbre
---------------------------------

png

Implémentation en Python

Nous allons implémenter la procédure parcours_en_profondeur proposée précedemment.


Entrée
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))
Sortie
Liste des noeuds visités par notre algorithme
---------------------------------------------
Nice
Marseille
Lyon
Paris
Toulouse
Montpellier
Rennes
Nancy
None

Pour rappel: Forme du graphe
------------------------------

png

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.


Entrée
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))
Sortie
Liste des chemins suivis
------------------------
[('Nice', 'Marseille'), ('Nice', 'Lyon'), ('Marseille', 'Montpellier'), ('Lyon', 'Paris'), ('Lyon', 'Nancy'), ('Montpellier', 'Toulouse'), ('Paris', 'Rennes')]

Représentation sous forme d'arbre
---------------------------------

png

Implémentation en Python

Nous allons implémenter la procédure parcours_en_largeur proposée précedemment.


Entrée
# 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))
Sortie
Liste des noeuds visités par notre algorithme
---------------------------------------------
Nice
Marseille
Lyon
Montpellier
Paris
Nancy
Toulouse
Rennes
None

Pour rappel: Forme du graphe
------------------------------

png

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é.


Entrée
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))
Sortie
Présence d'un cycle
-------------------
True

Pour rappel: Forme du graphe
----------------------------

png


Entrée
# 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))
Sortie
Présence d'un cycle
-------------------
False

Pour rappel: Forme du graphe
----------------------------

png

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.

 

Thumbnail of Youtube video JPeCmKFrKio

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))
Sortie
Liste des noeuds visités par notre algorithme
---------------------------------------------
True
True
False

Pour rappel: Forme du graphe
------------------------------

png