Théorie des graphes : la bibliothèque $\mathtt{NetworkX}$

Retour au tutoriel général

La bibliothèque $\mathtt{NetworkX}$ permet de travailler avec des graphes. Une brève présentation est disponible à l'adresse https://networkx.org/documentation/stable/

Une présentation plus détaillée des fonctionnalités est disponible à l'adresse https://networkx.org/documentation/stable/reference/index.html

Définition et tracé des graphes

• Il existe plusieurs façons de construire un graphe. On peut le construire en ajoutant les sommets et arêtes.

import networkx as nx
import matplotlib.pyplot as plt

# On crée un graphe vide
G= nx.Graph()

# On ajoute les sommets
G.add_node(1)            # un sommet
G.add_nodes_from([2,3])  # une liste de sommets


G.add_edge(1,2)                  # une arête
G.add_edges_from([(1,3),(2,1)])   # une liste d'arêtes
                 
# Si on ajoute une arete avec un sommet inconnu celui-ci sera automatiquement créé
G.add_edge(1,4)

nx.draw(G, with_labels=True)  # Tracé du graphe
plt.show()

Les mêmes fonctions existent en remplaçant $\mathtt{add}$ par $\mathtt{remove}$.

Pour le tracé, on peut spécifier la position des sommets soit par un calcul automatique (la liste des positionnement est disponible à l'adresse https://networkx.org/documentation/stable/reference/drawing.html#module-networkx.drawing.layout)

position = nx.circular_layout(G)
nx.draw(G, with_labels=True, pos=position)
plt.show()

ou en spécifiant manuellement les positions par un dictionnaire sommet / position

position = {1 : [0,0], 2:[-1,1], 3:[1,1], 4:[0,1.5]}
nx.draw(G, with_labels=True, pos=position)
plt.show()

On peut aussi construire un graphe à partir d'un dictionnaire : les clés sont les sommets, les valeurs sont la liste des sommets pointés par la clé.

import networkx as nx
import matplotlib.pyplot as plt

d = {0:[1],1:[0,2],2:[0]}
G = nx.Graph(d)

nx.draw(G, with_labels=True)
plt.show()

On peut aussi construire un graphe à partir de sa matrice d'adjacence.

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

M = np.array([[0,1,0],[1,1,0],[0,0,0]])
G = nx.Graph(M)

nx.draw(G, with_labels=True)
plt.show()

Si besoin, on peut renommer les noeuds (notamment si on utilise la définition via la matrice d'adjacence). Pour cela on utilise la méthode $\mathtt{relabel\_nodes}$. Les noeuds sont renommés en utilisant un dictionnaire dont les clés sont les anciens noeuds et les valeurs les nouveaux noeuds.

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

M = np.array([[0,1,0],[0,0,1],[1,0,0]])
G = nx.Graph(M)

nouveaux_noms = {0:'A', 1:'B', 2:'C'}
G = nx.relabel_nodes(G, nouveaux_noms)

nx.draw(G, with_labels=True)
plt.show()

 Graphes orientés

• La construction d'un graphe orienté est identique (arête par arête via un dictionnaire ou via la matrice d'adjacence) en remplaçant le constructeur $\mathtt{Graph}$ par $\mathtt{DiGraph}$.

import networkx as nx
import matplotlib.pyplot as plt

d = {0:[1],1:[0,2],2:[0]}
G = nx.DiGraph(d)

nx.draw(G, with_labels=True)
plt.show()

 Graphes valués

• De la même façon que pour la construction d'un graphe, pour un graphe valué il y a plusieurs façons d'indiquer les poids des arêtes.

import networkx as nx
import matplotlib.pyplot as plt

G=nx.DiGraph()

# Graphe valué arête par arête
G.add_edge(1,2,weight=0.5)
G.add_edges_from([(1, 3, {'weight' : 0.9}), (2, 3, {'weight' : 0.3})])

pos = nx.spring_layout(G)
nx.draw(G,with_labels=True,pos=pos)

labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)
plt.show()

Attention, pour la définition via un dictionnaire on utilise ici un dictionnaire de dictionnaires pour indiquer les valuations

import networkx as nx
import matplotlib.pyplot as plt

# Graphe pondéré via un dictionnaire de dictionnaires
d = {1:{2:{'weight':0.5}, 3:{'weight':0.9}}, 2:{3:{'weight':0.3}}}
G = nx.DiGraph(d)

pos = nx.spring_layout(G)
nx.draw(G,with_labels=True,pos=pos)

labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)
plt.show()

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

