Avant de créer un algorithme de recherche de cycle eulérien, on va d'abord s'assurer qu'il en existe bien un. Créons la matrice associé à notre graphe :
import numpy as np
matrix_zone_A = np.array([[0,1,0,1,0,0,0,0,0,0],[1,0,0,0,1,0,0,0,0,0],[0,0,0,1,0,0,0,1,0,0],[1,0,1,0,1,0,0,1,0,0],[0,1,0,1,0,1,0,1,0,0],[0,0,0,0,1,0,0,0,0,1],[0,0,0,0,0,0,0,1,1,0],[0,0,1,1,1,0,1,0,0,0],[0,0,0,0,0,0,1,0,0,1],[0,0,0,0,0,1,0,0,1,0]])
print("### Matrice associé au graphe de la zone A ###")
matrix_zone_A
### Matrice associé au graphe de la zone A ###
array([[0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 0, 1, 0, 0, 1, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 1, 1, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 1, 0]])
Ensuite, comptons le degré par sommet :
def degreSommetGrapheMatrice(matrice, sommet):
degre = sum(matrice[sommet])
return degre
print("### Degré des sommets du graphe de la Zone A ###")
for sommet in range(len(matrix_zone_A)):
print("sommet", str(sommet+1), ":", str(degreSommetGrapheMatrice(matrix_zone_A, sommet)))
### Degré des sommets du graphe de la Zone A ### sommet 1 : 2 sommet 2 : 2 sommet 3 : 2 sommet 4 : 4 sommet 5 : 4 sommet 6 : 2 sommet 7 : 2 sommet 8 : 4 sommet 9 : 2 sommet 10 : 2
D'une part, notre graphe n'a aucun sommet impair. D'autre part, notre graphe est connexe (d'un sommet donné on peut atteindre n'importe quels autres sommets). D'après le théorème d'Euler, notre graphe possède un cycle eulérien.On peut aussi créer un algorithme qui effectue ce raisonnement :
def existeCycleEulerien(matrice):
isEulerien = True
for sommet in range(len(matrice)):
degre = degreSommetGrapheMatrice(matrice, sommet)
if degre%2 !=0:
isEulerien = False
return isEulerien
if (existeCycleEulerien(matrix_zone_A)):
print ("Le graphe de la Zone A est eulérien")
else:
print ("Le graphe de la Zone A n'est pas eulérien")
Le graphe de la Zone A est eulérien
On va maintenant implémenter un algorithme pour trouver ce cycle Eulérien :
from collections import deque
import copy
def cycleEulerien(matrice):
# la matrice est passée par référence, on fait donc une copie de la matrice pour éviter d'écraser ses données.
# comme il faut aussi copier les listes internes, on fait une _copie profonde_
matrice = copy.deepcopy(matrice)
n = len(matrice)
cycle = deque() # cycle est le cycle à construire
stack = deque() # stack est la pile de sommets à traiter
cur = 0 # cur est le sommet courant. on commence avec le premier sommet de la matrice
# on boucle tant qu'il y a des sommets à traiter dans la pile
# ou que le sommet courant possède au moins 1 voisin non traité
while(len(stack) > 0 or degreSommetGrapheMatrice(matrice, cur) != 0):
# si le sommet courant ne possède aucun voisin, on l'ajoute au cycle
# et on revient au sommet ajouté précédemment dans la pile (backtracking)
# qui devient le nouveau sommet courant
if degreSommetGrapheMatrice(matrice, cur) == 0:
cycle.append(cur)
cur = stack[-1]
del stack[-1]
# si il a au moins 1 voisin, on l'ajoute à la stack pour y revenir plus tard (backtracking)
# on retire l'arête qu'il partage avec ce voisin, qui devient le sommet courant
else:
stack.append(cur)
ligne = matrice[cur]
i=0
for i in range(len(ligne)):
if ligne[i] != 0:
break
voisin = i
matrice[cur][voisin] = 0
matrice[voisin][cur] = 0
cur = voisin
return cycle;
print("### Calcul d'un cycle Eulérien du graphe de la Zone A ###")
cycle = cycleEulerien(matrix_zone_A)
for sommet in cycle:
print(sommet+1, "-> ", end = '')
print(cycle[0]+1)
### Calcul d'un cycle Eulérien du graphe de la Zone A ### 1 -> 4 -> 8 -> 7 -> 9 -> 10 -> 6 -> 5 -> 8 -> 3 -> 4 -> 5 -> 2 -> 1
On peut vérifier ce cycle eulérien manuellement via le graphe :
On peut maintenant analyser le temps que notre algorithme a besoin pour se terminer. On veut savoir s'il est utilisable sur des villes entières, et donc des matrices bien plus grandes que celle de la zone A. Pour cela, on va générer aléatoirement des matrices de taille croissante, et analyser le temps que met notre algorithme à trouver leur cycle eulérien. On va ensuite pouvoir afficher dans un graphique le temps de calcul de l'algorithme en fonction de la taille de la amtrice d'entrée.
Tout d'abord, créons une fonction qui génère un graphe aléatoire :
import numpy as np
def grapheAleatoireEulerien(taille):
# on génère une matrice aléatoire booléenne (pour pouvoir faire des `ou`)
b = np.random.choice((True, False), size=(taille,taille), p=[0.4, 0.6])
# on fait le `ou` logique de la matrice et de sa transposée
b_symm = np.logical_or(b, b.T)
# on renvoie la matrice de booléens convertie en matrice d'entiers
return b_symm.astype(int)
print(grapheAleatoireEulerien(4))
[[0 1 0 1] [1 0 1 0] [0 1 1 0] [1 0 0 1]]
Ensuite, affichons le temps de calcul de la fonction cycleEulerien sur plusieurs matrices :
from ipywidgets import IntProgress
from IPython.display import display
import time
from matplotlib import pyplot as plt
nb_iteration = 50
taille_min = 10
taille_max = 200
taille_step = 10
durees_moy = []
durees_mieux = []
durees_pire = []
# on affiche la barre de progression
nb_tests = ((taille_max - taille_min) / taille_step) * nb_iteration
bar = IntProgress(min=0, max=nb_tests, layout={"width" : "100%"})
display(bar)
for taille in range(10, 200, 10):
duree_mieux = float('inf')
duree_pire = 0.0
duree_moy = 0.0
for i in range(nb_iteration):
instance = grapheAleatoireEulerien(taille)
start = time.process_time()
cycle = cycleEulerien(instance)
stop = time.process_time()
duree = (stop-start)
duree_moy += duree
if duree_mieux > duree:
duree_mieux = duree
if duree_pire < duree:
duree_pire = duree
bar.value += 1 # on met à jour la barre de progression
# on met à jour les listes des temps d'exécution
durees_moy.append(duree_moy/nb_iteration)
durees_mieux.append(duree_mieux)
durees_pire.append(duree_pire)
# on cache la barre de progression
bar.close()
# on règle l'affichage des courbes
tailles = [x for x in range(10, 200, 10)]
plt.figure(figsize=(20,10))
plt.xlabel('taille du graphe')
plt.xticks(ticks=tailles) # valeurs affichées sur l'axe X
plt.ylabel('temps de calcul')
# on charge les données
plt.plot(tailles, durees_moy, label='durée moyenne')
plt.plot(tailles, durees_mieux, label='durée au mieux')
plt.plot(tailles, durees_pire, label='durée au pire')
# on affiche
plt.legend()
plt.show()
On peut aussi anticiper ce résultat en effectuant une étude théorique de complexité de la fonction cycleEulerien :
