1#!/usr/bin/env python3 

2from matplotlib import pyplot as plt 

3import networkx as nx 

4import numpy 

5from numpy import zeros 

6import copy 

7# pour copier le dictionnaire de données afin de le modifier sans modifier le 

8# dictionnaire initial 

9 

10import json 

11 

12def lire_entree_json() -> dict: 

13 """ 

14 Cette fonction lit un fichier json en entrée et renvoie le dictionnaire 

15 associé. 

16 

17 La fonction ne prends pas d'argument en entrée et renvoie un dictionnaire 

18 """ 

19 with open('data_exemple.json', 'r') as fichier: 

20 donnees = fichier.read() 

21 

22 exemple_graphe = json.loads(donnees) 

23 return exemple_graphe 

24 

25 

26def associer_eleves_numeros(dictionnaire: dict) -> dict: 

27 """ 

28 Cette fonction prend en entrée un dictionnaire et renvoie un dictionnaire 

29 associant les élèves à un numero d'ordre. 

30 

31 Cette fonction permet de «numéroter» les élèves pour un accès plus facile. 

32 La fonction repose fondamentalement sur une propriété de Python 3.7 : les 

33 dictionnaires sont désormais ordonnés par défaut. 

34 """ 

35 dict_eleves_numero = {} 

36 for k1,v1 in enumerate(dictionnaire): 

37 dict_eleves_numero[v1] = k1 

38 return dict_eleves_numero 

39 

40 

41def graphe_numerique(dictionnaire: dict,dict_eleves_numero: dict) -> dict: 

42 """ 

43 Cette fonction prend en entrée un dictionnaire (le graphe) et renvoie un 

44 dictionnaire (le graphe) purement numérique. 

45 

46 La fonction permet de réécrire le dictionnaire suivant le modèle adopté par 

47 le reste des fonctions du projet. 

48 >>> graphe_numerique({'Alice': {'Bob': 1, 'Eve': 2}}, {'Alice':0, 'Bob': 2, 'Eve':1}) 

49 {0: {2: 1, 1: 2}} 

50 """ 

51 dict_amis_numeros = dict((dict_eleves_numero[key], value) for (key, value) in dictionnaire.items()) 

52 for v in dict_amis_numeros.items(): 

53 dict_amis_numeros[v[0]] = dict((dict_eleves_numero[key], value) for (key, value) in v[1].items()) 

54 return dict_amis_numeros 

55 

56 

57def cree_dict_classe_liste(dictionnaire: dict) -> dict: 

58 """ 

59 Transforme un dictionnaire de dictionnaire en dictonnaire de liste (où les 

60 clefs sont les indices dans la liste) 

61 

62 - Precondition dictionnaire est du type dict_amis_numeros: 

63 {0: {20: 2, 15: 1}, 1: {18: 2, 13: 1}, 2: {17: 2, 7: 1} etc...} 

64 - Post condition : Cette fonction cree un dictionnaire ou les cles sont les 

65 numeros des eleves et les valeurs des listes de leurs amis 

66 Exemple : {0: [20, 15], 1: [18, 13], 2: [17, 7],etc...} 

67 >>> cree_dict_classe_liste({0: {20: 2, 15: 1}, 1: {18: 2, 13: 1}, 2: {17: 2, 7: 1}}) 

68 {0: [20, 15], 1: [18, 13], 2: [17, 7]} 

69 """ 

70 dictionnaire_liste={} 

71 for sommet in dictionnaire: 

72 dictionnaire_liste[sommet]=list(dictionnaire[sommet].keys()) 

73 return dictionnaire_liste 

74 

75def cree_graphe_nx(dictionnaire: dict) -> nx.DiGraph: 

76 """ 

77 Cette fonction premet de transformer une représentation en dictionnaire en 

78 une représentation «complexe» d'un objet graphe orienté. 

79 

80 - Précondition : l'entrée est un dictionnaire 

81 - Postcondition : la sortie est un graphe de Networkx 

82 """ 

83 G = nx.DiGraph() # au lieu de G=nx.Graph() 

84 for sommets in dictionnaire.keys(): 

85 G.add_node(sommets) 

86 for sommet in dictionnaire: 

87 for sommets_adjacents in dictionnaire[sommet]: 

88 G.add_edge(sommet, sommets_adjacents) 

