"""
Approximating TSP using fast MST-Algorithms
Copyright 2020, University of Freiburg
Philipp Schneider
"""
import heapq
import math
from AdjacencyMatrix import AdjacencyMatrix
import matplotlib.pyplot as plt
import networkx as nx
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)
Unit Tests:
Since main funcitonality is outsoruced to suprocedures
mst() and pre_order, we give unit test there
'''
# first compute the mst
tree = mst(am)
result = []
# pre-order traversal of mst, where nodes add themselves to result
pre_order(tree, 0, result)
return result
def mst(am):
'''
computes a minimum spanning tree for the given graph.
We employ Prim's algorithm for that task.
Parameter:
am - Instance of AdjacencyMatrix represnting the graph
Returns:
a tree given as an array containing at position i
a list of node i's children in the tree
Unit-Tests:
>>> n = 100
>>> cities_in_a_line = AdjacencyMatrix(n)
>>> for i in range(n):
... for j in range(n):
... cities_in_a_line.set_weight(i, j, abs(i-j))
>>> desired_mst = [[i+1] for i in range(n-1)]
>>> desired_mst.append([])
>>> mst(cities_in_a_line) == desired_mst
True
>>> n = 2**8
>>> cities_in_unit_hypercube = AdjacencyMatrix(n)
>>> def dist(i, j):
... x = i ^ j; setBits = 0
... while (x > 0):
... setBits += x & 1; x >>= 1
... return math.sqrt(setBits)
>>> for i in range(n):
... for j in range(n):
... cities_in_unit_hypercube.set_weight(i, j, dist(i,j))
>>> mst = mst(cities_in_unit_hypercube)
>>> mst_weight = 0
>>> for i in range(n):
... for j in mst[i]:
... mst_weight += cities_in_unit_hypercube.get_weight(i,j)
>>> mst_weight == n - 1
True
'''
# some notations making the subsequent code look a bit nicer
n = am.node_size()
insert = lambda heap, u, dist: heapq.heappush(heap, (dist, u)) # noqa
delete_min = lambda heap: heapq.heappop(heap)[1] # noqa
# h will be used as heap
h = []
# distance array, intially infinity for all nodes
d = [math.inf for v in range(n)]
# as it doesn't really matter here, we use node 0 as source
d[0] = 0
# array to store marks
marked = [False for v in range(n)]
# array to store the current parents
parent = [None for v in range(n)]
parent[0] = 0
# array containing at position i the list of children of node i
result_mst = [[] for v in range(n)]
# push all nodes to heap using distance as priority
for u in range(n):
insert(h, u, d[u])
# while h is not empty
while h:
u = delete_min(h)
if not marked[u]:
# for all neighbors of u
for v in range(n):
w = am.get_weight(u, v)
if not marked[v] and w < d[v] and v is not u:
d[v] = w
insert(h, v, d[v])
parent[v] = u
marked[u] = True
# add edge {u, parent[u]} to the mst
if u != 0:
result_mst[parent[u]].append(u)
return result_mst
def pre_order(tree, root, result):
'''
Pre-order traversal in a tree (not necessarily binary)
Parameter:
tree - a tree represented as array containing at
position i the list of children of node i
root - the node where to start the traversal
result - a list to which the current node adds itself
Unit Tests:
>>> line = [[1],[2],[3],[4],[]]
>>> result = []
>>> pre_order(line, 0, result)
>>> result
[0, 1, 2, 3, 4]
>>> full_tree = [[1, 2],[3, 4],[5, 6],[],[],[],[]]
>>> result = []
>>> pre_order(full_tree, 0, result)
>>> result
[0, 1, 3, 4, 2, 5, 6]
'''
result.append(root)
for v in tree[root]:
pre_order(tree, v, result)
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 tree_weight(am, tree):
'''
computes the sum of weights of edges of a tree
Parameter:
am - Instance of AdjacencyMatrix of size n
tree - a tree as adjacency list
Returns:
the weight of the tree rounded to two decimal places
'''
weight_sum = 0
for i in range(am.node_size()):
for j in tree[i]:
weight_sum += am.get_weight(i, j)
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
def draw(am, tour):
'''
draws the complete graph represented by AdjacencyMatrix
and the corresponding tour
Parameterts:
am - Adjacency matrix of the underlying graph
tour - list of nodes representing a tour
'''
n = am.node_size()
g = nx.Graph()
for i in range(n):
for j in range(n):
g.add_edge(i, j, weight=am.get_weight(i, j))
tour_edges = [(tour[i], tour[i+1]) for i in range(n-1)]
tour_edges.append((tour[n-1], tour[0]))
pos = nx.kamada_kawai_layout(g) # positions for all nodes
# nodes
nx.draw_networkx_nodes(g, pos, node_size=400)
# tour-edges
nx.draw_networkx_edges(g, pos, edgelist=tour_edges, width=6,
alpha=0.5, edge_color='r')
# labels
nx.draw_networkx_labels(g, pos, font_size=11)
plt.axis('off')
plt.show()