from File import File
from Pile import Pile
class Graphe:
def __init__(self, oriente):
self.dico = {}
self.oriente = oriente
def affiche(self):
for i in self.dico:
print(i,'->',self.dico[i])
def ajouter_sommet(self, sommet):
if not sommet in self.dico:
self.dico[sommet] = []
def ajouter_arete(self, s1, s2):
if s1 in self.dico and s2 in self.dico :
self.dico[s1].append(s2)
if not self.oriente :
self.dico[s2].append(s1)
def parcours_en_largeur(self, depart) -> None :
a_traiter = File()
deja_vus = [depart]
a_traiter.enfiler(depart)
while not a_traiter.est_vide():
s = a_traiter.defiler()
print(s,end=" ")
for v in self.dico[s]:
if not v in deja_vus:
a_traiter.enfiler(v)
deja_vus.append(v)
def parcours_en_profondeur(self, depart) -> None :
a_traiter = Pile()
deja_vus = [depart]
a_traiter.empiler(depart)
while not a_traiter.est_vide():
s = a_traiter.depiler()
print(s,end=" ")
for v in self.dico[s]:
if not v in deja_vus:
a_traiter.empiler(v)
deja_vus.append(v)
def parcours_profondeur_recursif(self, depart, deja_vu=[]) -> None:
deja_vu.append(depart)
print(depart,end=" ")
for v in self.dico[depart]:
if not v in deja_vu:
self.parcours_profondeur_recursif(v, deja_vu)
from Graphe import Graphe
class GraphePondere(Graphe):
def __init__(self, oriente):
super().__init__(oriente)
self.ponderation = {}
def get_sommets(self):
return list(self.dico.keys())
def ajouter_arete(self, s1, s2, ponderation) -> None:
if s1 in self.dico and s2 in self.dico :
self.dico[s1].append(s2)
self.ponderation[(s1,s2)] = ponderation
if not self.oriente :
self.dico[s2].append(s1)
self.ponderation[(s2,s1)] = ponderation
def show(self):
for i in self.dico:
print(i,'->', end="")
for element in self.dico[i]:
print('('+str(element)+','+str(self.ponderation[(i,element)])+')', end="")
print()
def get_ponderation(self, s1, s2) -> int:
if (s1, s2) in self.ponderation:
return self.ponderation[(s1, s2)]
else:
return None
def voisins(self,sommet):
l = []
for v in self.dico[sommet]:
l.append((v, self.ponderation[(sommet, v)]))
return l
def mini(self, dico):
mini = float('Inf')
mini_sommet =""
for k, v in dico.items():
if v[0] < mini and v[2] is not True:
mini = v[0]
mini_sommet = k
return mini, mini_sommet
def run(self):
d = self.initialisation()
sommet_courant = self.depart
for v in self.graphe.voisins(sommet_courant):
d[v[0]] = [v[1], sommet_courant, False]
for _ in range(self.graphe.ordre()-1):
mini = self.mini(d)
print("MINI : ", mini)
d[mini[1]][2] = True
sommet_courant = mini[1]
for v in self.graphe.voisins(sommet_courant):
if d[v[0]][2] is not True:
if d[sommet_courant][0] + v[1] < d[v[0]][0]:
d[v[0]] = [d[sommet_courant][0] + v[1], sommet_courant, False]
courant = self.fin
l = [courant]
while courant != self.depart:
courant = d[courant][1]
l.append(courant)
return l[::-1], d[self.fin][0]