# Offset Points

here’s my graph, not sure if the way i created plolycurves will affect the result? everytime i run it it’s generating diffrent indeces…

python:
`import System
import sys
pf_path = System.Environment.GetFolderPath(System.Environment.SpecialFolder.ProgramFilesX86)
sys.path.append(’%s\IronPython 2.7\Lib’ % pf_path)

import math
import random
from cStringIO import StringIO

sys.stdout = StringIO()

def distL2((x1,y1), (x2,y2)):
“”"Compute the L2-norm (Euclidean) distance between two points.

``````The distance is rounded to the closest integer, for compatibility
with the TSPLIB convention.

The two points are located on coordinates (x1,y1) and (x2,y2),
sent as parameters"""
xdiff = x2 - x1
ydiff = y2 - y1
return int(math.sqrt(xdiff*xdiff + ydiff*ydiff) + .5)
``````

def distL1((x1,y1), (x2,y2)):
“”"Compute the L1-norm (Manhattan) distance between two points.

``````The distance is rounded to the closest integer, for compatibility
with the TSPLIB convention.

The two points are located on coordinates (x1,y1) and (x2,y2),
sent as parameters"""
return int(abs(x2-x1) + abs(y2-y1)+.5)
``````

def mk_matrix(coord, dist):
“”"Compute a distance matrix for a set of points.

``````Uses function 'dist' to calculate distance between
any two points.  Parameters:
-coord -- list of tuples with coordinates of all points, [(x1,y1),...,(xn,yn)]
-dist -- distance function
"""
n = len(coord)
D = {}      # dictionary to hold n times n matrix
for i in range(n-1):
for j in range(i+1,n):
(x1,y1) = coord[i]
(x2,y2) = coord[j]
D[i,j] = dist((x1,y1), (x2,y2))
D[j,i] = D[i,j]
return n,D
``````

“basic function for reading a TSP problem on the TSPLIB format”
“NOTE: only works for 2D euclidean or manhattan distances”
f = open(filename, ‘r’);

``````line = f.readline()
while line.find("EDGE_WEIGHT_TYPE") == -1:

if line.find("EUC_2D") != -1:
dist = distL2
elif line.find("MAN_2D") != -1:
dist = distL1
else:
print "cannot deal with non-euclidean or non-manhattan distances"
raise Exception

while line.find("NODE_COORD_SECTION") == -1:

xy_positions = []
while 1:
if line.find("EOF") != -1: break
(i,x,y) = line.split()
x = float(x)
y = float(y)
xy_positions.append((x,y))

n,D = mk_matrix(xy_positions, dist)
return n, xy_positions, D
``````

def mk_closest(D, n):
“”"Compute a sorted list of the distances for each of the nodes.

``````For each node, the entry is in the form [(d1,i1), (d2,i2), ...]
where each tuple is a pair (distance,node).
"""
C = []
for i in range(n):
dlist = [(D[i,j], j) for j in range(n) if j != i]
dlist.sort()
C.append(dlist)
return C
``````

def length(tour, D):
“”“Calculate the length of a tour according to distance matrix ‘D’.”""
z = D[tour[-1], tour[0]] # edge from last to first city of the tour
for i in range(1,len(tour)):
z += D[tour[i], tour[i-1]] # add length of edge from city i-1 to i
return z

def randtour(n):
“”“Construct a random tour of size ‘n’.”""
sol = range(n) # set solution equal to [0,1,…,n-1]
random.shuffle(sol) # place it in a random order
return sol

def nearest(last, unvisited, D):
“”“Return the index of the node which is closest to ‘last’.”""
near = unvisited[0]
min_dist = D[last, near]
for i in unvisited[1:]:
if D[last,i] < min_dist:
near = i
min_dist = D[last, near]
return near

def nearest_neighbor(n, i, D):

``````Uses the Nearest Neighbor heuristic to construct a solution:
- start visiting city i
- while there are unvisited cities, follow to the closest one
"""
unvisited = range(n)
unvisited.remove(i)
last = i
tour = [i]
while unvisited != []:
next = nearest(last, unvisited, D)
tour.append(next)
unvisited.remove(next)
last = next
``````

def exchange_cost(tour, i, j, D):
“”"Calculate the cost of exchanging two arcs in a tour.

``````Determine the variation in the tour length if
arcs (i,i+1) and (j,j+1) are removed,
and replaced by (i,j) and (i+1,j+1)
(note the exception for the last arc).

Parameters:
-t -- a tour
-i -- position of the first arc
-j>i -- position of the second arc
"""
n = len(tour)
a,b = tour[i],tour[(i+1)%n]
c,d = tour[j],tour[(j+1)%n]
return (D[a,c] + D[b,d]) - (D[a,b] + D[c,d])
``````

def exchange(tour, tinv, i, j):
“”"Exchange arcs (i,i+1) and (j,j+1) with (i,j) and (i+1,j+1).

``````For the given tour 't', remove the arcs (i,i+1) and (j,j+1) and
insert (i,j) and (i+1,j+1).

This is done by inverting the sublist of cities between i and j.
"""
n = len(tour)
if i>j:
i,j = j,i
assert i>=0 and i<j-1 and j<n
path = tour[i+1:j+1]
path.reverse()
tour[i+1:j+1] = path
for k in range(i+1,j+1):
tinv[tour[k]] = k
``````

def improve(tour, z, D, C):
“”"Try to improve tour ‘t’ by exchanging arcs; return improved tour length.

``````If possible, make a series of local improvements on the solution 'tour',
using a breadth first strategy, until reaching a local optimum.
"""
n = len(tour)
tinv = [0 for i in tour]
for k in range(n):
tinv[tour[k]] = k  # position of each city in 't'
for i in range(n):
a,b = tour[i],tour[(i+1)%n]
dist_ab = D[a,b]
improved = False
for dist_ac,c in C[a]:
if dist_ac >= dist_ab:
break
j = tinv[c]
d = tour[(j+1)%n]
dist_cd = D[c,d]
dist_bd = D[b,d]
delta = (dist_ac + dist_bd) - (dist_ab + dist_cd)
if delta < 0:       # exchange decreases length
exchange(tour, tinv, i, j);
z += delta
improved = True
break
if improved:
continue
for dist_bd,d in C[b]:
if dist_bd >= dist_ab:
break
j = tinv[d]-1
if j==-1:
j=n-1
c = tour[j]
dist_cd = D[c,d]
dist_ac = D[a,c]
delta = (dist_ac + dist_bd) - (dist_ab + dist_cd)
if delta < 0:       # exchange decreases length
exchange(tour, tinv, i, j);
z += delta
break
return z
``````

def localsearch(tour, z, D, C=None):
“”"Obtain a local optimum starting from solution t; return solution length.

``````Parameters:
tour -- initial tour
z -- length of the initial tour
D -- distance matrix
"""
n = len(tour)
if C == None:
C = mk_closest(D, n)     # create a sorted list of distances to each node
while 1:
newz = improve(tour, z, D, C)
if newz < z:
z = newz
else:
break
return z
``````

def multistart_localsearch(k, n, D, report=None):
“”"Do k iterations of local search, starting from random solutions.

``````Parameters:
-k -- number of iterations
-D -- distance matrix
-report -- if not None, call it to print verbose output

Returns best solution and its cost.
"""
C = mk_closest(D, n) # create a sorted list of distances to each node
bestt=None
bestz=None
for i in range(0,k):
tour = randtour(n)
z = length(tour, D)
z = localsearch(tour, z, D, C)
if z < bestz or bestz == None:
bestz = z
bestt = list(tour)
if report:
report(z, tour)

return bestt, bestz
``````

“”“Local search for the Travelling Saleman Problem: sample usage.”""

coord = [(p.X, p.Y) for p in IN[0] ]
n, D = mk_matrix(coord, distL2) # create the distance matrix
instance = “toy problem”

# function for printing best found solution when it is found

from time import clock
init = clock()
def report_sol(obj, s=""):
print “cpu:%g\tobj:%g” %
(clock(), obj)

print “*** travelling salesman problem ***”

# random construction

print “random construction + local search:”
tour = randtour(n) # create a random tour
z = length(tour, D) # calculate its length
print “random:”, z, ’ --> ',
z = localsearch(tour, z, D) # local search starting from the random tour
print z

# greedy construction

print “greedy with nearest neighbor + local search:”
for i in xrange(5):
tour = nearest_neighbor(n, i, D) # create a greedy tour, visiting city ‘i’ first
z = length(tour, D)
print “nneigh attempt %i:” % i, z, ’ --> ',
z = localsearch(tour, z, D)
print z
print

# multi-start local search

print “random start local search:”
niter = 10
tour,z = multistart_localsearch(niter, n, D, report_sol)
assert z == length(tour, D)
print “best found (%i iterations): z = %g” % (niter, z)

sys.stdout.seek(0)
OUT = tour`

code from here: Connect the dots