89 return G 

90 

91 

92def afficher_graphe(dictionnaire,fichier): 

93 """ 

94 Cette fonction permet de créer un fichier png correspondant au graphe passé 

95 en argument. 

96 

97 Prends un dictionnaire en entrée, représentant un graphe et affiche un 

98 graphe. 

99 Son code de retour est None 

100 """ 

101 G = cree_graphe_nx(dictionnaire) 

102 plt.clf() 

103 #pos = nx.spring_layout(G) 

104 #nx.draw_networkx_nodes(G, pos, node_color='b', node_size=60) 

105 #nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5) 

106 #nx.draw_networkx_labels(G, pos, font_size=10) 

107 #plt.axis('off') 

108 nx.draw_circular(G,with_labels=True) # Cela me semble mieux 

109 plt.show() 

110 plt.savefig(fichier) 

111 return None 

112 

113 

114 

115def chemin_long_3(dictionnaire: dict, start: int) -> list: 

116 """ 

117 Cette fonction retourne une liste de toutes les listes de chemins de 

118 longueur 3 partant du sommet start 

119 

120 Precondition : dictionnaire est du type : {0: [20, 15], 1: [18, 13],etc} 

121 Ce dictionnaire est cree par la fonction cree_dict_classe_liste(dict_amis_numeros) 

122 Postcondition : retourne une liste de listes de chemins 

123 Par exemple : pour le sommet 0 et le dictionnaire complet, on obtient: 

124 [[0, 20, 25, 18], [0, 20, 25, 20], [0, 20, 18, 25], [0, 20, 18, 23], [0, 15, 19, 5], [0, 15, 19, 14], [0, 15, 5, 19], [0, 15, 5, 14]] 

125 Test : 

126 >>> chemin_long_3({0: [20, 15], 1: [18, 13], 2: [17, 7], 3: [24, 7], \ 

127 4: [18, 11], 5: [19, 14], 6: [4, 13], 7: [24, 3], 8: [26, 23], 9: [25, 20], \ 

128 10: [22, 23], 11: [13, 22], 12: [4, 13], 13: [16, 12], 14: [17, 4], \ 

129 15: [19, 5], 16: [18, 13], 17: [4, 15], 18: [25, 23], 19: [5, 14], \ 

130 20: [25, 18], 21: [25, 18], 22: [13, 23], 23: [8, 18], 24: [3, 7], \ 

131 25: [18, 20], 26: [13, 23]}, 0) 

132 [[0, 20, 25, 18], [0, 20, 25, 20], [0, 20, 18, 25], [0, 20, 18, 23], [0, 15, 19, 5], [0, 15, 19, 14], [0, 15, 5, 19], [0, 15, 5, 14]] 

133 """ 

134 liste=[[] for i in range(8)] 

135 # 1 sommet des chemins 

136 for i in range(8): 

137 liste[i].append(start) 

138 # 2 sommets des chemins 

139 for i in range(4): 

140 liste[i].append(dictionnaire[liste[i][-1]][0]) 

141 for i in range(4,8): 

142 liste[i].append(dictionnaire[liste[i][-1]][1]) 

143 # 3 sommets des chemins 

144 i=0 

145 j=0 

146 liste[i].append(dictionnaire[liste[i][-1]][j]) 

147 i=1 

148 j=0 

149 liste[i].append(dictionnaire[liste[i][-1]][j]) 

150 while i<6: 

151 i=i+1 

152 j=(j+1)%2 

153 liste[i].append(dictionnaire[liste[i][-1]][j]) 

154 i=i+1 

155 liste[i].append(dictionnaire[liste[i][-1]][j]) 

156 # 4 sommets des chemins 

157 for i in range(8): 

158 j=i%2 

159 liste[i].append(dictionnaire[liste[i][-1]][j]) 

160 return liste 

161 

162 

163def tous_les_chemins_long_3(dictionnaire: dict) -> list: 

