Implémenter les méthodes suivantes de la classe Graphe_NO
Puis tester sur différents cas de graphes non orientés simples
class Graphe_NO:
def __init__(self,nb_sommets):
self.nb_sommets = nb_sommets
self.nb_aretes = 0
self.aretes = [[] for i in range(self.nb_sommets)]
self.visites = [False]*self.nb_sommets
self.peres = [-1]*self.nb_sommets
self.peres[0] = 0
def ajoute_arete(self,u,v):
self.nb_aretes += 1
self.aretes[u].append(v)
self.aretes[v].append(u)
def voisins(self,i):
return self.aretes[i]
def degre(self,i):
pass
def max_degre(self):
pass
def _a_un_cycle(self,s):
for v in self.aretes[s]:
if self.peres[v] == -1:
self.peres[v] = s
if self._a_un_cycle(v):
return True
elif self.peres[s] != v and self.peres[v] != s:
return True
return False
def a_un_cycle(self):
return self._a_un_cycle(0)
def __str__(self):
pass
Implémenter une classe PP_NO (parcours en profondeur)
Puis tester
class PP_NO:
def __init__(self,graphe,source):
self.visites = [False]*graphe.nb_sommets
self.ancetres = [0]*graphe.nb_sommets
self.source = source
self.pp(graphe,source)
def pp(self,graphe,v):
self.visites[v] = True
for w in graphe.aretes[v]:
if not self.visites[w]:
self.ancetres[w] = v
self.pp(graphe,w)
def a_un_chemin_vers(self,v):
pass
def chemin_vers(self,v):
pass
Implémenter une classe PL_NO (parcours en largeur)
Puis tester
class PL_NO:
def __init__(self,graphe,source):
self.source = source
self.visites = [False]*graphe.nb_sommets
self.distance = [-1]*graphe.nb_sommets
self.distance[source] = 0
self.ancetres = [source]*graphe.nb_sommets
self.pl(graphe,source)
def pl(self,graphe,source):
file = deque([source])
self.visites[source] = True
while len(file) > 0:
v = file.pop()
for x in graphe.aretes[v]:
if not self.visites[x]:
self.visites[x] = True
self.ancetres[x] = v
self.distance[x] = self.distance[v] + 1
file.appendleft(x)
def nb_sauts(self,sommet):
pass
def dist_max(self):
pass
def cercles(self):
"""
retourne une liste de liste où
le premier élément est la liste [source] puis la liste
des sommets à distance 1 de la source et ainsi de suite
"""
pass
def a_un_chemin_vers(self,v):
pass
def chemin_vers(self,v):
pass
On teste l'algorithme de Dijkstra sur plusieurs exemples
class Sommet:
"""
un objet de type Sommet a trois attributs:
-un sommet = un entier de 0 à n-1 = un sommet du graphe pondéré
-une cle = la distance à la source du sommet en question (évolue)
-pos = position de l'objet dans la file min (évolue)
"""
def __init__(self,sommet,cle,pos):
self.sommet = sommet
self.cle = cle
self.pos = pos
class File_min:
"""
Une file de priorité min pour l'algorithme
de Dijkstra
la file contient des références concernant des objets de type Sommet
les objets sont placés dans la file min à partir de leur clé
"""
def __init__(self,n):
self.taille = n
self.tab = [n]
def inserer(self,Sommet):
self.taille += 1
self.tab.append(Sommet)
Sommet.pos = self.taille
self.percoler(self.taille)
def tamiser(self,i):
"""
la valeur du sommet i est strictement plus grande
que l'un de ses enfants
On fait descendre cette valeur dans l'arbre jusqu'à ce
qu'elle trouve sa place
complexité logarithmique
"""
enfant_gauche = i << 1
enfant_droit = enfant_gauche + 1
if enfant_gauche <= self.taille and\
self.tab[enfant_gauche].cle < self.tab[i].cle:
max = enfant_gauche
else:
max = i
if enfant_droit <= self.taille and\
self.tab[enfant_droit].cle < self.tab[max].cle:
max = enfant_droit
if max != i:
echanger(self.tab,i,max)
self.tab[i].pos = i
self.tab[max].pos = max
self.tamiser(max)
def percoler(self,i):
"""
La valeur du sommet i est strictement plus petite que celle de son parent
On fait monter cette valeur dans l'arbre jusqu'à ce qu'elle retrouve
sa place
"""
pos = i
while pos > 1 and self.tab[pos].cle < self.tab[pos >> 1].cle:
echanger(self.tab,pos,pos >> 1)
self.tab[pos].pos = pos
self.tab[pos >> 1].pos = pos >> 1
pos = pos >> 1
def minimum(self):
return self.tab[1].sommet
def cree_tas_min(self,tableau):
"""
cree un tas min de n éléments à partir d'un tableau de n éléments
Propriété : les feuilles d'un arbre binaire complété sont indexés par
E(n/2) + 1, E(n/2) + 2,...,n
Autrement dit ça ne sert à rien de tamiser les feuilles
On tamise les noeuds qui ne sont pas des feuilles dans l'ordre inverse
de E(n/2) jqà la racine
complexité linéaire
"""
for i in range(self.taille):
self.tab.append(tableau[i])
for i in range(self.taille//2,0,-1):
self.tamiser(i)
def elimine_racine(self):
"""
retourne la racine en enlevant cette valeur du tas
on rétablit la structure de tas min
on met à jour la position du Sommet qui prend la place
de la racine
complexité logarithmique
"""
racine = self.tab[1]
self.tab[1] = self.tab[self.taille]
#on met à jour la position du Sommet qui prend la place
#de la racine
self.tab[1].pos = 1
#on élimine la racine
self.tab.pop()
self.taille -= 1
self.tamiser(1)
return racine.sommet
def __len__(self):
return len(self.tab)
def __str__(self):
ch =''
for i in range(1,len(self.tab)):
ch = ch + str(self.tab[i].sommet)+" "
return ch
class Dijkstra:
def __init__(self,graphe:Graphe_NO,source:int,l):
self.source = source
self.distance = [inf]*graphe.nb_sommets
self.distance[source] = 0
self.ancetres = [source]*graphe.nb_sommets
self.dijkstra(graphe,source,l)
def relachement(self,v,x,l,file_min,dictionnaire):
if self.distance[v] + l[v][x] < self.distance[x]:
self.ancetres[x] = v
self.distance[x] = self.distance[v] + l[v][x]
#p est la position dans la file du Sommet associé au sommet
#du graphe de valeur x
p = dictionnaire[x].pos
file_min.tab[p].cle = self.distance[x]
file_min.percoler(p)
def dijkstra(self,graphe,source,l):
liste = [Sommet(i,self.distance[i],i+1) for i in range(graphe.nb_sommets)]
dictionnaire = {i:liste[i] for i in range(graphe.nb_sommets)}
file_min = File_min(graphe.nb_sommets)
file_min.cree_tas_min(liste)
while len(file_min) > 1:
v = file_min.elimine_racine()
for x in graphe.aretes[v]:
self.relachement(v,x,l,file_min,dictionnaire)
def dist(self,sommet):
pass
def a_un_chemin_vers(self,v):
pass
def chemin_vers(self,v):
pass
Modifier tout ce qui a été fait précédemment mais cette fois ci pour un graphe orienté