networkx¶
Par Deni Gahlinger 1
Introduction¶
NetworkX est une bibiothèque Python qui permet d’instancier des graphes composés de nœuds et de ponts, ou liens. Grâce à cette bibliothèque, la manipulation de ces graphes est simplifiée
Un graphe, c’est un ensemble d’objet ou nœud pouvant être reliés par des ponts. Il existe plusieurs opérations et calculs sur les graphes. les graphes que NetworkX permet d’instancier peuvent contenir comme nœud nimporte quel objet hashable.
Nous allons donc voir premièrement un exemple d’instanciation de noeuds, ensuite découvrire les différentes sortes de graphes ainsi que les opérations sur elles, et finalement comprendre les différents types d’affichages de graphes.
Instanciation¶
Voici un exemple d’instanciation d’un graphe simple avec NetworkX. Comme NetworkX prend nimporte quel objet hashable comme noeud, l’exemple prendra des int.
"""Exemple d'instanciation d'un graphe avec NetworkX."""
import networkx as nwx
# création du graphe vide avec un attribu (laisser les parenthèses vides
# si on ne veut psa d'attributs)
G = nwx.Graph(day="Friday")
G.graph['day'] = 'Monday'
G.add_node(1, time='5pm') # ajout d'un noeud avec un attribu de temps (5pm)
G.add_nodes_from([2, 3]) # ajout de plusieurs noeuds
Ns = nwx.path_graph(10) # création d'un groupe de noeud
G.add_nodes_from(Ns) # ajour de chaque noeud dans le graphe
Ng = nwx.path_graph(10)
G.add_node(Ng) # ajout de Ng comme un noeud de G.
G.add_edge(1, 2) # création d'un pont dans le graphe
e = (2, 3)
G.add_edge(*e) # ajout d'un pont déjà existant
G.add_edges_from([(1, 2), (1, 3)]) # ajout de plusieurs edges
G.remove_edge(1, 2)
# suppression du pont (1,2) on peut aussi supprimer des
# groupes de ponts et des noeuds de la même façon avec
# Graph.remove_node(), Graph.remove_nodes_from(),
# Graph.remove_edges_from()
G.clear() # supprime tout les noeuds et ponts du graphe
G.add_node([1, 2, 3])
G.add_edges_from([(1, 2), (1, 3)])
G.nodes() # affiche les noeuds
G.edges() # affiche les ponts
nwx.connected_components(G) # affiche les groupes de noeuds interconnectés
nwx.degree(G) # affiche les noeuds avec leurs nombre de connexions
nwx.degree(G).values() # affiche le nombre de connexion des noeuds
G.node[1] # affiche le noeud 1
# Directed graphs / graphes dirigés
# ces graphes permettent différences opérations supplémentaires comme :
# DiGraph.out_edges(), DiGraph.in_degree(), DiGraph.predecessors(),
# DiGraph.successors().
DG = nwx.DiGraph()
# ajout de ponts ayant différents poids
DG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)])
# Multigraph
# Les multigraph permettent d'avoir plusieurs ponts entre deux mêmes points.
MG = nwx.DiGraph()
# ajout de ponts ayant différents poids
MG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)])
# code pris sur :
# https://networkx.github.io/documentation/networkx-1.10/tutorial/tutorial.html
Opération sur des graphes¶
NetworkX permet différentes opérations sur les graphes. En voici un exemple :
"""Exemple d'opérations sur les graphes avec NetworkX."""
import NetworkX as nwx
G1 = nwx.Graph()
G1.add_nodes_from([1, 2, 3])
G2 = nwx.Graph()
G1.add_nodes_from([4, 5, 6])
# operations classiques sur les graphes :
# FIXME: nb = nwx.subgraph(G1, nbunch)
# induit un subgraphe de G en noeuds d'un nBrunch
G3 = nwx.union(G1, G2) # union de deux graphes
G3 = nwx.disjoint_union(G1, G2) # union sans doublure
G3 = nwx.cartesian_product(G1, G2) # produit cartésien
G3 = nwx.compose(G1, G2)
# combine les graphes en détectant les mêmes noeuds
G3 = nwx.complement(G1) # complements de G1
G3 = nwx.create_empty_copy(G1) # crée une copie vide de G1
G3 = nwx.convert_to_directed(G1) # convertis un graphe dirigé
G1 = nwx.convert_to_undirected(G3) # convertis un graphe dirigé
# création de graphe classique prédéfinis
K_5 = nwx.complete_graph(5)
K_3_5 = nwx.complete_bipartite_graph(3, 5)
barbell = nwx.barbell_graph(10, 10)
lollipop = nwx.lollipop_graph(10, 20)
# untilisation des générateurs de graphes stockastiques
er = nwx.erdos_renyi_graph(100, 0.15)
ws = nwx.watts_strogatz_graph(30, 3, 0.1)
ba = nwx.barabasi_albert_graph(100, 5)
red = nwx.random_lobster(100, 0.9, 0.9)
# enregistrement d'un graphe dans un fichier
nwx.write_gml(red, "path.to.file")
mygraph = nwx.read_gml("path.to.file")
# code pris sur :
# https://networkx.github.io/documentation/networkx-1.10/tutorial/tutorial.html
Dessin d’un graphe¶
NetworkX n’est pas fait spécialement pour dessiner un graphe.
"""Exemple de dessin d'un graphe de networkX."""
import matplotlib.pyplot as plt
import networkx as nwx
G1 = nwx.Graph()
G1.add_nodes_from([1, 2, 3])
# dessin avec Mathplotlib
nwx.draw(G1) # on peut aussi essayer avec :
# nx.draw_random(G), nx.draw_circular(G), nx.draw_spectral(G)
plt.show() # pour afficher ensuite
plt.savefig("path.png") # pour enregistrer sur un fichier dans un format png
# voir aussi : nx.draw_graphviz(G) et nx.write_dot(G,'file.dot') avec
# PyGraphviz ou pydot
# code pris sur :
# https://networkx.github.io/documentation/networkx-1.10/tutorial/tutorial.html
Conclusion¶
On peut voir que NetwokX est une librairie assez simple à utiliser dans les bases, mais est assez complète Cette librairie est vraiment utile pour différentes problématique touchant les graphes et la théories des graphes comme le voyageur de commerce. Certains problèmes mathématiques dans ce domaine peuvent avoir une grande complexité (complexité non polynomiale).
L’existance d’une librairie comme NetworkX permet de manipuler des graphes de façon simple et offre plusieurs options utile pour une utilisation assez large dans le domaine des graphes.