164 """ 

165 Afficher tous les chemins de longueur 3, indépendament de leur point de 

166 départ 

167 

168 - Precondition : dictionnaire est du type : {0: [20, 15], 1: [18, 13],etc} 

169 Ce dictionnaire est cree par la fonction cree_dict_classe_liste(dict_amis_numeros) 

170 - Postcondition : Exemple de liste retournée : 

171 [[[0, 20, 25, 18], [0, 20, 25, 20], [0, 20, 18, 25], [0, 20, 18, 23], [0, 15, 19, 5], [0, 15, 19, 14], [0, 15, 5, 19], [0, 15, 5, 20]], 

172 [[1, 18, 25, 18], [1, 18, 25, 20], [1, 18, 23, 8], etc... 

173 >>> tous_les_chemins_long_3({0: [20, 15], 1: [18, 13], 2: [17, 7], 3: [24, 7], \ 

174 4: [18, 11], 5: [19, 14], 6: [4, 13], 7: [24, 3], 8: [26, 23], 9: [25, 20], \ 

175 10: [22, 23], 11: [13, 22], 12: [4, 13], 13: [16, 12], 14: [17, 4], \ 

176 15: [19, 5], 16: [18, 13], 17: [4, 15], 18: [25, 23], 19: [5, 14], \ 

177 20: [25, 18], 21: [25, 18], 22: [13, 23], 23: [8, 18], 24: [3, 7], \ 

178 25: [18, 20], 26: [13, 23]}) 

179 [[[0, 20, 25, 18], [0, 20, 25, 20], [0, 20, 18, 25], [0, 20, 18, 23], [0, 15, 19, 5], [0, 15, 19, 14], [0, 15, 5, 19], [0, 15, 5, 14]], [[1, 18, 25, 18], [1, 18, 25, 20], [1, 18, 23, 8], [1, 18, 23, 18], [1, 13, 16, 18], [1, 13, 16, 13], [1, 13, 12, 4], [1, 13, 12, 13]], [[2, 17, 4, 18], [2, 17, 4, 11], [2, 17, 15, 19], [2, 17, 15, 5], [2, 7, 24, 3], [2, 7, 24, 7], [2, 7, 3, 24], [2, 7, 3, 7]], [[3, 24, 3, 24], [3, 24, 3, 7], [3, 24, 7, 24], [3, 24, 7, 3], [3, 7, 24, 3], [3, 7, 24, 7], [3, 7, 3, 24], [3, 7, 3, 7]], [[4, 18, 25, 18], [4, 18, 25, 20], [4, 18, 23, 8], [4, 18, 23, 18], [4, 11, 13, 16], [4, 11, 13, 12], [4, 11, 22, 13], [4, 11, 22, 23]], [[5, 19, 5, 19], [5, 19, 5, 14], [5, 19, 14, 17], [5, 19, 14, 4], [5, 14, 17, 4], [5, 14, 17, 15], [5, 14, 4, 18], [5, 14, 4, 11]], [[6, 4, 18, 25], [6, 4, 18, 23], [6, 4, 11, 13], [6, 4, 11, 22], [6, 13, 16, 18], [6, 13, 16, 13], [6, 13, 12, 4], [6, 13, 12, 13]], [[7, 24, 3, 24], [7, 24, 3, 7], [7, 24, 7, 24], [7, 24, 7, 3], [7, 3, 24, 3], [7, 3, 24, 7], [7, 3, 7, 24], [7, 3, 7, 3]], [[8, 26, 13, 16], [8, 26, 13, 12], [8, 26, 23, 8], [8, 26, 23, 18], [8, 23, 8, 26], [8, 23, 8, 23], [8, 23, 18, 25], [8, 23, 18, 23]], [[9, 25, 18, 25], [9, 25, 18, 23], [9, 25, 20, 25], [9, 25, 20, 18], [9, 20, 25, 18], [9, 20, 25, 20], [9, 20, 18, 25], [9, 20, 18, 23]], [[10, 22, 13, 16], [10, 22, 13, 12], [10, 22, 23, 8], [10, 22, 23, 18], [10, 23, 8, 26], [10, 23, 8, 23], [10, 23, 18, 25], [10, 23, 18, 23]], [[11, 13, 16, 18], [11, 13, 16, 13], [11, 13, 12, 4], [11, 13, 12, 13], [11, 22, 13, 16], [11, 22, 13, 12], [11, 22, 23, 8], [11, 22, 23, 18]], [[12, 4, 18, 25], [12, 4, 18, 23], [12, 4, 11, 13], [12, 4, 11, 22], [12, 13, 16, 18], [12, 13, 16, 13], [12, 13, 12, 4], [12, 13, 12, 13]], [[13, 16, 18, 25], [13, 16, 18, 23], [13, 16, 13, 16], [13, 16, 13, 12], [13, 12, 4, 18], [13, 12, 4, 11], [13, 12, 13, 16], [13, 12, 13, 12]], [[14, 17, 4, 18], [14, 17, 4, 11], [14, 17, 15, 19], [14, 17, 15, 5], [14, 4, 18, 25], [14, 4, 18, 23], [14, 4, 11, 13], [14, 4, 11, 22]], [[15, 19, 5, 19], [15, 19, 5, 14], [15, 19, 14, 17], [15, 19, 14, 4], [15, 5, 19, 5], [15, 5, 19, 14], [15, 5, 14, 17], [15, 5, 14, 4]], [[16, 18, 25, 18], [16, 18, 25, 20], [16, 18, 23, 8], [16, 18, 23, 18], [16, 13, 16, 18], [16, 13, 16, 13], [16, 13, 12, 4], [16, 13, 12, 13]], [[17, 4, 18, 25], [17, 4, 18, 23], [17, 4, 11, 13], [17, 4, 11, 22], [17, 15, 19, 5], [17, 15, 19, 14], [17, 15, 5, 19], [17, 15, 5, 14]], [[18, 25, 18, 25], [18, 25, 18, 23], [18, 25, 20, 25], [18, 25, 20, 18], [18, 23, 8, 26], [18, 23, 8, 23], [18, 23, 18, 25], [18, 23, 18, 23]], [[19, 5, 19, 5], [19, 5, 19, 14], [19, 5, 14, 17], [19, 5, 14, 4], [19, 14, 17, 4], [19, 14, 17, 15], [19, 14, 4, 18], [19, 14, 4, 11]], [[20, 25, 18, 25], [20, 25, 18, 23], [20, 25, 20, 25], [20, 25, 20, 18], [20, 18, 25, 18], [20, 18, 25, 20], [20, 18, 23, 8], [20, 18, 23, 18]], [[21, 25, 18, 25], [21, 25, 18, 23], [21, 25, 20, 25], [21, 25, 20, 18], [21, 18, 25, 18], [21, 18, 25, 20], [21, 18, 23, 8], [21, 18, 23, 18]], [[22, 13, 16, 18], [22, 13, 16, 13], [22, 13, 12, 4], [22, 13, 12, 13], [22, 23, 8, 26], [22, 23, 8, 23], [22, 23, 18, 25], [22, 23, 18, 23]], [[23, 8, 26, 13], [23, 8, 26, 23], [23, 8, 23, 8], [23, 8, 23, 18], [23, 18, 25, 18], [23, 18, 25, 20], [23, 18, 23, 8], [23, 18, 23, 18]], [[24, 3, 24, 3], [24, 3, 24, 7], [24, 3, 7, 24], [24, 3, 7, 3], [24, 7, 24, 3], [24, 7, 24, 7], [24, 7, 3, 24], [24, 7, 3, 7]], [[25, 18, 25, 18], [25, 18, 25, 20], [25, 18, 23, 8], [25, 18, 23, 18], [25, 20, 25, 18], [25, 20, 25, 20], [25, 20, 18, 25], [25, 20, 18, 23]], [[26, 13, 16, 18], [26, 13, 16, 13], [26, 13, 12, 4], [26, 13, 12, 13], [26, 23, 8, 26], [26, 23, 8, 23], [26, 23, 18, 25], [26, 23, 18, 23]]] 

180 """ 

