Les graphes¶

Liens : https://iut-info.univ-reims.fr/users/blanchard/ISN20181218/les-graphes-from-scratch.html

http://cours-info.iut-bm.univ-fcomte.fr/wiki/pmwiki.php/Graphes/TP10#toc11

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

# Pour voir le contenu de la bibliothèque
# import networkx
# dir(networkx)

# pour avoir de l'aide sur la commande is_connected par exemple
# help(networkx.is_connected)

Premier exemple¶

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¶

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¶

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]]

plt.figure()
nx.draw(nx.DiGraph(M))
plt.show()

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

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

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

ListeDegres

{'E': 4, 'L': 4, 'M': 3, 'N': 3, 'S': 4, 'T': 2}

# Graphes Eulériens
nx.is_eulerian(g)

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

Travail à partir de la matrice d'adjacence¶

# 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]])

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]]

  # pour calculer le produit    
    
AdjaCarre=np.dot(adjacence,adjacence)

AdjCube=np.dot(AdjaCarre,adjacence)

AdjCube

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

# 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¶

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

nx.dijkstra_path_length(g,'M','S')

11

Exemple d'un graphe complet¶

recherche d'un circuit Eulérien.

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

[(0, 4),
 (4, 3),
 (3, 2),
 (2, 4),
 (4, 1),
 (1, 3),
 (3, 0),
 (0, 2),
 (2, 1),
 (1, 0)]