sp.py

import math
import argparse
import sys

# # Données de graph.h directement intégrées dans le code
# NB_NODES = 5
# NB_LINKS = 7

# LINKS = [
#     [2,0,1],
#     [0,1,2],
#     [0,3,3],
#     [0,4,1],
#     [1,2,-1],
#     [3,1,-2],
#     [3,4,5]
# ]


def get_file_infos(links):
    """
    Récupère les informations basiques du graphe : le nombre de noeuds et de liens.
    """
    nb_nodes = max(max(link[:2]) for link in links) + 1
    nb_edges = len(links)
    return nb_nodes, nb_edges


def bellman_ford(links, s, nb_nodes, verbose):
    """
    Exécute l'algorithme de Bellman-Ford avec comme noeud source `s`.
    Retourne un tableau de distances pour atteindre chaque noeud depuis `s`,
    ainsi que le chemin pour atteindre ces noeuds (tableau de précédence).
    Si le noeud est isolé ou qu'un cycle négatif est trouvé, retourne une distance
    infinie pour chaque autre noeud, et une distance de 0 pour `s`.
    """

    # Initialisation.
    dist = [math.inf] * nb_nodes
    dist[s] = 0  # Le noeud source est à distance 0 de lui-meme.
    path = [-1] * nb_nodes
    
    # Iteration de Bellman-Ford.
    for _ in range(nb_nodes-1):
        for j in range(len(links)):
            node_from, node_to, cost = links[j][0], links[j][1], links[j][2]
            if (dist[node_from] != math.inf and dist[node_to] > dist[node_from] + cost):
                dist[node_to] = dist[node_from] + cost
                path[node_to] = node_from
    
    # Detection de cycle negatif.
    for j in range(len(links)):
        node_from, node_to, cost = links[j][0], links[j][1], links[j][2]
        if (dist[node_from] != math.inf and dist[node_to] > dist[node_from] + cost):
            if verbose:
                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):
    """
    Retourne une liste contenant le chemin de `source` vers `dest`
    en utilisant le tableau de précédence `path`.
    """
    r = [dest]
    i = dest
    while i != source:
        r.insert(0, path[i])
        i = path[i]
    return r


def get_max(dist, s):
    """
    Retourne l'indice du noeud dont il existe un chemin de `s` vers ce noeud
    et le cout de ce chemin est le plus élevé parmis tous les noeuds ayant un chemin
    depuis `s`.
    """
    max_cost = -math.inf
    max_node = s
    for node_idx in range(len(dist)):
        if node_idx != s and dist[node_idx] != math.inf and dist[node_idx] >= max_cost:
            max_cost = dist[node_idx]
            max_node = node_idx
    if max_cost == -math.inf:
        if dist[s] != math.inf and dist[s] >= max_cost:
            max_cost = dist[s]

    return max_cost, max_node


def read_graph():
    """
    Récupère le graphe directement à partir des données définies dans le code.
    """
    global LINKS, NB_NODES
    nb_nodes, nb_edges = get_file_infos(LINKS)
    return LINKS, nb_nodes





if __name__ == "__main__":

    parser = argparse.ArgumentParser(
        description="LEPL1503 - Algorithme de plus court chemin")
    parser.add_argument(
        "input_file", help="chemin vers le fichier d'instance representant le graphe a traiter.")
    parser.add_argument("-f", help="chemin vers le fichier qui contiendra le resultat de programme, au format specifie dans l'enonce. Defaut : stdout.",
                        type=argparse.FileType("wb"), default=sys.stdout)
    parser.add_argument(
        "-v", help="autorise les messages de debug. Si ce n'est pas active, aucun message de ce type ne peut etre affiche, excepte les messages d'erreur en cas d'echec. Defaut : False.", action="store_true")
    args = parser.parse_args()

    verbose = args.v
    output_fd = args.f
    nb_nodes = None
    nb_edges = None

    if verbose:
        # Exemple de message que vous pouvez ecrire si le mode verbose est actif.
        print(args, file=sys.stderr)

    graph, nb_nodes = read_graph()
    if output_fd == sys.stdout or output_fd == sys.stderr:
        print("Nombre de noeuds: " + str(nb_nodes))
    else:
        output_fd.write(nb_nodes.to_bytes(4, "big"))
    
    for source in range(nb_nodes):
        dist, path = bellman_ford(graph, source, verbose)

        # Ces messages ne sont pas des messages de debug.
        # Ils peuvent donc etre affiches (uniquement si la sortie choisie est stdout ou stderr)
        # meme si le mode verbose n'est pas actif.
    dist, path = bellman_ford(graph, source, verbose)

    for i in range(nb_nodes):
        print(f"Distance to node {i} : {dist[i]}")
        print(f"Path to node {i} : {path[i]}")