181 liste=[] 

182 for sommet in dictionnaire: 

183 liste.append(chemin_long_3(dictionnaire, sommet)) 

184 return liste 

185 

186 

187def dedoublonner(liste: list) -> list: 

188 """ 

189 Une fonction pour retirer les éventuels doublons, l'ordre ne comptant pas. 

190 

191 Precondition : une liste de liste, contenant éventuellement des doublons 

192 Postcondition : une liste de liste, sans doublon 

193 La fonction permet de retirer les doublons d'une liste 

194 >>> dedoublonner([[1,2],[2,1]]) 

195 [{1, 2}] 

196 """ 

197 retval = [] 

198 for elem in liste: 

199 if set(elem) not in [set(s) for s in retval]: 

200 retval.append(set(elem)) 

201 return retval 

202 

203 

204def cycles_longueur_3(liste_chemins: list) -> list: 

205 """ 

206 Retourne les chemins qui sont des cycles 

207 

208 - Pre-condition : liste_chemin est du type retourne par la fonction tous_les_chemins_long_3(dictionnaire) 

209 - Post-condition : retourne la liste de tous les chemins de longueur 3 

210 qui sont des cycles. 

211 >>> cycles_longueur_3([[[0, 20, 25, 18], [0, 20, 25, 20], [0, 20, 18, 25], [0, 20, 18, 23], [0, 15, 19, 5], [0, 15, 19, 14], [0, 15, 5, 19], [0, 15, 5, 14]], [[1, 18, 25, 18], [1, 18, 25, 20], [1, 18, 23, 8], [1, 18, 23, 18], [1, 13, 16, 18], [1, 13, 16, 13], [1, 13, 12, 4], [1, 13, 12, 13]], [[2, 17, 4, 18], [2, 17, 4, 11], [2, 17, 15, 19], [2, 17, 15, 5], [2, 7, 24, 3], [2, 7, 24, 7], [2, 7, 3, 24], [2, 7, 3, 7]], [[3, 24, 3, 24], [3, 24, 3, 7], [3, 24, 7, 24], [3, 24, 7, 3], [3, 7, 24, 3], [3, 7, 24, 7], [3, 7, 3, 24], [3, 7, 3, 7]], [[4, 18, 25, 18], [4, 18, 25, 20], [4, 18, 23, 8], [4, 18, 23, 18], [4, 11, 13, 16], [4, 11, 13, 12], [4, 11, 22, 13], [4, 11, 22, 23]], [[5, 19, 5, 19], [5, 19, 5, 14], [5, 19, 14, 17], [5, 19, 14, 4], [5, 14, 17, 4], [5, 14, 17, 15], [5, 14, 4, 18], [5, 14, 4, 11]], [[6, 4, 18, 25], [6, 4, 18, 23], [6, 4, 11, 13], [6, 4, 11, 22], [6, 13, 16, 18], [6, 13, 16, 13], [6, 13, 12, 4], [6, 13, 12, 13]], [[7, 24, 3, 24], [7, 24, 3, 7], [7, 24, 7, 24], [7, 24, 7, 3], [7, 3, 24, 3], [7, 3, 24, 7], [7, 3, 7, 24], [7, 3, 7, 3]], [[8, 26, 13, 16], [8, 26, 13, 12], [8, 26, 23, 8], [8, 26, 23, 18], [8, 23, 8, 26], [8, 23, 8, 23], [8, 23, 18, 25], [8, 23, 18, 23]], [[9, 25, 18, 25], [9, 25, 18, 23], [9, 25, 20, 25], [9, 25, 20, 18], [9, 20, 25, 18], [9, 20, 25, 20], [9, 20, 18, 25], [9, 20, 18, 23]], [[10, 22, 13, 16], [10, 22, 13, 12], [10, 22, 23, 8], [10, 22, 23, 18], [10, 23, 8, 26], [10, 23, 8, 23], [10, 23, 18, 25], [10, 23, 18, 23]], [[11, 13, 16, 18], [11, 13, 16, 13], [11, 13, 12, 4], [11, 13, 12, 13], [11, 22, 13, 16], [11, 22, 13, 12], [11, 22, 23, 8], [11, 22, 23, 18]], [[12, 4, 18, 25], [12, 4, 18, 23], [12, 4, 11, 13], [12, 4, 11, 22], [12, 13, 16, 18], [12, 13, 16, 13], [12, 13, 12, 4], [12, 13, 12, 13]], [[13, 16, 18, 25], [13, 16, 18, 23], [13, 16, 13, 16], [13, 16, 13, 12], [13, 12, 4, 18], [13, 12, 4, 11], [13, 12, 13, 16], [13, 12, 13, 12]], [[14, 17, 4, 18], [14, 17, 4, 11], [14, 17, 15, 19], [14, 17, 15, 5], [14, 4, 18, 25], [14, 4, 18, 23], [14, 4, 11, 13], [14, 4, 11, 22]], [[15, 19, 5, 19], [15, 19, 5, 14], [15, 19, 14, 17], [15, 19, 14, 4], [15, 5, 19, 5], [15, 5, 19, 14], [15, 5, 14, 17], [15, 5, 14, 4]], [[16, 18, 25, 18], [16, 18, 25, 20], [16, 18, 23, 8], [16, 18, 23, 18], [16, 13, 16, 18], [16, 13, 16, 13], [16, 13, 12, 4], [16, 13, 12, 13]], [[17, 4, 18, 25], [17, 4, 18, 23], [17, 4, 11, 13], [17, 4, 11, 22], [17, 15, 19, 5], [17, 15, 19, 14], [17, 15, 5, 19], [17, 15, 5, 14]], [[18, 25, 18, 25], [18, 25, 18, 23], [18, 25, 20, 25], [18, 25, 20, 18], [18, 23, 8, 26], [18, 23, 8, 23], [18, 23, 18, 25], [18, 23, 18, 23]], [[19, 5, 19, 5], [19, 5, 19, 14], [19, 5, 14, 17], [19, 5, 14, 4], [19, 14, 17, 4], [19, 14, 17, 15], [19, 14, 4, 18], [19, 14, 4, 11]], [[20, 25, 18, 25], [20, 25, 18, 23], [20, 25, 20, 25], [20, 25, 20, 18], [20, 18, 25, 18], [20, 18, 25, 20], [20, 18, 23, 8], [20, 18, 23, 18]], [[21, 25, 18, 25], [21, 25, 18, 23], [21, 25, 20, 25], [21, 25, 20, 18], [21, 18, 25, 18], [21, 18, 25, 20], [21, 18, 23, 8], [21, 18, 23, 18]], [[22, 13, 16, 18], [22, 13, 16, 13], [22, 13, 12, 4], [22, 13, 12, 13], [22, 23, 8, 26], [22, 23, 8, 23], [22, 23, 18, 25], [22, 23, 18, 23]], [[23, 8, 26, 13], [23, 8, 26, 23], [23, 8, 23, 8], [23, 8, 23, 18], [23, 18, 25, 18], [23, 18, 25, 20], [23, 18, 23, 8], [23, 18, 23, 18]], [[24, 3, 24, 3], [24, 3, 24, 7], [24, 3, 7, 24], [24, 3, 7, 3], [24, 7, 24, 3], [24, 7, 24, 7], [24, 7, 3, 24], [24, 7, 3, 7]], [[25, 18, 25, 18], [25, 18, 25, 20], [25, 18, 23, 8], [25, 18, 23, 18], [25, 20, 25, 18], [25, 20, 25, 20], [25, 20, 18, 25], [25, 20, 18, 23]], [[26, 13, 16, 18], [26, 13, 16, 13], [26, 13, 12, 4], [26, 13, 12, 13], [26, 23, 8, 26], [26, 23, 8, 23], [26, 23, 18, 25], [26, 23, 18, 23]]]) 

212 [{24, 3, 7}, {8, 26, 23}, {25, 18, 20}] 

213 """ 

