"""
Approximating TSP using fast MST-Algorithms
Copyright 2020, University of Freiburg
Philipp Schneider
"""
import heapq # noqa
import math # noqa
from AdjacencyMatrix import AdjacencyMatrix # noqa
from networkx.utils.union_find import UnionFind # noqa
def compute_tour(am):
'''
computes a tour which as an array tour[0],...,tour[n-1]
containing the nodes {0,...,n-1}) of a graph given as
Adjacency matrix that has a small sum of edge weights of
a roundtrip defined as:
w(tour[0],tour[1]) + ...
+ w(tour[n-2],tour[n-1])
+ w(tour[n-1],tour[0])
the guarantee is that the weight of the computed tour
is at most twice that of the best possible tour.
Parameter:
am - Instance of AdjacencyMatrix
Returns:
an array of size n representing the order in which
nodes are visited (in a roundtrip)
'''
def tour_weight(am, tour):
'''
computes the sum of edge weigths when all nodes of a
tour are visited as a roundtrip
Parameter:
am - Instance of AdjacencyMatrix of size n
tour - permuation of {0,...,n-1}
Returns:
the following value rounded to two decimal places
w(tour[0],tour[1]) + ...
+ w(tour[n-1],tour[n-1])
+ w(tour[n-1],tour[0])
'''
n = am.node_size()
weight_sum = 0
for i in range(n-1):
weight_sum += am.get_weight(tour[i], tour[i + 1])
weight_sum += am.get_weight(tour[n-1], tour[0])
return round(weight_sum, 2)
def read_graph_from_file(filename):
'''
reads a complete weighted graph from a file (that must
be loated in same folder) and creates an adjacency matrix
from it
Parameter:
filename - name of file
Returns:
instance of AdjacencyMatrix representing the file
'''
with open(filename) as input:
lines = input.read().splitlines()
# first line contains the number of nodes
am = AdjacencyMatrix(int(lines[0]))
# other lines contain edges seperated by a whitespace
for i in range(0, len(lines) - 1):
for j in range(am.node_size()):
entries = lines[i + 1].split(' ')
am.set_weight(i, j, float(entries[j]))
return am