# Graphe pondéré via la matrice d'adjacence
M = np.array([[0,0.5,0.9],[0,0,0.3],[0,0,0]])
G = nx.DiGraph(M)

pos = nx.spring_layout(G)
nx.draw(G,with_labels=True,pos=pos)

labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)
plt.show()

Pour récupérer les poids (sous forme de dictionnaire) on utilise la fonction $\mathtt{get\_edge\_attributes}$ (déjà utilisée pour l'affichage)

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

# Graphe pondéré via la matrice d'adjacence
M = np.array([[0,0.5,0.9],[0,0,0.3],[0,0,0]])
G = nx.DiGraph(M)
P = nx.get_edge_attributes(G,'weight')
print("Dictionnaire des poids : ", P)

# Parcours des arêtes et affichage des poids
for a in G.edges:
    print("Poids de l'arête", a, ':',P[a])

Dictionnaire des poids :  {(0, 1): 0.5, (0, 2): 0.9, (1, 2): 0.3}
Poids de l'arête (0, 1) : 0.5
Poids de l'arête (0, 2) : 0.9
Poids de l'arête (1, 2) : 0.3

Propriétés des graphes

• Il existe de nombreuses fonctions pour récupérer les différentes propriétés d'un graphe.

import networkx as nx
import matplotlib.pyplot as plt

d = {0:[1],1:[0,2],2:[0]}
G = nx.DiGraph(d)

nx.draw(G, with_labels=True)
plt.show()

print("Nombre de noeuds = ", G.number_of_nodes())
print("Nombre d'aretes = ", G.number_of_edges())
print("Diamètre =", nx.diameter(G))

print("Liste des sommets : ", G.nodes)
print("Liste des arêtes : ", G.edges)
print("Liste des voisins d\'un sommet donné : ", list(G.adj[0]))

print("Matrice d\'adjacence : \n", nx.to_numpy_array(G))    # au format array de NumPy
print("Convertir au format dictionnaire : \n", nx.to_dict_of_lists(G))    

Nombre de noeuds =  3
Nombre d'aretes =  4
Diamètre = 2
Liste des sommets :  [0, 1, 2]
Liste des arêtes :  [(0, 1), (1, 0), (1, 2), (2, 0)]
Liste des voisins d'un sommet donné :  [1]
Matrice d'adjacence : 
 [[0. 1. 0.]
 [1. 0. 1.]
 [1. 0. 0.]]
Convertir au format dictionnaire : 
 {0: [1], 1: [0, 2], 2: [0]}

d = {0:[1],1:[2,0],2:[0,3]}
G = nx.Graph(d)

nx.draw(G, with_labels=True)
plt.show()

print("Dictionnaire des degrés : ", dict(G.degree()))

Dictionnaire des degrés :  {0: 2, 1: 2, 2: 3, 3: 1}

Exemple de boucle sur les sommets

for s in G.nodes():
    print("Liste des voisins du sommet ",s, " : ", list(G[s]))

Liste des voisins du sommet  0  :  [1, 2]
Liste des voisins du sommet  1  :  [0, 2]
Liste des voisins du sommet  2  :  [1, 0, 3]
Liste des voisins du sommet  3  :  [2]

Quelques algorithmes

De nombreux algorithmes sont implémentés pour l'étude des graphes dans la bibliothèque $\texttt{NetworkX}$ : https://networkx.org/documentation/stable/reference/algorithms/index.html

On présente ici simplement les fonctions de parcours en largeur (et en profondeur) ainsi que la recherche de plus court chemin.

• Les parcours en profondeur (Depth-First Search) et en largeur (Breadth-First Search) sont implémentées dans la bibliothèque $\mathtt{NetworkX}$

import networkx as nx
import matplotlib.pyplot as plt

d = {0:[1,2],1:[3,4],3:[5],4:[6]}
G = nx.DiGraph(d)
print("Graphe G : \n")
plt.figure(1)
nx.draw(G, with_labels=True,pos=nx.spring_layout(G))
plt.show()

Graphe G : 

parcours_prof = nx.dfs_tree(G, source=1)

print("Liste du parcours en profondeur : \n")
print(list(parcours_prof.edges()))

print("Arbre du parcours en profondeur : \n")
plt.figure(2)
nx.draw(parcours_prof, with_labels=True)

Liste du parcours en profondeur : 

[(1, 3), (1, 4), (3, 5), (4, 6)]
Arbre du parcours en profondeur : 

import networkx as nx
import matplotlib.pyplot as plt

d = {0:[1,2],1:[3,4],3:[5],4:[6]}
G = nx.DiGraph(d)
print("Graphe G : \n")
plt.figure(1)
nx.draw(G, with_labels=True,pos=nx.spring_layout(G))
plt.show()

Graphe G : 

parcours_larg = nx.bfs_tree(G, source=1) 

print("Liste du parcours en largeur : \n")
print(list(parcours_larg.edges()))

print("Arbre du parcours en largeur : \n")
plt.figure(2)
nx.draw(parcours_larg, with_labels=True)

Liste du parcours en largeur : 

[(1, 3), (1, 4), (3, 5), (4, 6)]
Arbre du parcours en largeur : 

• Le calcul de plus court chemin se fait avec la fonction $\mathtt{shortest\_path}$. Les différents options (choix de l'algorithme, format renvoyé etc...) sont disponibles à l'adresse https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html

Cas d'un graphe non orienté

import networkx as nx
import matplotlib.pyplot as plt

d = {0:[1,2],1:[3,4],2:[3],3:[5],4:[6]}
G = nx.Graph(d)
print("Graphe G : \n")

nx.draw(G, with_labels=True,pos=nx.spring_layout(G))
plt.show()

print(nx.shortest_path(G, source=2, target=4))

Graphe G : 

[2, 0, 1, 4]

Cas d'un graphe valué

import networkx as nx
import matplotlib.pyplot as plt

d = {0:{1:{'weight':2}, 2:{'weight':4}},
     1:{3:{'weight':1}, 4:{'weight':6}},
     2:{3:{'weight':3}},
     3:{4:{'weight':1}, 5:{'weight':2}},
     4:{6:{'weight':5}}
    }

G = nx.DiGraph(d)
print("Graphe G : \n")

pos=nx.circular_layout(G)
nx.draw(G, with_labels=True,pos=pos)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)
plt.show()

print("Plus court chemin de 0 à 4 : ",nx.shortest_path(G, source=0, target=4))

Graphe G : 

Plus court chemin de 0 à 4 :  [0, 1, 4]

Quelques commentaires supplémentaires pour la visualisation

• Attention si la bibliothèque $\mathtt{NetworkX}$ est très utilisée pour travailler avec des graphes, la partie "visualisation" n'est pas très développée (et risque d'être abandonnée). Un point important souligné dans l'exemple ci-dessous est qu'elle n'affiche pas les boucles (en tous cas je n'y arrive pas...)