214 liste_cycles=[] 

215 for liste in liste_chemins: 

216 for chemin in liste: 

217 if chemin[0]==chemin[3]: 

218 liste_cycles.append(chemin) 

219 return dedoublonner(liste_cycles) 

220 

221 

222def trinomes_parfaits(liste_cycles: list) -> list: 

223 """ 

224 Retourne la listes des set de groupes de 3 (cycles du graphe initial) 

225 

226 Pre-condition : liste_cycles est retournée par cycles_longueur_3(liste_chemins) 

227 Post-condition : retourne une liste d ensembles 

228 >>> trinomes_parfaits([{24, 3, 7}, {8, 26, 23}, {25, 18, 20}]) 

229 [{24, 3, 7}, {8, 26, 23}, {25, 18, 20}] 

230 """ 

231 grou_3=[] 

232 for chemin in liste_cycles: 

233 set_chemin=set(chemin) 

234 grou_3.append(set_chemin) 

235 #Suppression des doublons : 

236 groupes_3=[] 

237 for element in grou_3: 

238 if element not in groupes_3: 

239 groupes_3.append(element) 

240 return groupes_3 

241 

242 

243def dict_reduit(dictionnaire: dict, trios: list) -> dict: 

244 """ 

245 Affiche le dictionnaire initial, réduit des trios composés 

246 

247 - Pre-condition : dictionnaire est retourne par la fonction 

248 def cree_dict_classe_liste(dict_amis_numeros) 

249 trios est retourne par la fonction 

250 def trinomes_parfaits(cycles_longueur_3(liste_chemins)) 

251 - Post-condition : Retourne un dictionnaire ou les sommets et aretes faisant 

252 intervenir un eleve d un trio sont supprimes. 

253 Par exemple (dans notre cas) : 

254 {0: [15], 1: [13], 2: [17], 4: [11], 5: [19, 14], 6: [4, 13], 

255 9: [20], 10: [22], 11: [13, 22], 12: [4, 13], 13: [16, 12], 14: [17, 4], 

256 15: [19, 5], 16: [13], 17: [4, 15], 19: [5, 14], 21: [18], 22: [13]} 

257 >>> dict_reduit(cree_dict_classe_liste(dict_amis_numeros), [{24, 3, 7}, {8, 26, 23}, {25, 18, 20}]) 

258 {0: [11, 9], 1: [2, 4], 2: [1, 6], 4: [1, 22], 5: [25], 6: [22, 13], 9: [10], 10: [9], 11: [12, 6], 12: [11, 6], 13: [14, 1], 14: [1], 15: [22], 16: [22], 17: [12, 15], 19: [1], 21: [19], 22: [20]} 

259 """ 

