Parcours de Graphes

Ce document vise à illustrer les algorithmes classiques de parcours de graphes

Graphe

Un graphe est un objet mathématique constitué de :

  • un ensemble $V$ de sommets
  • un ensemble $E \subset V \times V$ d'arêtes reliant ces sommets
In [1]:
import networkx as nx
import matplotlib.pyplot as plt

G = nx.gnp_random_graph(10, 0.4)
nx.draw(G)

Ici les sommets sont les points bleus, et les arêtes sont les lignes qui les relient. On distingue les graphes non orientés, pour lesquels les arêtes n'ont pas de notion de direction, et les graphes orientés, pour lesquels l'arête de u à v n'est pas la même que l'arête de v à u. En terme de terminologie, on utilise souvent le terme arc plutôt qu'arête pour le cas non orienté.

Les graphes permettent de modéliser de très nombreux problèmes, et se prêtent également bien à l'étude des structures de données. Une liste chaînée par exemple peut être vue comme un graphe où les sommets sont les cellules et les arêtes sont les liens des cellules vers leurs suivantes. Plus généralement toute structure de donnée ou des petits blocs de mémoire sont liés les uns aux autres par des adresses ou des références se prête bien à ce formalisme.

Le code qui suit vise à générer des graphes et les animer, il n'est pas important pour la compréhension de la suite.

In [2]:
# Cliquer à gauche pour voir ou masquer le code

import matplotlib.animation
from IPython.display import HTML
from scipy.spatial import Delaunay, Voronoi, voronoi_plot_2d
import shapely.geometry as geom
import math
import random

def animate_graph(G, positions, animation, **kwargs):
    fig, ax = plt.subplots(figsize=(10,10))
    plt.close()
        
    def update(frame):
        ax.clear()
        
        nx.draw(G, pos=positions, ax=ax, node_size=200, node_color = animation['colors'][frame], width = animation['widths'][frame], **kwargs)
                
    ani = matplotlib.animation.FuncAnimation(fig, update, frames=len(animation['colors']), interval=80, repeat=True)
    return HTML(ani.to_html5_video())

def disk_lloyd(pts):
    new_pts = []
    vor = Voronoi(pts)
    disk = geom.Point(0,0).buffer(1.0)
    for i in range(len(pts)):
        pt = pts[i]
        r = vor.regions[vor.point_region[i]]
        if -1 not in r:
            p = geom.Polygon([vor.vertices[k] for k in r]).intersection(disk)
            new_pts.append(p.centroid.coords[:][0])
        else:
            new_pts.append(pt)
    return new_pts

def gen_in_disk(size):
    #https://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly
    pts = []
    for i in range(size):
        t = 2*math.pi*random.random()
        u = random.random()+random.random()
        if u>1:
            r = 2-u 
        else:
            r = u
        pts.append((r*math.cos(t), r*math.sin(t)))
    #smooth
    for i in range(20):
        pts = disk_lloyd(pts)
    return pts
        
def delaunay_graph(pts):
    G = nx.Graph()
    delaunay = Delaunay(pts)
    for s in delaunay.simplices:
        for i in range(3):
            v0 = s[i]
            v1 = s[(i+1)%3]
            G.add_edge(v0,v1)
    for i, n in enumerate(G.nodes):
        G.nodes[n]['index'] = i
    for i,e in enumerate(G.edges):
        G.edges[e]['index'] = i
    return G

def leftmost(g, pts):
    lm = 0
    xlm = pts[lm][0]
    for n in G.nodes:
        xn = pts[n][0]
        if xn < xlm:
            lm = n
            xlm = xn
    return lm

def rightmost(g, pts):
    lm = 0
    xlm = pts[lm][0]
    for n in G.nodes:
        xn = pts[n][0]
        if xn > xlm:
            lm = n
            xlm = xn
    return lm

class animated_container:
    
    def __init__(self, G):
        self.init_color = "gray"
        self.pushed_color = "cornflowerblue"
        self.popped_color = "darkorange"
        self.current_color = "gold"
    
        self.init_width = 1
        self.used_width = 5
        
        self.colors = [self.init_color for n in G.nodes]
        self.widths = [self.init_width for e in G.edges]
        
        self.animation = {'colors':[], 'widths':[]}
        self.pop_steps = []
        self.current = None
        
        self.graph = G
        
    def append_animation(self):
        colors = self.colors[:]
        if self.current != None:
            colors[self.current] = self.current_color
        self.animation['colors'].append(colors)
        self.animation['widths'].append(self.widths[:])
        
    def push(self,v,u = None):
        self.colors[self.graph.nodes[v]['index']] = self.pushed_color
        if u != None:
            self.widths[self.graph[u][v]['index']] = self.used_width
        self.append_animation()
        
    def pop(self,u):
        self.colors[self.graph.nodes[u]['index']] = self.popped_color
        self.append_animation()
        self.pop_steps.append(self.graph.nodes.data())
    
    def top(self,v):
        self.current = self.graph.nodes[v]['index']
    
    def empty(self):
        return 

Nous pouvons maintenant générer aléatoirement des graphes permettant d'illustrer facilement les parcours, car leurs arêtes ne partent pas dans tous les sens.

