1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
|
"""
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())
|