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.
# 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.
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.
# 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¶
# 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.
begin = leftmost(G, pts)
s = stack(G)
traverse(G, begin, s)
animate_graph(G, pts, s.animation)
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.
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)
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¶
#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.
q = queue(G)
traverse(G, begin, q)
animate_graph(G, pts, q.animation)