260 sommets_trios=set() 

261 for groupe in trios: 

262 for element in groupe: 

263 sommets_trios.add(element) 

264 dictionnaire_sans_cycle=copy.deepcopy(dictionnaire) # Pour que le dictionnaire 

265 #d origine ne soit pas modifie 

266 for eleve in sommets_trios: # liste des eleves se trouvant 

267 # dans un cycle de longueur 3 

268 del dictionnaire_sans_cycle[eleve] #supprime la cle correspondante 

269 # c est a dire le sommet 

270 for liste in dictionnaire_sans_cycle.values(): # Supprime les arretes 

271 # menant a un eleve dans un trio 

272 for element in liste: 

273 if element in sommets_trios: 

274 liste.remove(element) 

275 return dictionnaire_sans_cycle 

276 

277 

278# La fonction ci-dessous est devenue inutile il me semble 

279#Il suffit d utiliser def trinomes_parfaits(liste_cycles): 

280def sommets_cycles_3(matrice: numpy.ndarray) -> list: 

281 """ 

282 Retourne la liste des sommets appartenant a un cycle de longueur 3 

283 """ 

284 n = len(matrice) 

285 matrice_chemins_3 = matrice @ matrice @ matrice 

286 liste_sommets_appartenant_cycles = [] 

287 for i in range(n): 

