|
Graph Convolutional Branch and Bound v1.0.0
A TSP solver that combines a graph convolutional network with a 1-Tree branch-and-bound.
|
Functions | |
| def | compute_prob (net, config, dtypeLong, dtypeFloat) |
| def | write_adjacency_matrix (graph, y_probs, x_edges_values, nodes_coord, filepath, num_nodes, kmedoids_labels=None) |
| def | add_dummy_cities (num_nodes, model_size) |
| def | create_temp_file (num_nodes, str_grap) |
| def | cluster_nodes (graph, k) |
| def | fix_instance_size (graph, num_nodes, model_size=100) |
| def | get_instance (num_nodes) |
| def | main (filepath, num_nodes, model_size) |
Variables | |
| category | |
| sys | filepath = sys.argv[1] |
| int | num_nodes = int(sys.argv[2]) |
| int | model_size = int(sys.argv[3]) |
@file main.py
@author Lorenzo Sciandra
@brief A recombination of code take from: https://github.com/chaitjo/graph-convnet-tsp.
Some functions were created for the purpose of the paper.
@version 1.0.0
@data 2024-05-1
@copyright Copyright (c) 2024, license MIT
Repo: https://github.com/LorenzoSciandra/GraphConvolutionalBranchandBound
| def main.add_dummy_cities | ( | num_nodes, | |
| model_size | |||
| ) |
This function adds dummy cities to the graph instance. The dummy cities are randomly generated are
added to the graph instance and the new instance is saved in a temporary file.
Args:
num_nodes: The number of nodes of the graph instance.
model_size: The size of the Graph Convolutional Network to use.
| def main.cluster_nodes | ( | graph, | |
| k | |||
| ) |
| def main.compute_prob | ( | net, | |
| config, | |||
| dtypeLong, | |||
| dtypeFloat | |||
| ) |
This function computes the probability of the edges being in the optimal tour, by running the GCN.
Args:
net: The Graph Convolutional Network.
config: The configuration file, from which the parameters are taken.
dtypeLong: The data type for the long tensors.
dtypeFloat: The data type for the float tensors.
Returns:
y_probs: The probability of the edges being in the optimal tour.
x_edges_values: The distance between the nodes.
| def main.create_temp_file | ( | num_nodes, | |
| str_grap | |||
| ) |
| def main.fix_instance_size | ( | graph, | |
| num_nodes, | |||
model_size = 100 |
|||
| ) |
The function that fixes the instance size with clustering.
It applies the k-medoids clustering to the graph and creates a new instance with the medoids as the new nodes.
Args:
graph: The graph to fix.
num_nodes: The number of nodes of the graph instance.
model_size: The size of the Graph Convolutional Network to use.
| def main.get_instance | ( | num_nodes | ) |
| def main.main | ( | filepath, | |
| num_nodes, | |||
| model_size | |||
| ) |
The function that runs the Graph Convolutional Network and writes the adjacency matrix to a file
for the given input instance.
Args:
filepath: The path to the file where the adjacency matrix will be written.
num_nodes: The number of nodes in the TSP instance.
model_size: The size of the Graph Convolutional Network to use.
| def main.write_adjacency_matrix | ( | graph, | |
| y_probs, | |||
| x_edges_values, | |||
| nodes_coord, | |||
| filepath, | |||
| num_nodes, | |||
kmedoids_labels = None |
|||
| ) |
This function writes the adjacency matrix to a file.
The file is in the format:
cities: (x1, y1);(x2, y2);...;(xn, yn)
adjacency matrix:
(0.0, 0.0);(0.23, 0.9);...;(0.15, 0.56)
...
(0.23, 0.9);(0.3, 0.59);...;(0.0, 0.0)
where each entry is (distance, probability)
If needed adjusts the size of the graph when the model size is different from the number of nodes in the instance.
Args:
graph: The set of nodes in the graph.
y_probs: The probability of the edges being in the optimal tour.
x_edges_values: The weight of the edges.
nodes_coord: The nodes coordinates used in the GCN.
filepath: The path to the file where the adjacency matrix will be written.
num_nodes: The number of nodes in the TSP instance.
kmedoids_labels: The labels of the k-medoids clustering.
1.9.6