Appliquer la théorie des graphes avec NetworkX

La théorie des graphes est un aspect des mathématiques qui a beaucoup d’applications dans divers domaines. Que ce soit en biologie, en réseau informatique, en analyse de réseaux sociaux, la modélisation par la théorie des graphes s’avère très efficace. En règle générale, les problèmes qui mettent en scène des réseaux (ensemble d' »entités » entre lesquelles il existe des « liens ») peuvent être modélisés sous forme de graphes. Il est possible de manipuler des graphes avec NetworkX, qui est une bibliothèque Python.

Dans cet article, nous découvrirons, NetworkX. Mais avant de passer aux possibilités de NetworkX, il est important de rappeler des définitions basiques.

Qu’est-ce qu’un graphe

Graphe simple non-orienté

Un graphe (ou graphe simple non orienté) est un couple G = (V, E) comprenant :

V un ensemble de sommets (aussi appelés nœuds, points ou vertex) ;
E ⊆ ((x, y} | (x, y) ∈ V² ∧ x ≠ y} un ensemble d’arêtes (aussi appelées liens ou lignes), qui sont des paires de sommets (c.-à-d. qu’une arête est associée à deux sommets distincts).

Dans l’arête {x, y}, les sommets x et y sont appelés les extrémités ou les sommets extrêmes de l’arête.

Chaque boule (de A à G) est un noeud (sommet) et les liens sont représentés par les lignes droites.

Graphe orienté

Un graphe orienté est un couple G = (V, A) (parfois G = (V, E)) comprenant :

V un ensemble de sommets (aussi appelés nœuds ou points) ;
A ⊆ {(x, y) | (x, y) ∈ V² ∧ x ≠ y} un ensemble de flèches (aussi appelées arêtes orientées — parfois simplement arêtes avec l’ensemble correspondant nommé E au lieu de A —, liens orientés ou lignes orientées)

On voit bien que l’unique différence est le fait que les liens sont orientés. Le lien (A, B) est différent du lien (B, A) dans un graphe orienté.

Graphe étiqueté / Graphe pondéré

Un graphe étiqueté est un graphe (orienté ou non) dont les liens ont un nom (ou étiquette) qui peut être un symbole, une lettre, un chiffre, etc.

Un graphe pondéré etiqueté dont les etiquettes sont des valeurs numériques.

NetworkX

Installation de NetworkX

pip install NetworkX

Oui, c’est aussi simple que ça !

Les bases

On importe NetworkX afin de pouvoir tester les bouts de code qui suivent :

import networkx as nx

Créer un graphe

L’on peut créer un graphe avec NetworkX en utilisant une des classes suivantes :

nx.Graph : Pour les graphes non orientés.
nx.DiGraph : Pour les graphes orientés.
nx.MultiGraph : Qui est une classe plus flexible autorisant plusieurs liens entre différents noeuds.
nx.MultiDiGraph : Qui est la version orientée de nx.MutliGraph

G = nx.DiGraph() # Création d'un graphe orienté

Une fois l’objet Graph créé, il y faut ajouter des nœuds et liens. Toutes ces classes permettent de créer des nœuds avec tous les types hashables (int, str, tuple, etc) de Python.

G.add_edge('A', 'B') # Création d'un lien => Deux noeuds
G.add_edge('B', 'C') # Création d'un lien avec un noeud déjà existant
G.add_node('D') # Création d'un noeud qui n'a aucun lien
G.add_nodes_from(['E', 'F', 'G']) # Création de noeuds par lots
G.add_edges_from([('A', 'G'), ('G', 'B'), ('B', 'C'), ('C', 'E'), ('E', 'F'), ('D', 'F')]) # Création des liens par lots

# Il est possible d'ajouter des attributs à un noeud ou à un lien
G.add_edge('A', 'B', poids=6) # Ajout d'un attribut 'poids' de valeur 6 au lien A-B
G.add_node('A', color='blue')

# On a la possibilité de réinitialiser notre graphe en faisant :
G.clear()

Il existe d’autres façons de créer un graphe avec NetworkX. On peut :

Utiliser un générateur de graphe qui se base sur des algorithmes pour créer un graphe avec une topologie précise.
Importer un fichier (GraphML, pickle, etc) contenant un graphe existant.

On recrée notre graphe orienté pondéré vu tout à l’heure :

G.add_weighted_edges_from([('A', 'B', 6), ('B', 'C', 8), ('A', 'G', 1), ('G', 'B', 9), ('B', 'C', 8), ('C', 'E', 2), ('E', 'F', 7), ('D', 'F', 7)])

Lecture d’un graphe

Desiner un graphe

NetworkX permet de dessiner les graphes que l’on manipule grâce à un bon nombre de méthodes. Cependant, NetworkX n’a pas pour vocation d’être un outil de visualisation, il est donc recommandé d’utiliser des outils spécialisés (GraphViz, Gephi, etc) dans la visualisation de graphes quand on veut faire des visuels plus élaborés.

Une représentation visuelle de notre graphe avec NetworkX se ferait comme ça :

nx.draw_networkx(G)

Parser un graphe

Un graphe NetworkX est représenté sous forme de dictionnaire Python. Parser un graphe revient donc à parser un dictionnaire.

print(G['A']['B']['weight']) # Pour recuperer l'attribut 'weight' du lien A-B
# [Out] : 6

print(G['A']) # pour recuperer toutes les informations (les voisins) sur le noeud 'A'
# [Out] : {'B': {'weight': 6}, 'G': {'weight': 1}}

Pour parser l’ensemble du graphe (tous les nœuds) on peut utiliser la méthode : G.adjacency() ou G.adj.items().

for noeud, info in G.adj.items():
    for voisin, info_lien in info.items(): 
        print(f"Le lien entre {noeud} et {voisin} a pour poids {info_lien['weight']}")

# [Out] :
# Le lien entre A et B a pour poids 6
# Le lien entre A et G a pour poids 1
# Le lien entre B et C a pour poids 8
# Le lien entre C et E a pour poids 2
# Le lien entre G et B a pour poids 9
# Le lien entre E et F a pour poids 7
# Le lien entre D et F a pour poids 7

Conclusion

Nous venons de voir comment traiter des données sous forme de graphes avec la bibliothèque Python NetworkX. La théorie des graphes est un domaine très vaste. Cet article ne fait qu’une introduction succincte de la bibliothèque NetworkX et pas de la théorie des graphes. Il y a encore beaucoup de fonctionnalités intéressantes que nous n’avons pas vue telles que les algorithmes pour les graphes. Cela fera sûrement, l’objet d’un autre article.

N’hésitez pas à laisser des commentaires. À bientôt !