288 if matrice_chemins_3[i][i] != 0: 

289 liste_sommets_appartenant_cycles.append(i) 

290 return liste_sommets_appartenant_cycles 

291 

292 

293def creation_matrice_adj(graphe: dict) -> numpy.ndarray: 

294 """ 

295 Retourne la matrice d adjacence de grphe. 

296 

297 Precondition : graphe est de type dictionnaire. 

298 C est le dictionnaire du graphe des amis, ou les prenoms sont remplaces par 

299 des numeros (ici entre 0 et 26) 

300 Il n y a aucun prenom dans ce dictionnaire. 

301 Ce graphe se trouve dans le fichier donnees_Projet 

302 Post condition : cette fonction retourne un objet ndarray de numpy. 

303 """ 

304 n = len(graphe) 

305 matrice = zeros((n, n)) 

306 for sommet_ligne in graphe.keys(): 

307 i = sommet_ligne # Pour plus de clarte a la lecture 

308 for sommet_colonne in graphe.keys(): 

309 j = sommet_colonne # Pour plus de clarte a la lecture 

310 if sommet_colonne in graphe[sommet_ligne]: 

311 matrice[i][j] = 1 # Notation habituelle en Maths 

312 return matrice 

313 

314 

315def eleves_sans_amis(dictionnaire: dict) -> list: 

316 """ 

317 Cette fonction renvoie la liste des points isolés à partir d'un graphe 

318 

319 Entrée : un dictionnaire représentant un graphe 

320 Sortie : Une liste de sommets de degré nul ? (voir la terminologie) 

321 >>> eleves_sans_amis(dict_amis_numeros) 

322 [0, 3, 7, 16, 17, 18, 23] 

323 """ 

324 s = set() 

325 for k in dict_amis_numeros.values(): 

326 for e in k.keys(): 

327 s.add(e) 

328 dep = set() 

329 for k in dict_amis_numeros.keys(): 

330 dep.add(k) 

331 dep -= s 

332 liste_eleves_sans_amis = list(dep) 

333 return liste_eleves_sans_amis 

334 

335def recherche_binomes(matrice): 

336 """ 

337 Cette fonction retourne la liste des listes d eleves s etant mutuellement 

338 choisis par deux 

339 

340 Precondition : matrice est la matrice d adjacence complete du graphe de la 

341 classe matrice est de type : ndarray de numpy 

342 Postcondition : type retourné : liste de listes de deux numeros d eleves 

343 triees 

344 """ 

345 liste_binomes = [] 

346 for i in range(len(matrice)): 

347 for j in range(len(matrice)): 

348 if matrice[i][j] == 1 and matrice[j][i] == 1: 

349 liste_binomes.append([i, j]) 

350 for binome in liste_binomes: # Classer les numeros par ordre croissant 

351 binome.sort() 

352 # Ce qui suit sert a supprimer les doublons car toutes les listes 

353 # sont trouvees deux fois. 

354 new_binomes = [] 

355 for binome in liste_binomes: 

356 if binome not in new_binomes: 

357 new_binomes.append(binome) 

358 return new_binomes 

359 

360# La fonction ci-dessous est a peu pres realisee avec 

361# def cycles_longueur_3(liste_chemins): 

362def renvoyer_cycles(G: nx.classes.digraph.DiGraph) -> set: # Fonction a creer 

363 """ 

364 Le but de cette fonction est de faire une proposition sur les cycles non 

365 connectés au graphe. 

366 

367 Voir le test correspondant. 

368 """ 

369 s = set() # Ensemble vide 

370 return s 

371 

372def score_popularite(graphe: dict) -> list: 

373 """ 

374 Renvoie un tableau de listes contenant le score de popularité et 

375 d'inimitié de chacun. 

376 

377 - L'entrée est un graphe (au sens des dictionnaires) 

378 - La sortie est une liste 

379 >>> score_popularite({'Alice': {'Bob': 2, 'Eve': -1, 'Donald': 1}, \ 

380 'Bob': {'Alice': 2, 'Eve': -1, 'Donald': 1}, \ 

381 'Eve': {'Alice': 2, 'Bob': 1, 'Donald': -1}, \ 

382 'Donald': {'Bob': 2, 'Alice': 1, 'Eve': -1}}) 

383 [5, 5, -3, 1] 

384 """ 

385 d = dict() 

386 for nom in graphe: 

387 d[nom] = 0 

388 for nom in graphe.values(): 

389 for score in nom: 

390 d[score] += nom[score] 

391 return list(d.values()) 

392 

393exemple_graphe = lire_entree_json() 

394dict_eleves_numero = associer_eleves_numeros(exemple_graphe) 

395dict_amis_numeros = graphe_numerique(exemple_graphe, dict_eleves_numero) 

396 

397dictionnaire=cree_dict_classe_liste(dict_amis_numeros) 

398liste_chemins=tous_les_chemins_long_3(dictionnaire) 

399trios=trinomes_parfaits(cycles_longueur_3(liste_chemins)) 

400G_petit=cree_graphe_nx(dict_reduit(dictionnaire,trios)) 

401 

402def run(): 

403 """ 

404 La fonction qui éxécute le code 

405 >>> run() 

406 """ 

407 afficher_graphe(exemple_graphe,'graphe_initial.png') 

408 afficher_graphe(dict_reduit(dictionnaire,trios),'graphe_petit.png') 

409 

410 with open('resultat.txt','w') as fichier: 

411 fichier.write(f"{sommets_cycles_3(creation_matrice_adj(dict_amis_numeros))} \n \ 

412 {liste_chemins} \n \ 

413 tous les cycles de longueur 3 {cycles_longueur_3(liste_chemins)} \n \ 

414 trios {trios} \n \ 

415 dictionnaire reduit: {dict_reduit(dictionnaire,trios)}" 

416 ) 

417 return None 

418 

419if __name__ == '__main__': 

420 run()