import networkx as nx
import matplotlib.pyplot as plt

# On crée un graphe vide
G= nx.Graph()

G.add_edge(1,1)                  

nx.draw(G, with_labels=True)
plt.show()

A des fins de visualisation on pourra préférér l'utilisation de $\mathtt{PyGraphviz}$. Cette bibliothèque repose sur Graphivz (sudo apt-get install graphviz) et doit être installée (pip install pygraphviz). Pour ne surcharger ce tutoriel, le reste des graphes sera affiché avec la fonction $\mathtt{draw}$ de $\mathtt{NetworkX}$.

import networkx as nx
import matplotlib.pyplot as plt
from IPython.display import Image

d = {0:[0],1:[0,2],2:[0]}
G = nx.DiGraph(d)
G.add_node(4,style='filled',fillcolor= "#%02x%02x%02x" % (120, 100, 180))   #RGB converti en hexRGB
G.add_edge(2,4, arrowsize=2.0,penwidth=2.0)


G.graph['graph'] = {'scale': '1'}   
G.graph['node']={'shape':'circle'}
G.graph['edges']={'arrowsize':'4.0'}

A = nx.nx_agraph.to_agraph(G)
A.layout('dot')

# Enregistrer l'image du graphe 
A.draw('networkx_graph.png')

# ou l'afficher directement dans un terminal IPython
Image(A.draw(format='png'))

Pour afficher les poids d'un graphe pondéré on ajoute l'attribut $\mathtt{label}$

import networkx as nx
import matplotlib.pyplot as plt
from IPython.display import Image

G=nx.DiGraph()

# Graphe pondéré arête par arête
G.add_edge(1,2,weight=0.5)
G.add_edges_from([(1, 3, {'weight' : 0.9}), (2, 3, {'weight' : 0.3})])

pos = nx.spring_layout(G)

for e in G.edges:
    G[e[0]][e[1]]['label']= G[e[0]][e[1]]['weight']

A = nx.nx_agraph.to_agraph(G)
A.layout('dot')

# Enregistrer l'image du graphe 
A.draw('networkx_weighted_graph.png')

# ou l'afficher directement dans un terminal IPython
Image(A.draw(format='png'))