# Copyright 2019 Justin Baum
# tsp-single-file.py
# Python3
# Needs networkx(pip3 install networkx)
# Needs plotly(pip3 install plotly)
# To run, (python3 single_fine_tsp.py)
import networkx as nx
import matplotlib.pyplot as plt
import time
import random
count = 1
def showGraph(V, matrix, walk):
global count
X = nx.Graph()
plt.close()
X.add_nodes_from(V.keys())
E =genedges(matrix, walk)
X.add_edges_from(E)
Elabels =genedgelabels(matrix, walk)
nx.draw_networkx_edge_labels(X, V, edge_labels=Elabels, font_color='red', font_size=10)
nx.draw(X, V, with_labels=True)
plt.savefig('fig'+str(count)+'.png')
count += 1
def main():
V = gennodes(12)
matrix = makematrix(V)
nnwalk = _nearestneighbor(matrix)
weight = _getweight(nnwalk, matrix)
showGraph(V, matrix, nnwalk)
i = 0
globali = 0
while i < 400000 and globali < 2000000:
i += 1
globali += 1
walk = nnwalk[:]
threeoptswap(walk)
tweight = _getweight(walk, matrix)
if weight > tweight:
nnwalk = walk[:]
weight = tweight
showGraph(V, matrix, nnwalk)
i = 0
return
## UTILITIES
def gennodes(n, size = 200):
graph = {}
for i in range(n):
x = random.randint(0, size)
y = random.randint(0,size)
graph[i] = (x,y)
return graph
def makematrix(V):
m = len(V)
matrix = [[0 for i in range(m)] for j in range(m)]
for node in V:
for neighbor in V:
point1 = V[node]
point2 = V[neighbor]
matrix[node][neighbor] = int(dist(point1, point2)**0.5)
return matrix
def genedgelabels(matrix, walk):
prev = 0
edges = {}
for step in walk:
edges[(prev, step)] = matrix[prev][step]
prev = step
edges[(prev, 0)] = matrix[prev][0]
return edges
def genedges(matrix, walk):
prev = 0
edges = []
for step in walk:
edges.append([prev, step])
prev = step
edges.append([prev, 0])
return edges
def dist(point1, point2):
return (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2
def threeoptswap(walk):
x = random.randint(0, len(walk)-1)
y = random.randint(0, len(walk)-1)
z = random.randint(0, len(walk)-1)
temp = walk[x]
walk[x] = walk[y]
walk[y] = walk[z]
walk[z] = temp
return
def _nearestneighbor(matrix):
m = len(matrix)
for row in matrix:
assert(m == len(row))
prev = 0
walk = []
unvisited = list(range(m))[1:]
while len(unvisited) > 0:
min = float("inf")
curr = 0
for leg in unvisited:
leglength = matrix[prev][leg]
if leglength < min:
min = leglength
curr = leg
walk.append(curr)
unvisited.remove(curr)
return walk
def _getweight(walk, matrix):
prev = 0
weight = 0
for dest in walk:
weight += matrix[prev][dest]
prev = dest
weight += matrix[prev][0]
return weight
if __name__ == "__main__":
main()