HybridSolver.py

Go to the documentation of this file.

"""
    @file: HybridSolver.py
    @author Lorenzo Sciandra
    @brief First it builds the program in C, specifying the number of nodes to use and whether it is in hybrid mode or not.
    Then it runs the graph conv net on the instance, and finally it runs the Branch and Bound.
    It can be run on a single instance or a range of instances.
    The input matrix is generated by the neural network and stored in the data folder. The output is stored in the results folder.
    @version 1.0.0
    @data 2024-05-1
    @copyright Copyright (c) 2024, license MIT
 
    Repo: https://github.com/LorenzoSciandra/GraphConvolutionalBranchandBound
"""
import subprocess
import argparse
import pprint as pp
import os
import time
import numpy as np
 
 
def adjacency_matrix(orig_graph):
    """
    Calculates the adjacency matrix of the graph.
    Args:
        orig_graph: The original graph.
 
    Returns:
        The adjacency matrix of the graph.
    """
    adj_matrix = np.zeros((len(orig_graph), len(orig_graph)))
 
    for i in range(0, len(orig_graph)):
        for j in range(i + 1, len(orig_graph)):
            adj_matrix[i][j] = np.linalg.norm(np.array(orig_graph[i]) - np.array(orig_graph[j]))
            adj_matrix[j][i] = adj_matrix[i][j]
 
    return adj_matrix
 
 
def create_temp_file(num_nodes, str_grap):
    """
    Creates a temporary file to store the current instance of the TSP for the neural network.
    Args:
        num_nodes: The number of nodes in the TSP instance.
        str_grap: The string representation of the graph.
    """
    filepath = "graph-convnet-tsp/data/hyb_tsp/test_" + str(num_nodes) + "_nodes_temp.txt"
 
    if not os.path.exists(os.path.dirname(filepath)):
        try:
            os.makedirs(os.path.dirname(filepath))
        except OSError as exc:  # Guard against race condition
            if exc.errno != errno.EEXIST:
                raise
 
    with open(filepath, 'w+') as file:
        file.writelines(str_grap)
        file.flush()
        os.fsync(file.fileno())
 
 
def get_nodes(graph):
    """
    From a graph, it returns the nodes in a string format.
    Args:
        graph: The graph to get the nodes from.
 
    Returns:
        The nodes in a string format.
    """
    nodes = ""
    i = 0
    for node in graph:
        nodes += "\t" + str(i) + " : " + str(node[0]) + " " + str(node[1]) + "\n"
        i += 1
 
    return nodes
 
 
def get_instance(instance, num_nodes):
    """
    Gets the instance of the TSP from the file.
    Args:
        instance: The instance to get.
        num_nodes: The number of nodes in the TSP instance.
 
    Returns:
        The graph in a list and string format.
    """
 
    lines = None
    file_path = "graph-convnet-tsp/data/hyb_tsp/test_" + str(num_nodes) + "_nodes.txt"
    with open(file_path, "r") as f:
        lines = f.readlines()
 
    if lines is None or len(lines) < instance - 1:
        raise Exception(
            "The instance " + str(instance) + " for the number of nodes " + str(num_nodes) + " does not exist.")
 
    str_graph = lines[instance - 1]
    orig_graph = str_graph
 
    if "output" in str_graph:
        str_graph = str_graph.split(" output")[0]
 
    str_graph = str_graph.replace("\n", "").strip()
    nodes = str_graph.split(" ")
    graph = [float(x) for x in nodes]
    graph = [[graph[i], graph[i + 1]] for i in range(0, len(graph), 2)]
 
    return graph, orig_graph
 
 
def build_c_program(build_directory, num_nodes, hyb_mode):
    """
    Builds the C program with the specified number of nodes and whether it is in hybrid mode or not.
    Args:
        build_directory: The directory where the CMakeLists.txt file is located and where the executable will be built.
        num_nodes: The number of nodes to use in the C program.
        hyb_mode: 1 if the program is in hybrid mode, 0 otherwise.
    """
    source_directory = "../"
    cmake_command = [
        "cmake",
        "-S" + source_directory,
        "-B" + build_directory,
        "-DCMAKE_BUILD_TYPE=Release",
        "-DMAX_VERTEX_NUM=" + str(num_nodes),
        "-DHYBRID=" + str(hyb_mode)
    ]
    # print(cmake_command)
    make_command = [
        "make",
        "-C" + build_directory,
        "-j"
    ]
    try:
        subprocess.check_call(cmake_command)
        subprocess.check_call(make_command)
    except subprocess.CalledProcessError as e:
        print("Build failed:")
        print(e.output)
        raise Exception("Build failed")
 
 
