Tuto Python & SciPy : réaliser des graphes
Rédigé par Imane BENHMIDOU, Publié le 24 Octobre 2020, Mise à jour le Jeudi, 03 Décembre 2020 22:08
Table des matières
3.1. Algorithmes de parcours d’un graphe
3.1.1. Algorithme de parcours en largeur (BFS : Breadth First Search)
3.1.2. Algorithme de parcours en profondeur (DFS : Depth First Search)
3.2. Algorithmes du plus court chemin
3.2.2. Algorithme de Floyd – Warshall
3.2.3. Algorithme de Bellman - Ford
Introduction
La librairie SciPy qui permet le calcul scientifique est composée de plusieurs sous-modules permettant différentes opérations comme les opérations d’optimisation, d’algèbre linéaire, d’interpolation, etc.
Nous prêterons attention en particulier au sous-module CSGraph qui est l’acronyme de Compressed Sparse Graph et qui comprend des opérations permettant de travailler avec des graphes et dont les algorithmes se basent sur des représentations matricielles éparses.
La création de ce sous-module a été motivée par plusieurs algorithmes utilisés dans scikit-learn.
1. Définitions
Tout d’abord un graphe est un couple G = (V, E), où V est l’ensemble des sommets appelés également nœuds ou points et E est l’ensemble des arêtes appelées aussi liens ou lignes et qui sont des paires de sommets, i.e. une arête est liée à deux sommets distincts.
Un graphe creux (sparse graph) quant à lui est un graphe contenant peu d’arêtes.
2. Représentations de graphe
Le sous-module CSGraph utilise les graphes représentés dans des matrices éparses.
Un graphe de N nœuds peut être représenté par une matrice de N lignes et N colonnes.
- Si i et j sont deux nœuds du graphe alors G [i, j] = w, avec w le poids de l’arête qui lie entre ces deux nœuds.
- Si i et j deux nœuds du graphe et qui ne sont pas liés, alors leur valeur dans la matrice dépend de la représentation :
- Pour les représentations de matrices denses G [i, j] = 0, l’infini ou NaN.
- Pour les représentations denses masquées (i.e. np.ma.MaskedArray) G [i, j] = valeur masquée.
- Pour les représentations de matrices éparses G [i, j] = non-entrée.
Exemple 1 :
Le graphe ci-dessous contient 3 nœuds.
Où : G [2,3] = 1 et G [2,4] = 2
Afin de représenter ce graphe on peut procéder selon les trois représentations précédemment citées, on obtient alors :
- Code :
import numpy as np
from scipy.sparse import csr_matrix
#représentation numéro 1
G_dense = np.array([[0, 1, 2],
[1, 0, 0],
[2, 0, 0]])
print(G_dense)
#représentation numéro 2
G_masque = np.ma.masked_values(G_dense, 0)
print(G_masque)
#représentation numéro 3
G_eparse = csr_matrix(G_dense)
print(G_eparse)
- Résultat de l’exécution :
Le code précédent engendrera des erreurs si on a dans le graphe un poids nul. Alors pour remédier à cela on peut faire appel à la routine utilitaire csgraph_from_dense du sous-module CSGraph qui permet de convertir une représentation dense en une représentation éparse pouvant être comprise par les algorithmes du sous-module.
Exemple 2 :
Le graphe ci-dessous contient 3 nœuds.
Où : G [2,3] = 1 et G [2,4] = 0
- Code :
from scipy.sparse.csgraph import csgraph_from_dense
#représentation numéro 1
G_dense = np.array([[np.inf, 1, 0],
[1, np.inf, np.inf],
[0, np.inf, np.inf]])
print(G_dense)
#représentation numéro 2
G_masque = np.ma.masked_invalid(G_dense)
print(G_masque)
#représentation numéro 3
G_sparse = csgraph_from_dense(G_dense, null_value=np.inf)
print(G_sparse)
- Résultat de l’exécution :
Le tableau ci-dessous regroupe quelques routines utilitaires du sous-module CSGraph.
|
FONCTION |
DESCRIPTION |
|
Construit un graphe de format CSR (Compressed Sparse Row) à partir d’une matrice dense. |
|
|
Construit un graphe de format CSR (Compressed Sparse Row) à partir d’une matrice masquée. |
|
|
Construit une représentation du graphe en une matrice masqué à partir d’une matrice dense. |
|
|
Converti une représentation éparse en une représentation dense. |
|
|
Converti une représentation éparse en une représentation masquée. |
3. Algorithmes de la théorie des graphes
3.1. Algorithmes de parcours d’un graphe
3.1.1. Algorithme de parcours en largeur (BFS : Breadth First Search)
La fonction breadth_first_tree permet de parcourir un graphe selon l’algorithme de parcours en largeur.
Exemple 3 :
Appliquons l’algorithme de parcours en largeur sur le graphe suivant :
- Code :
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import breadth_first_tree
G = [[0, 1, 2, 0, 0],
[0, 0, 0, 2, 2],
[0, 3, 0, 2, 0],
[0, 0, 0, 0, 4],
[0, 0, 0, 0, 0]]
G_eparse = csr_matrix(G)
p = breadth_first_tree ( G_eparse, 0, directed = True)
p.toarray().astype(int)
- Résultat de l’exécution :
3.1.2. Algorithme de parcours en profondeur (DFS : Depth First Search)
La fonction depth_first_tree permet de parcourir un graphe selon l’algorithme de parcours en profondeur.
Exemple 4 :
- Code :
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import depth_first_tree
G = [[0, 1, 2, 0, 0],
[0, 0, 0, 2, 2],
[0, 3, 0, 2, 0],
[0, 0, 0, 0, 4],
[0, 0, 0, 0, 0]]
G_eparse = csr_matrix(G)
d = depth_first_tree ( G_eparse, 0, directed = True)
d.toarray().astype(int)
- Résultat de l’exécution :
3.2. Algorithmes du plus court chemin
3.2.1. Algorithme de Dijkstra
On peut faire appel à la fonction dijkstra du sous-module CSGraph pour appliquer l’algorithme de Dijkstra qui sert à résoudre le problème du plus court chemin dans un graphe orienté pondéré par des réels positifs.
La fonction dijkstra retourne :
- dist_matrix qui est la matrice des distances entre les nœuds du graphe.
- predecessors qui est la matrice des prédécesseurs.
Exemple 5 :
Considérons le graphe ci-après :
On lui applique l’algorithme de Dijkstra.
- Code :
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
G = [[0, 1, 2, 0, 0],
[0, 0, 0, 2, 2],
[0, 3, 0, 2, 0],
[0, 0, 0, 0, 4],
[0, 0, 0, 0, 0]]
G_eparse = csr_matrix(G)
dist_matrix, predecessors = dijkstra (csgraph = G_eparse, directed = True,
return_predecessors = True)
print(dist_matrix)
print(predecessors)
- Résultat de l’exécution :
Remarque :
Dans la matrice des prédécesseurs on retrouve dans certains cas [i, j] = -9999, par défaut ce nombre est affiché lorsqu’il n’existe pas de lien entre un nœud i et un nœud j. Dans le cas contraire elle nous donner l’indice du nœud précédent dans le chemin du point i au point j.
3.2.2. Algorithme de Floyd – Warshall
La fonction floyd_warshall permet de calculer les distances des plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré selon l’algorithme Floyd - Warshall.
La fonction floyd_warshall retourne :
- dist_matrix qui est la matrice des distances entre les nœuds du graphe.
- predecessors qui est la matrice des prédécesseurs.
Exemple 6 :
On reprend le graphe de l’exemple précédent et on applique dessus l’algorithme de Floy - Warshall.
- Code :
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
G = [[0, 1, 2, 0, 0],
[0, 0, 0, 2, 2],
[0, 3, 0, 2, 0],
[0, 0, 0, 0, 4],
[0, 0, 0, 0, 0]]
G_eparse = csr_matrix(G)
dist_matrix, predecessors = floyd_warshall ( csgraph = G_eparse, directed = True,
return_predecessors = True )
print(dist_matrix)
print(predecessors)
- Résultat de l’exécution :
3.2.3. Algorithme de Bellman - Ford
La fonction bellman_ford permet de calculer les plus courts chemins depuis un sommet source donné dans un graphe orienté et pondéré selon l’algorithme Bellman - Ford. Et contrairement à l’algorithme de Dijkstra, celui-ci autorise les poids négatifs.
La fonction bellman_ford retourne :
- dist_matrix qui est la matrice des distances entre les nœuds du graphe.
- predecessors qui est la matrice des prédécesseurs.
Exemple 7 :
Considérons le graphe suivant dans lequel on va appliquer l’algorithme de Bellman - Ford :
- Code :
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
G = [ [0, -1, 2, 0, 0],
[0, 0, 0, 2, 2],
[0, 3, 0, -2, 0],
[0, 0, 0, 0, -4],
[0, 0, 0, 0, 0] ]
G_eparse = csr_matrix(G)
dist_matrix, predecessors = bellman_ford (csgraph = G_eparse, directed = True,
return_predecessors = True)
print(dist_matrix)
print(predecessors)
- Résultat de l’exécution :
3.2.4. Algorithme de Johnson
La fonction johnson permet de calculer les plus courts chemins entre toutes les paires de sommets dans un graphe orienté aux arcs pondérés en utilisant l’algorithme de Johnson.
La fonction johnson retourne :
- dist_matrix qui est la matrice des distances entre les nœuds du graphe.
- predecessors qui est la matrice des prédécesseurs.
Exemple 8 :
Reprenons le graphe de l’exemple précédent en lui appliquant cette fois-ci l’algorithme de Johnson.
- Code :
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import johnson
G = [[0, -1, 2, 0, 0],
[0, 0, 0, 2, 2],
[0, 3, 0, -2, 0],
[0, 0, 0, 0, -4],
[0, 0, 0, 0, 0]]
G_eparse = csr_matrix(G)
dist_matrix, predecessors = johnson (csgraph = G_eparse, directed = True,
return_predecessors = True)
print(dist_matrix)
print(predecessors)
- Résultat de l’exécution :
Conclusion
Dans ce tutoriel nous avons eu l’occasion de parcourir différents éléments du sous module CSGraph de la bibliothèque Scipy et qui permet de manipuler les graphes. À savoir comment présenter un graphe en utilisant les différentes représentations, l'utilisation des algorithmes de théorie des graphes pour parcourir un graphe soit en largeur ou en profondeur ainsi que les algorithmes de calcul du plus court chemin.