Newer
Older
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
import numpy as np
import math
import argparse
import sys
import os
parser = argparse.ArgumentParser(description="LEPL1503 - Détection et correction d'erreurs")
parser.add_argument("input_file", help="Nom du fichier contenant les données nécessaires")
parser.add_argument("-f", help="Chemin vers le fichier de sortie", type=argparse.FileType("wb"), default=sys.stdout)
parser.add_argument("-v", help="\"verbose\" mode: si ajouté, affiche des informations sur l'exécution du programme", action="store_true")
args = parser.parse_args()
verbose = args.v
output_fd = args.f
nb_nodes = None
nb_edges = None
if verbose:
print(args, file=sys.stderr)
def get_file_infos(data):
nb_nodes = int.from_bytes(data[0:4], "big",signed=True)
nb_edges = int.from_bytes(data[4:], "big",signed=True)
return nb_nodes,nb_edges
def bellman_ford(table,s):
dist = [math.inf]*nb_nodes
dist[s]=0
path = [-1]*nb_nodes
for _ in range(nb_nodes-1):
for j in range(len(table)):
a,b,cab = table[j][0],table[j][1],table[j][2]
if(dist[a]!=math.inf and dist[b]>dist[a]+cab):
dist[b]=dist[a]+cab
path[b]=a
for j in range(len(table)):
a,b,cab = table[j][0],table[j][1],table[j][2]
if(dist[a]!=math.inf and dist[b]>dist[a]+cab):
print("Cycle négatif détecté")
return -1, -1
return dist, path
def get_path(dest, path,source):
r = [dest]
i = dest
while(True):
if (i ==source):
break
r.insert(0,path[i])
i = path[i]
return r
def get_max(dist,s):
max = -math.inf
n = s
for i in range(len(dist)):
if(i!=s and dist[i]!=math.inf and dist[i]>=max):
max = dist[i]
n=i
if(max==-math.inf):
if(dist[s]!=math.inf and dist[s]>=max):
max = dist[s]
return max,n
if __name__ == "__main__":
with open(args.input_file, "rb") as input_file:
binary_data = input_file.read()
nb_nodes, nb_edges = get_file_infos(binary_data[:8])
if verbose:
print("Number of nodes :", nb_nodes, ", number of links :", nb_edges)
binary_data = binary_data[8:]
table = []
if output_fd == sys.stdout or output_fd == sys.stderr:
print(nb_nodes)
else :
output_fd.write(nb_nodes.to_bytes(4, "big"))
for i in range(nb_edges):
a = int.from_bytes(binary_data[i*16:i*16+4],"big",signed=True)
b = int.from_bytes(binary_data[i*16+4:i*16+8],"big",signed=True)
cab = int.from_bytes(binary_data[i*16+8:i*16+12],"big",signed=True)
cba = int.from_bytes(binary_data[i*16+12:i*16+16],"big",signed=True)
if (cab !=0):
l1 = [a,b,cab]
table.append(l1)
if(cba!=0):
l2 = [b,a,cba]
table.append(l2)
for i in range(nb_nodes):
dist, path = bellman_ford(table,i)
if dist ==-1 : break
if output_fd == sys.stdout or output_fd == sys.stderr:
print("source : "+str(i))
d,n = get_max(dist,i)
print("destination : "+ str(n))
print("cout : "+ str(d))
p = get_path(n,path,i)
print("nombre de noeuds : "+str(len(p)))
print("chemin : "+" ".join(str(x) for x in p))
print("-----------------------")
else :
output_fd.write(i.to_bytes(4, "big"))
d,n = get_max(dist,i)
output_fd.write(n.to_bytes(4, "big",signed=True))
output_fd.write(d.to_bytes(4, "big",signed=True))
r = get_path(n,path,i)
output_fd.write(len(r).to_bytes(4, "big",signed=True))
for j in range(len(r)) :
output_fd.write(r[j].to_bytes(4, "big"))