"""
Représentation d’un graphe à l'aide d'une liste d'adjacence.
"""
from __future__ import annotations
class Sommet:
"""
Représentation d'un sommet.
"""
def __init__(self: Sommet, val: str) -> None:
"""
Initialisation du sommet.
"""
self.val = val
self.adj = [] # Sommets adjacents
def liste_adjacents(self: Sommet) -> list[Sommet]:
"""
Retourne la liste des sommets adjacents.
"""
return self.adj
def ajoute_adjacent(self: Sommet, som: Sommet) -> None:
"""Ajoute un sommet adjacent"""
self.adj.append(som)
def __repr__(self: Sommet) -> str:
rep = str(self.val) + " : ["
for i, sommet in enumerate(self.adj):
rep += str(sommet.val)
if i < len(self.adj) - 1:
rep += ", "
rep += "]"
return rep
class Graphe:
"""
Représentation du graphe.
"""
def __init__(self: Graphe, valeurs: str = "") -> None:
"""
La liste des sommets peut être passée dans une
chaîne de caractères. Chaque sommet doit être
séparé du précédent par une virgule.
Hypothèse : chaque sommet n'est présent qu'une seule
fois dans valeurs.
"""
self.sommets = [] # liste des sommets
if valeurs != "":
for sommet in valeurs.split(","):
self.sommets.append(Sommet(sommet))
def liste_sommets(self: Graphe) -> list[Sommet]:
"""
Retourne la liste des sommets du graphe.
"""
return self.sommets
def ajout_sommet(self: Graphe, val: str) -> None:
"""
Ajout du sommet de valeur val.
Si le sommet est déjà présent dans le graphe une exception
est levée.
"""
if self.existe_sommet(val):
raise Exception("Sommet déjà présent dans le graphe !")
self.sommets.append(Sommet(val)) # Ajout de l'objet de type Sommet
def existe_sommet(self: Graphe, s: str) -> bool:
"""
Vérifie que le sommet s existe bien dans le graphe.
"""
sommet_present = False # Sommet pas présent
for sommet in self.sommets: # sommet référence un objet
if sommet.val == s:
sommet_present = True
break
return sommet_present
def recuperation_sommet(self: Graphe, s: str) -> Sommet:
"""
Récupère le sommet de valeur s.
Lève une exception si le sommet n'existe pas.
"""
if not self.existe_sommet(s):
raise Exception(f"Le sommet {s} n'existe pas.")
for objet_sommet in self.sommets:
if objet_sommet.val == s:
return objet_sommet
def ajout_arete(self: Graphe, s1: str, s2: str) -> None:
"""
Ajoute l'arête (ou l'arc) {s1, s2} au graphe.
Si les sommets n'existent pas, on lève une exception.
Si l'arête existe déjà, on lève une exception.
Ne crée pas l'arête {s2, s1}.
"""
# L'arête existe-t-elle déjà ?
if self.existe_arête(s1, s2):
raise Exception("Arête existe déjà !")
# Récupération des sommets
sommet_depart = self.recuperation_sommet(s1)
sommet_destination = self.recuperation_sommet(s2)
# Ajout du sommet s2 à la liste des adjacents de s1
sommet_depart.ajoute_adjacent(sommet_destination)
def existe_arête(self, s1: str, s2: str) -> bool:
"""
Détermine si l'arête {s1, s2} existe dans le graphe.
Ne vérifie pas l'existence de l'arête {s2, s1}.
Lève une exception si l'un des sommets n'existe pas.
"""
objet_sommet_depart = self.recuperation_sommet(s1)
objet_sommet_arrivee = self.recuperation_sommet(s2)
return objet_sommet_arrivee in objet_sommet_depart.liste_adjacents()
def est_non_oriente(self: Graphe) -> bool:
"""
Détermine si le graphe est non orienté.
"""
for sommet1 in self.sommets:
for sommet2 in sommet1.liste_adjacents():
if not self.existe_arête(sommet2.val, sommet1.val):
return False
return True
def construction_matrice(self: Graphe) -> list[list[int]]:
"""
Construction de la matrice sommet - sommet du graphe.
"""
val_sommets_ordonnees = sorted([sommet.val for sommet in self.sommets])
matrice = [] # Initialisation de la matrice
for nom_sommet in val_sommets_ordonnees:
# Récupération de l'objet de type sommet associé au nom
sommet = self.recuperation_sommet(nom_sommet)
# Récupération des noms des sommets adjacents
nom_sommets_adjacents = [sommet_adj.val for sommet_adj in sommet.adj]
ligne_matrice = [] # Initialisation de la ligne de la matrice
for i in range(len(val_sommets_ordonnees)):
if val_sommets_ordonnees[i] in nom_sommets_adjacents:
ligne_matrice.append(1)
else:
ligne_matrice.append(0)
matrice.append(ligne_matrice) # Ajout de la ligne à la matrice
return matrice
def representation_matrice(self: Graphe) -> str:
"""
Retourne une chaîne de caractères qui permet un
affichage classique de la matrice (lignes x colonnes).
"""
matrice = self.construction_matrice()
rep = ""
nbre = len(matrice) # nombre de lignes et de colonnes
for i in range(nbre):
for j in range(nbre):
rep += str(matrice[i][j]) + "\t"
rep += "\n"
return rep
def __repr__(self: Graphe) -> str:
"""
Représentation du graphe sous forme d'une chaîne de caractères.
"""
rep = "{"
for i, sommet in enumerate(self.sommets):
rep += repr(sommet)
# Ajout de la virgule sauf dernier tour de boucle
if i < len(self.sommets) - 1:
rep += ", "
rep += "}"
return rep
def suppression_arete(self: Graphe, s1: str, s2: str) -> None:
"""
Supprime l'arête {s1, s2} si elle existe, lève une exception
dans le cas contraire.
"""
pass
def suppression_sommet(self: Graphe, s: str) -> None:
"""
Supprime le sommet s s'il existe, lève une exception dans
le cas contraire.
S'assure avant la suppression du sommet que toute arrête
dans laquelle il intervient est supprimée.
"""
pass
def rend_non_oriente(self: Graphe) -> None:
"""
Assure que pour toute arête {s1, s2} il existe une
arête {s2, s1}. Si ce n'est pas le cas, cette arête
est créée.
"""
pass
def taille(self: Graphe) -> int:
"""
Retourne le nombre de sommets dans le graphe.
"""
return len(self.sommets)
if __name__ == "__main__":
s1 = Sommet("a")
s2 = Sommet("b")
s3 = Sommet("c")
s1.adj.append(s2)
s1.adj.append(s3)
print(s1)
print(s2)
g1 = Graphe("a,b,c,d")
print(g1)
print(f"Sommet g présent dans le graphe : {g1.existe_sommet('g')}")
print(f"Sommet a présent dans le graphe : {g1.existe_sommet('a')}")
g1.ajout_sommet("e")
print(g1)
g1.ajout_arete("a", "b")
g1.ajout_arete("b", "a")
g1.ajout_arete("a", "e")
# g1.ajout_arete("a", "b")
g1.ajout_arete("c", "e")
g1.ajout_arete("e", "c")
print(g1)
print(f"Le graphe est non orienté : {g1.est_non_oriente()}")
g1.ajout_arete("e", "a")
print(f"Le graphe est non orienté : {g1.est_non_oriente()}")
print(f"Matrice : {g1.construction_matrice()}")
print(g1.representation_matrice())
print(f"Taille du graphe : {g1.taille()}")
print("---------------------")
g2 = Graphe("a,b,c,d,e,f,g")
print(f"Taille du graphe : {g2.taille()}")
g2.ajout_arete("a", "d")
g2.ajout_arete("a", "b")
g2.ajout_arete("a", "c")
g2.ajout_arete("b", "a")
g2.ajout_arete("b", "c")
g2.ajout_arete("b", "d")
g2.ajout_arete("b", "f")
g2.ajout_arete("c", "a")
g2.ajout_arete("c", "b")
g2.ajout_arete("c", "e")
g2.ajout_arete("d", "a")
g2.ajout_arete("d", "b")
g2.ajout_arete("d", "f")
g2.ajout_arete("e", "c")
g2.ajout_arete("f", "b")
g2.ajout_arete("f", "d")
g2.ajout_arete("f", "g")
g2.ajout_arete("g", "f")
print(f"Le graphe est non orienté : {g2.est_non_oriente()}")
print(g2.representation_matrice())
print(g2.liste_sommets())