Table of Contents
- 1 Premier exemple
- 2 Deuxième exemple
- 3 Création d'un graphe à partir d'une matrice d'adjacence
- 4 Exercice tiré d'un ancien bac
- 5 Quelques éléments sur les matrices
- 6 Algorithme de Dijkstra
- 7 Exemple d'un graphe complet
- 8 Simulation à l'aide d'une matrice d'adjacence: simulation d'un réseau social
- 9 Un graphe en modifiant la largeur des arêtes en fonction du poids
- 10 Un graphe avec indication des poids sur les arêtes
In [2]:
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
In [2]:
# Pour voir le contenu de la bibliothèque
# import networkx
# dir(networkx)
In [4]:
# pour avoir de l'aide sur la commande is_connected par exemple
# help(networkx.is_connected)
Premier exemple
In [5]:
# déclaration d'un graphe dans la variable g
g=nx.Graph() # Graph, non orienté. Digraph, orienté.
# déclare que le graphe de g contient 5 sommets
g.add_nodes_from(range(5))
# définit les arêtes entre les sommets, par exemple (4,5) déclare une arête entre le sommet 4 et 5
# si on rajoute dans la liste des sommets non déclarés ils sont ajoutés ici on a ajouté le sommet 5
g.add_edges_from([(0,1),(3,4),(4,2),(1,3),(4,0),(1,2),(1,5)])
plt.figure()
nx.draw(g)
plt.show()
Deuxième exemple
In [4]:
g = nx.newman_watts_strogatz_graph(100, 15, 0.35, seed = 12345 )
plt.figure()
nx.draw(g)
plt.show()
Création d'un graphe à partir d'une matrice d'adjacence
In [10]:
# déclaration de la matrice M
M = np.array([[0,0,1,1],
[1,1,0,0],
[0,1,0,1],
[1,0,1,0]])
# affichage de la matrice
print(M)
In [11]:
# affichage du graphe associé à la matrice d'ajacence M
plt.figure()
nx.draw(nx.DiGraph(M))
plt.show()
In [12]:
options = {
'node_color' : 'yellow', # couleur des sommets
'node_size' : 550, # taille des sommets
'edge_color' : 'tab:blue', # couleur des arêtes
'with_labels': True # affiche l'étiquette des sommets
}
#DiGraph permet de faire des graphes orienté
G = nx.DiGraph(M)
plt.figure()
nx.draw(G, **options)
#**options fait référence à la variable options contenant toutes les informations de mise en page du graphe
plt.show()
Exercice tiré d'un ancien bac
Une agence de tourisme propose la visite de certains monuments parisiens.
Chacun de ces monuments est désigné par une lettre comme suit :
E : Tour Eiffel
L : Musée du Louvre
M : Tour Montparnasse
N : Cathédrale Notre-Dame de Paris
S : Basilique du Sacré-Cœur de Montmartre
T : Arc de triomphe
Cette agence fait appel à une société de transport par autocar qui propose les liaisons suivantes (chacune de ces liaisons pouvant s’effectuer dans les deux sens de circulation) :
In [20]:
g=nx.Graph()
# on définit les arêtes du graph en respectant les donnés de l'énoncé
g.add_edges_from([('S','T'),('S','E'),('S','N'),('T','E'),('E','L'),('E','M'),('L','N'),('M','N'),('L','M'),('L','S')])
options = {
'node_color' : 'yellow',
'node_size' : 550,
'edge_color' : 'tab:grey',
'with_labels': True
}
plt.figure()
nx.draw(g, **options)
plt.show()
In [14]:
# Recherche des degrés des sommets
# La liste des degrés est un dictionnaire.
ListeDegres={}
for x in g.nodes() :
ListeDegres[x]=g.degree(x)
In [15]:
ListeDegres
Out[15]:
In [16]:
# Graphes Eulériens
nx.is_eulerian(g)
nx
Out[16]:
Il n'existe pas de parcours eulérien dans un graphe non Eulérien d'implanté dans networkx, il faut le programmer soit même. Un site intéressant qui cherche ce parcours avec l'algorithme de Fleury.
https://repl.it/@PascalTherese/Fleurys-Algorithm
Pour les courageux, on peut aussi l'implanter.
Quelques éléments sur les matrices
In [15]:
# Créer la matrice d'adjacence
adjacence = np.array([[0,1,1,0,1,1],
[1,0,1,1,1,0],
[1,1,0,1,0,0],
[0,1,1,0,1,0],
[1,1,0,1,0,1],
[1,0,0,0,1,0]])
In [16]:
print(adjacence)
In [17]:
# pour calculer le produit
AdjaCarre=np.dot(adjacence,adjacence)
In [18]:
AdjCube=np.dot(AdjaCarre,adjacence)
In [19]:
AdjCube
Out[19]:
In [ ]:
In [24]:
# Créer la matrice d'adjacence pour qu'elle tienne compte des poids
inf = float("inf") # on utilisera inf pour symboliser l'absence d'arcs
adjacencePoids = np.array([[inf,8,10,inf,10,4],
[8,inf,7,2,5,inf],
[10,7,inf,1,inf,inf],
[inf,2,4,inf,8,inf],
[10,5,inf,8,inf,8],
[4,inf,inf,inf,8,inf]])
print(adjacencePoids)
Algorithme de Dijkstra
In [17]:
g=nx.Graph()
#('S','T',{'weight':8}) permet de définir une arête entre les sommets S et T avec une pondération de 8
g.add_edges_from([('S','T',{'weight':8}),('S','E',{'weight':10}),('S','N',
{'weight':8}),('T','E',{'weight':4}),('E','L',{'weight':8}),
('E','M',{'weight':10}),('L','N',{'weight':2}),('M','N',
{'weight':4}),('L','M',{'weight':7}),('L','S',{'weight':5})])
options = {
'node_color' : 'yellow',
'node_size' : 550,
'edge_color' : 'tab:grey',
'with_labels': True
}
plt.figure()
nx.draw(g, **options)
plt.show()
In [18]:
nx.dijkstra_path_length(g,'M','S')
Out[18]:
Exemple d'un graphe complet
recherche d'un circuit Eulérien.In [19]:
g=nx.complete_graph(5)
plt.figure()
nx.draw(g)
plt.show()
nx.is_eulerian(g)
list(nx.eulerian_circuit(g))
Out[19]:
In [ ]:
Simulation à l'aide d'une matrice d'adjacence: simulation d'un réseau social
- Le problème de notre simulation est que les interactions sont de l'odre une chance sur deux.
- Il faudrait une activité en classe réelle avec les élèves pour comparer les matrices d'adjacence.
- Dans networkx, il y a des méthodes de simulation de réseaux aléatoires. Exemple aves la méthode Barabasi.
In [22]:
# première méthode
n=10
adj= np.around(np.random.rand(n,n))
In [23]:
# deuxième méthode
matrix2=np.random.randint(2,size=(n,n))
In [23]:
print(adj)
In [24]:
print(matrix2)
In [ ]:
In [25]:
graph = nx.DiGraph(adj)
options = {
'node_color' : 'yellow',
'node_size' : 550,
'edge_color' : 'tab:grey',
'with_labels': True
}
plt.figure()
nx.draw(graph, **options)
plt.show()
In [21]:
# Dans networkx, il y a des méthodes de simulation de réseaux aléatoires. Exemple aves la méthode Barabasi.
node_number = 10
initial_nodes = 2
G = nx.barabasi_albert_graph(node_number, initial_nodes)
options = {
'node_color' : 'yellow',
'node_size' : 550,
'edge_color' : 'tab:grey',
'with_labels': True
}
plt.figure()
nx.draw(G, **options)
plt.show()
Lien très intéressant :
Les outils de networkx pour l'anayse des graphes :
- g.degree() : degrés des sommets du graphe g
- g.number_of_nodes() : nombre de sommets du graphe g
- g.number_of_edges() : nombre d’arcs du graphe g
- g.predecessors(i) : liste des prédecesseurs du sommet i, le graphe doit être orienté, à utiliser avec list()
- g.successors(i) : liste des successeurs du sommet i, le graphe doit être orienté, à utiliser avec list()
- g.neighbors(i) : liste des voisins du sommet i, le graphe doit être orienté à utiliser avec list()
On dispose aussi des indicateurs et outils suivants (liste non exhaustive) :
- density(g) : densité du graphe g
- diameter(g) : diamètre du graphe g
- shortest_path(g) : plus courts chemins entre tous les couples de sommets de g
- pagerank(g) : calcul du pagerank
- center(g) : centre
- periphery(g) : périphérie
- eccentricity(G)
In [60]:
print(G.degree())
print(G.number_of_nodes())
print(G.number_of_edges())
# pour les successeurs, prédecesseurs, utilisatin d'ungraphe orienté .
print(list(graph.predecessors(2)))
print(list(graph.successors(2)))
print(list(graph.neighbors(2)))
In [46]:
print(nx.density(G))
print(nx.diameter(G))
print(nx.shortest_path(G))
print(nx.pagerank(G))
print(nx.center(G))
print(nx.periphery(G))
Un graphe en modifiant la largeur des arêtes en fonction du poids
In [3]:
import networkx as nx
G = nx.DiGraph()
G.add_edge(1,2,color='r',weight=2)
G.add_edge(2,3,color='b',weight=4)
G.add_edge(3,4,color='g',weight=6)
#pour positionner les sommets de manière circulaire
pos = nx.circular_layout(G)
#pour créer la liste des arêtes
edges = G.edges()
print(edges)
#pour créer la liste des couleurs des arêtes
colors = [G[u][v]['color'] for u,v in edges]
#pour créer la liste des poids qui donneront la largeur des arêtes
weights = [G[u][v]['weight'] for u,v in edges]
options = {
'node_color' : 'yellow',
'node_size' : 550,
'edge_color' : 'tab:grey',
'with_labels': True
}
#nx.Draw{G,**options}
nx.draw(G,pos, node_color='yellow',with_labels=True,edges=edges, edge_color=colors, width=weights)
Un graphe avec indication des poids sur les arêtes
In [71]:
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import pylab
G = nx.DiGraph()
G.add_edges_from([('A', 'B'),('C','D'),('G','D')], weight=1)
G.add_edges_from([('D','A'),('D','E'),('B','D'),('D','E')], weight=2)
G.add_edges_from([('B','C'),('E','F')], weight=3)
G.add_edges_from([('C','F')], weight=4)
val_map = {'A': 1.0,
'D': 0.5714285714285714,
'H': 0.0}
values = [val_map.get(node, 0.45) for node in G.nodes()]
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in G.edges(data=True)])
red_edges = [('C','D'),('D','A')]
edge_colors = ['black' if not edge in red_edges else 'red' for edge in G.edges()]
pos=nx.circular_layout(G)
#commande pour faire des arêtes avec indication de poids
# commande qui utilise pylab
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
#commande pour tracer le graphe
nx.draw(G,pos, node_color = values,with_labels=True, node_size=1500,edge_color=edge_colors,edge_cmap=plt.cm.Reds)
pylab.show()
In [6]:
import networkx
dir(networkx)
Out[6]:
In [ ]:
In [ ]:
In [ ]: