TSP in python ; this is code to solve tsp whenever called, where given coordinates as in name of pos and then start coordinate as in start, help me how it works ?

Qurrat ul Ainy qurratul.ainy1 at gmail.com
Thu Mar 17 13:49:06 EDT 2016


from os import system, getcwd, chdir

def tsp_generate_hops(pos, start, length):
   hops = []
   tour = solve_tsp(pos)
   c = -1
   for hop in tsp_hop_gen(tour, start):
      c += 1
      hops.append(hop)
      if c == length:
         break
   return hops

def solve_tsp(data):
   old_cwd = getcwd()
   chdir('/tmp')
   data_len = len(data)
   f = file('tmp.tsp', 'w')
   f.write('TYPE : TSP\nDIMENSION: %d\nEDGE_WEIGHT_TYPE : EUC_2D\nNODE_COORD_SECTION\n' % data_len)
   for i in range(0, len(data)):
      entry = data[i]
      f.write('%d %f %f\n' % (i + 1, entry[0], entry[1]))
   f.write('EOF\n')
   f.close()
   try:
      system('concorde tmp.tsp > /dev/null')
      tour = []
      for line in file('tmp.sol').readlines()[1:]:
         for value in line.strip().split(' '):
            tour.append(int(value))
   except:
      raise RuntimeError('could not compute TSP')
   chdir(old_cwd)
   return tour

def tsp_hop_gen(tour, start):
   '''
   hop generator based on tsp solved tour,
   starting at the given start hop
   '''
   y = False
   for hop in tour:
      if hop == start:
         y = True
      if y:
         yield hop
   while True:
      for hop in tour:
         yield hop



More information about the Python-list mailing list