Untitled

Views: 622

Anonymous   3 years ago   Never
Text   2.47 KB   Public
Crumb Tree
  • Untitled
Highlight mode ON

Click on the lines you want to highlight and share this url.

    Download   RAW   Copy   Fork
  1. import sys
  2. import math
  3. from collections import defaultdict
  4. sys.path.append('../')
  5. import numpy
  6.  
  7. # PRE = in nodes le coordinate sono in radianti
  8. class TSP:
  9.     def __init__(self):
  10.         self.name = ''
  11.         self.dimension = 0
  12.         self.etype = ''
  13.         self.nodes = defaultdict(list)
  14.         self.adjMatrix = []
  15.  
  16.  
  17.     def add_node(self, i: int, x: float, y: float):
  18.         if(self.etype == 'GEO'):
  19.             degX, degY = int(x), int(y)
  20.             minX, minY = x - degX, y - degY
  21.             x, y = math.pi*(degX+5.0*minX/3.0)/180.0, math.pi*(degY+5.0*minY/3.0)/180.0
  22.         self.nodes[i] = [x,y]
  23.  
  24.     # FUNZIONA (tm) ?
  25.     # def get_weight(self, first: int, sec: int):
  26.     #     RRR = 6378.388
  27.     #     q1 = math.cos(self.nodes[first][1] - self.nodes[sec][1])
  28.     #     q2 = math.cos(self.nodes[first][0] - self.nodes[sec][0])
  29.     #     q3 = math.cos(self.nodes[first][0] + self.nodes[sec][0])
  30.     #     final = (RRR*math.acos((0.5*((1.0+q1)*q2 - (1.0-q1)*q3))) + 1.0)
  31.     #     if self.etype == 'GEO':
  32.     #         return math.floor(final)
  33.     #     else:
  34.     #         return int(round(final))
  35.  
  36.     def get_weight(self, first: int, sec: int):
  37.         if self.etype == 'GEO':
  38.             RRR = 6378.388
  39.             q1 = math.cos(self.nodes[first][1] - self.nodes[sec][1])
  40.             q2 = math.cos(self.nodes[first][0] - self.nodes[sec][0])
  41.             q3 = math.cos(self.nodes[first][0] + self.nodes[sec][0])
  42.             return  int( RRR * math.acos( 0.5*((1.0+q1)*q2 - (1.0-q1)*q3) ) + 1.0)
  43.         else:
  44.             return math.sqrt((self.nodes[sec][1]-self.nodes[first][1])**2 + (self.nodes[sec][0]-self.nodes[first][0])**2)
  45.  
  46.     def calculateAdjMatrix(self):
  47.         for i in range(self.dimension+1):
  48.             self.adjMatrix.append([0 for i in range(self.dimension+1)])
  49.  
  50.         for i in range(1, self.dimension+1):
  51.             for j in range(1, self.dimension+1):
  52.                 if i == j:
  53.                     self.adjMatrix[i][j] = 0
  54.                 else:
  55.                     self.adjMatrix[i][j] = self.adjMatrix[j][i] = self.get_weight(i, j)
  56.  
  57.         self.printAdjMatrix()
  58.  
  59.     def printAdjMatrix(self):
  60.         print('\n')
  61.         print('\n'.join([''.join(['{:4}'.format((item)) for item in row])
  62.       for row in self.adjMatrix]))
  63.