In [3]:
pts = gen_in_disk(200)
G = delaunay_graph(pts)
plt.subplots(figsize=(10,10))
nx.draw(G, pos=pts, node_size = 100)

Traverser un graphe

Le principe de la traversée d'un graphe consiste à partir d'un sommet et étendre le parcours à ses voisins. Il est donc nécessaire de :

  • maintenir un ensemble des sommets à traiter
  • pouvoir déterminer si un sommet a déjà été rencontré

Initialement, seul le sommet de départ a été rencontré et a été traité. On distingue :

  • le parcours en profondeur qui utilise une pile pour l'ensemble des sommets à traiter
  • le parcours en largeur qui utilise une file pour l'ensemble des sommets à traiter

À part cette différence de gestion des sommets à traiter l'algorithme de parcours est le même. De manière générique nous pouvons le coder comme suit.

In [4]:
# G est le graphe
# start le sommet de départ
# s la structure de données à utiliser pour stocker les sommets à traiter

def traverse(G, start, s):    
    # initialement, aucun sommet n'est traité
    for n in G.nodes:
        G.nodes[n]['visited'] = False
    
    # on ajoute le sommet de départ aux sommets à traiter
    s.push(start)
    # on le marque comme vu
    G.nodes[start]['visited'] = True
    
    #tant qu'il reste des sommets à traiter
    while not s.empty():
        # récupérer un sommet à traiter
        t = s.top()
        # si ce sommet a un voisin non vu
        finished = True
        for n in G.neighbors(t):
            if not G.nodes[n]['visited']:
                # marquer le voisin comme vu
                G.nodes[n]['visited'] = True
                # l'ajouter aux sommets à traiter
                s.push(n, t)
                # indiquer qu'un voisin inconnu a été rencontré
                finished = False
                break
        # lorsqu'aucun voisin n'était inconnu
        if finished:
            # retirer le sommet de l'ensemble des sommets à traiter
            s.pop()

Parcours en profondeur à l'aide d'une pile

In [5]:
# Implémentation d'une pile

class stack(animated_container):
    
    def __init__(self, G):
        super().__init__(G)
        
        # la pile est implémentée dans un tableau
        self.data = []
        
    def push(self,v,u = None):
        super().push(v, u)
        
        # l'insertion se fait en fin de tableau
        self.data.append(v)
        
    def pop(self):
        u = self.top()
        super().pop(u)
        
        # le retrait se fait en fin de tableau
        self.data.pop()
        
    def top(self):
        # le sommet de la pile est en fin de tableau
        t = self.data[-1]
        super().top(t)
        return t
    
    def empty(self):
        super().empty()
        return len(self.data) == 0

En utilisant une pile, la politique "last in first out" (LIFO) fait que l'algorithme cherche à avancer le plus possible sans attendre d'avoir fini d'étudier intégralement les voisins d'un sommet.

In [6]:
begin = leftmost(G, pts)
s = stack(G)
traverse(G, begin, s)
In [7]:
animate_graph(G, pts, s.animation)
Out[7]:

Le parcours en profondeur s'exprime beaucoup plus naturellement de façon récursive. Dans cette version, la pile semble avoir disparue, mais c'est la pile d'appels de fonction qui sert de pile pour les calculs.

In [8]:
def recursive_descent(G, v):
    #Pour chaque sommet voisin
    for n in G.neighbors(v):
        #si le sommet est inconnu
        if not G.nodes[n]['visited']:
            #le visiter
            G.nodes[n]['visited'] = True
            #lancer immédiatement son exploration
            recursive_descent(G,n)

def traverse_profondeur(G, start):    
    # initialement, aucun sommet n'est traité
    for n in G.nodes:
        G.nodes[n]['visited'] = False
    
    #visite du sommet initial
    G.nodes[start]['visited'] = True
    #lancement de la récursion
    recursive_descent(G,start)
In [9]:
traverse_profondeur(G, begin)

#vérification que tous les sommets sont visités
for n in G.nodes:
    if not G.nodes[n]['visited']:
        print("a node was missed")

Parcours en largeur à l'aide d'une file

In [10]:
#Implémentation naïve d'une file

class queue(animated_container):
    
    def __init__(self, G):
        super().__init__(G)
        
        #les données sont stockées dans un tableau
        self.data = []
        
    def push(self,v,u = None):
        super().push(v, u)
        #l'insertion est faite en fin de tableau
        self.data.append(v)
        
    def pop(self):
        u = self.top()
        super().pop(u)
        #ouch, la complexité de la suite est mauvaise
        #recopier tout le tableau sans son premier élément
        #le retrait à donc lieu au début
        self.data = self.data[1:]
        
    def top(self):
        #le sommet de la file est au début du tableau
        t = self.data[0]
        super().top(t)
        return t
    
    def empty(self):
        super().empty()
        return len(self.data) == 0

En utilisant une file, la politique "first in first out" (FIFO) assure que les sommets sont traités par ordre de découverte, et qu'on traite intégralement tous les voisins d'un sommet avant de passer au suivant.

In [11]:
q = queue(G)
traverse(G, begin, q)
In [12]:
animate_graph(G, pts, q.animation)
Out[12]: