-
Notifications
You must be signed in to change notification settings - Fork 0
/
fichier_graphe_non_oriente_sym.py
116 lines (89 loc) · 3.16 KB
/
fichier_graphe_non_oriente_sym.py
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
import random
import numpy as np
####nombre de sommets
N= 8
INF = float('inf')
R=50000000
####definir la matrice d'adjacence
def p(i,j):
p = random.randint(1,R)
return 0 if p > 3*R/4 else p
#test
# for i in range(10):
# print(p(0,4))
A = [ [ p(i,j) for j in range(N)] for i in range(N)]
#avoir une matrice symétrique à coeff diagonaux nulls
for i in range(N):
A[i][i]=0
for j in range(i):
A[i][j] = A[j][i]
#aucun noeud ne doit être isolé
nb = 0
for i in range (len(A)):
if N-A[i].count(0)<1 : #si le noeuds est isolé
try:
noeuds_choisi = random.randint(i+1,N-1)
except:
noeuds_choisi = random.randint(1,i)
poids_choisi = random.randint(1,50)
A[i][noeuds_choisi] = A[noeuds_choisi][i] = poids_choisi
nb+= N-A[i].count(0)
def afficher_matrice(A):
for i in range(len(A)):
for j in range(len(A[0])):
str = (2 + int(np.log(R)/np.log(10))- int(np.log(A[i][j])/np.log(10)) ) * " " if A[i][j]!=0 else (2+ int(np.log(R)/np.log(10)))*" "
print(A[i][j],end=str)
print("\n")
print("\n")
afficher_matrice(A)
print("nbInt={} sur {} elements ".format(nb,len(A)**2), end = "\n\n")
Matrice_Adjacence = A
afficher_matrice(Matrice_Adjacence)
####sommet de départ
sommet_depart = 0
print("sommet de départ= ",sommet_depart,end = "\n\n")
def PCC(A,s): #A est une matrice (n,n) et s, un entier entre 0 et len(A)-1
#des vérifications
B = np.array(A)
if (B != np.transpose(B)).any():
print("matrice d'adjacence non symétrique")
return
if s not in range(0,len(A)):
print("sommet inexistant")
return
if (B.diagonal()!=0).any():
print("retranchez les valeurs des diagonales")
return
#des initialisations
λ = [INF for i in range(len(A))] #liste des distances à s
λ[s] = 0
Q = [s] #liste des sommets en cours
D = [] #liste des sommets déjà visités
while len(Q)!=0:
print(λ)
#identifier le sommet courant
distance_min = INF; sommet_courant=0;
for somet in Q:
if λ[somet] < distance_min:
distance_min = λ[somet]
sommet_courant = somet
break
#enlever le sommet couant de la liste des sommets à visitet
print("\n")
print("tentative d'enlever {} de Q".format(sommet_courant))
Q.remove(sommet_courant); print("opération réussie: distance min entre {} et {} touvé = {}".format(s,sommet_courant,distance_min))
D.append(sommet_courant)
#actualiser les distances
liste_poids_successeurs = A[sommet_courant]
for sommet_sucesseur in range(len(liste_poids_successeurs)):
if liste_poids_successeurs[sommet_sucesseur]!=0:
#ajouter le sommet à liste des sommets à visiter
if sommet_sucesseur not in Q and sommet_sucesseur not in D:
Q.append(sommet_sucesseur)
print("le sommet {} a été ajouté".format(sommet_sucesseur))
#voir si la distance à s est plus petite quand on passe par le sommet courant
distance = λ[sommet_sucesseur]
distance_passant_par_s = distance_min + A[sommet_courant][sommet_sucesseur]
λ[sommet_sucesseur] = min(distance, distance_passant_par_s)
return λ
print(PCC(Matrice_Adjacence,sommet_depart) ,end="\n\n")