In [1]:
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
In [17]:
# Pour voir le contenu de la bibliothèque
# import networkx
# dir(networkx)
In [16]:
# pour avoir de l'aide sur la commande is_connected par exemple
# help(networkx.is_connected)

Premier exemple

In [2]:
g=nx.Graph()
g.add_nodes_from(range(5))

g.add_edges_from([(0,1),(3,4),(4,2),(1,3),(4,0),(1,2)])

plt.figure()
nx.draw(g)
plt.show()
C:\Users\Pascal\Anaconda3\lib\site-packages\networkx\drawing\nx_pylab.py:611: MatplotlibDeprecationWarning: isinstance(..., numbers.Number)
  if cb.is_numlike(alpha):

Deuxième exemple

In [3]:
g = nx.newman_watts_strogatz_graph(100, 15, 0.35, seed = 12345 )

plt.figure()
nx.draw(g)
plt.show()
C:\Users\Pascal\Anaconda3\lib\site-packages\networkx\drawing\nx_pylab.py:611: MatplotlibDeprecationWarning: isinstance(..., numbers.Number)
  if cb.is_numlike(alpha):

Création d'un graphe à partir d'une matrice d'adjacence

In [5]:
M = np.array([[0,0,1,1],
              [1,1,0,0],
              [0,1,0,1],
              [1,0,1,0]])
print(M)
[[0 0 1 1]
 [1 1 0 0]
 [0 1 0 1]
 [1 0 1 0]]
In [6]:
plt.figure()
nx.draw(nx.DiGraph(M))
plt.show()
In [7]:
options = {
    'node_color' : 'yellow',
      'node_size'  : 550,
      'edge_color' : 'tab:grey',
      'with_labels': True
}
G = nx.DiGraph(M)
plt.figure()
nx.draw(G, **options)
plt.show()

Exercice tiré d'un bac ES

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) :

image.png

In [8]:
g=nx.Graph()

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()
C:\Users\Pascal\Anaconda3\lib\site-packages\networkx\drawing\nx_pylab.py:611: MatplotlibDeprecationWarning: isinstance(..., numbers.Number)
  if cb.is_numlike(alpha):

image.png

image.png

In [4]:
# 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 [5]:
ListeDegres
Out[5]:
{'E': 4, 'L': 4, 'M': 3, 'N': 3, 'S': 4, 'T': 2}
In [6]:
# Graphes Eulériens
nx.is_eulerian(g)
Out[6]:
False

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

image.png

Travail à partir de la matrice d'adjacence

In [ ]:
# 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 [25]:
print(adjacence)
[[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 [33]:
  # pour calculer le produit    
    
AdjaCarre=np.dot(adjacence,adjacence)
In [35]:
AdjCube=np.dot(AdjaCarre,adjacence)
In [36]:
AdjCube
Out[36]:
array([[ 6, 10,  9,  5, 10,  6],
       [10,  8,  8,  8, 10,  4],
       [ 9,  8,  4,  8,  5,  4],
       [ 5,  8,  8,  4,  9,  4],
       [10, 10,  5,  9,  6,  6],
       [ 6,  4,  4,  4,  6,  2]])

image.png

image.png

In [63]:
# 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)
[[ 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]]

Algorithme de Dijkstra

In [14]:
g=nx.Graph()

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 [92]:
nx.dijkstra_path_length(g,'M','S')
Out[92]:
11

Exemple d'un graphe complet

recherche d'un circuit Eulérien.

In [20]:
g=nx.complete_graph(5)

plt.figure()
nx.draw(g)
plt.show()
nx.is_eulerian(g)
list(nx.eulerian_circuit(g))
C:\Users\Pascal\Anaconda3\lib\site-packages\networkx\drawing\nx_pylab.py:611: MatplotlibDeprecationWarning: isinstance(..., numbers.Number)
  if cb.is_numlike(alpha):
Out[20]:
[(0, 4),
 (4, 3),
 (3, 2),
 (2, 4),
 (4, 1),
 (1, 3),
 (3, 0),
 (0, 2),
 (2, 1),
 (1, 0)]