def hybrid_solver(num_instances, num_nodes, hyb_mode, gen_matrix):
    """
    The Graph Convolutional Branch-and-Bound Solver.
    Args:
        num_instances: The range of instances to run on the Solver.
        num_nodes: The number of nodes in each TSP instance.
        hyb_mode: True if the program is in hybrid mode, False otherwise.
        gen_matrix: True if the adjacency matrix is already generated, False otherwise.
    """
 
    model_size = 0
    adj_matrix = None
 
    if hyb_mode:
        if num_nodes <= 1:
            raise Exception("The number of nodes must be greater than 1.")
        elif num_nodes <= 20:
            model_size = 20
        elif num_nodes <= 50:
            model_size = 50
        else:
            model_size = 100
    else:
        model_size = num_nodes
 
    build_directory = "../cmake-build/CMakeFiles/BranchAndBound1Tree.dir"
    hybrid = 1 if hyb_mode else 0
    build_c_program(build_directory, num_nodes, hybrid)
 
    if "-" in num_instances:
        instances = num_instances.split("-")
        start_instance = 1 if int(instances[0]) == 0 else int(instances[0])
        end_instance = int(instances[1])
    else:
        start_instance = 1
        end_instance = int(num_instances)
 
    print("Starting instance: " + str(start_instance))
    print("Ending instance: " + str(end_instance))
 
    for i in range(start_instance, end_instance + 1):
        start_time = time.time()
        graph, str_graph = get_instance(i, num_nodes)
        input_file = "../data/AdjacencyMatrix/tsp_" + str(num_nodes) + "_nodes/tsp_test_" + str(i) + ".csv"
        absolute_input_path = os.path.abspath(input_file)
 
        if not os.path.exists(os.path.dirname(absolute_input_path)):
            try:
                os.makedirs(os.path.dirname(absolute_input_path))
            except OSError as exc:  # Guard against race condition
                if exc.errno != errno.EEXIST:
                    raise
 
        result_mode = "hybrid" if hyb_mode else "classic"
        output_file = "../results/AdjacencyMatrix/tsp_" + str(num_nodes) + "_nodes_" + result_mode \
                      + "/tsp_result_" + str(i) + ".txt"
 
        if hyb_mode:
            create_temp_file(num_nodes, str_graph)
            absolute_python_path = os.path.abspath("./graph-convnet-tsp/main.py")
            result = subprocess.run(
                ['python3', absolute_python_path, absolute_input_path, str(num_nodes), str(model_size)],
                cwd="./graph-convnet-tsp", check=True)
            if result.returncode == 0:
                print('Neural Network completed successfully on instance ' + str(i) + ' / ' + str(end_instance))
            else:
                print('Neural Network failed on instance ' + str(i) + ' / ' + str(end_instance))
 
        elif gen_matrix:
            adj_matrix = adjacency_matrix(graph)
            with open(absolute_input_path, "w") as f:
                nodes_coord = ";".join([f"({graph[i][0]}, {graph[i][1]})" for i in range(len(graph))])
                f.write(nodes_coord + "\n")
                for k in range(len(adj_matrix)):
                    for j in range(len(adj_matrix[k])):
                        f.write(f"({adj_matrix[k][j]}, 0);")
                    f.write("\n")
 
        absolute_output_path = os.path.abspath(output_file)
        if not os.path.exists(os.path.dirname(absolute_output_path)):
            try:
                os.makedirs(os.path.dirname(absolute_output_path))
            except OSError as exc:  # Guard against race condition
                if exc.errno != errno.EEXIST:
                    raise
        cmd = [build_directory + "/BranchAndBound1Tree", absolute_input_path, absolute_output_path]
        result = subprocess.run(cmd)
        if result.returncode == 0:
            print('Branch-and-Bound completed successfully on instance ' + str(i) + ' / ' + str(end_instance))
        else:
            print('Branch-and-Bound failed on instance ' + str(i) + ' / ' + str(end_instance))
 
        end_time = time.time()
        cities = get_nodes(graph)
 
        if hyb_mode:
            os.remove("graph-convnet-tsp/data/hyb_tsp/test_" + str(num_nodes) + "_nodes_temp.txt")
 
        with open(output_file, "a") as f:
            f.write("\nNodes: \n" + cities)
            f.write("\nTime taken: " + str(end_time - start_time) + "s\n")
            f.flush()
            os.fsync(f.fileno())
 
 
if __name__ == "__main__":
    """
    Args:
        --range_instances: The range of instances to run on the Solver.
        --num_nodes: The number of nodes in each TSP instance.
        --hybrid_mode: If present, the program is in hybrid mode, otherwise it is in classic mode.
    """
 
    parser = argparse.ArgumentParser()
    parser.add_argument("--range_instances", type=str, default="1-1")
    parser.add_argument("--num_nodes", type=int, default=20)
    parser.add_argument("--hybrid", action="store_true")
    opts = parser.parse_args()
 
    pp.pprint(vars(opts))
 
    gen_matrix = opts.hybrid == False
 
    hybrid_solver(opts.range_instances, opts.num_nodes, opts.hybrid, gen_matrix)