shortest_path.py

import math

import argparse
import sys


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é")
            dist = [math.inf] * nb_nodes
            dist[s] = 0
            path = [-1] * nb_nodes
    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*12:i*12+4], "big", signed=True)
            b = int.from_bytes(binary_data[i*12+4:i*12+8], "big", signed=True)
            cab = int.from_bytes(
                binary_data[i*12+8:i*12+12], "big", signed=True)
            l1 = [a, b, cab]
            table.append(l1)
        for i in range(nb_nodes):
            dist, path = bellman_ford(table, i)
            if dist == -1:
                continue  # TODO: if there is no shortest path (negative cycle or empty path), put a 0 value instead of not showing it at all

            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(d.to_bytes(4, "big", signed=True))
                output_fd.write(n.to_bytes(4, "big"))
                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"))