1 """TravelingSalesmanProblem solving using GeneticAlgorithm by Sujin and destine
   2 """
   3 
   4 import unittest
   5 
   6 def encode(path):
   7     temp = range(1, len(path)+1)
   8     result = []
   9     for eachpath in path:
  10         p = temp.index(eachpath)
  11         result.append(p+1)
  12         temp.remove(eachpath)
  13     return result
  14 
  15     if path == [1]:
  16         return [1]
  17     elif path == [1,2]:
  18         return [1,1]
  19 
  20 def decode(depath):
  21     temp = range(1, len(depath) +1)
  22     result = []
  23     for eachpath in depath:
  24         p = temp[eachpath - 1]
  25         result.append(p)
  26         temp.remove(p)
  27     return result 
  28 def getDistance(path):
  29     distanceMap=[[ 0, 10, 20, 30, 40, 50], 
  30              [10,  0,  9, 40, 25, 15], 
  31              [20,  9,  0, 32,  9, 41], 
  32              [30, 40, 32,  0, 39,  5],  
  33              [40, 25,  9, 39,  0, 27], 
  34              [50, 15, 41,  5, 27,  0]]
  35     result = 0
  36     if len(path) == 1:
  37         return 0
  38     for eachpath in range(len(path)-1):
  39         result = result + distanceMap[path[eachpath]-1][path[eachpath+1]-1]  
  40     return result
  41 def crossOver(path1, path2, xPoint):
  42     depath1 = encode(path1)
  43     depath2 = encode(path2)
  44     if len(depath1) != len(depath2):
  45         return 0
  46     # This swapping algorithm can be possible.
  47     #temp = []
  48     #childpath1 = depath1[:]
  49     #childpath2 = depath2[:]
  50     #if xPoint <= 0 or xPoint>= len(depath1):
  51     #    return 0
  52     #temp = childpath2[xPoint:]
  53     #childpath2[xPoint:] = childpath1[xPoint:]
  54     #childpath1[xPoint:] = temp
  55     
  56     # in Python this index slicing is more preferred.
  57     if xPoint <= 0 or xPoint>= len(depath1):
  58         return 0
  59     childpath1 = depath1[:xPoint] + depath2[xPoint:]
  60     childpath2 = depath2[:xPoint] + depath1[xPoint:]
  61     
  62     return decode(childpath1), decode(childpath2)
  63     
  64 class TestEnDecoding(unittest.TestCase):
  65     def testEncoding1(self):
  66         path = [1]
  67         self.assertEquals([1], encode(path))
  68     def testEncoding2(self):
  69         path = [1,2]
  70         self.assertEquals([1,1], encode(path))
  71     def testEncoding3(self):
  72         path = [3, 4, 1, 2, 5]
  73         self.assertEquals([3,3,1,1,1], encode(path))
  74     def testDecoding1(self):
  75         depath = [1]
  76         self.assertEquals([1], decode(depath))
  77     def testDecoding2(self):
  78         depath = [1,3,2,2,2,1]
  79         self.assertEquals([1,4,3,5,6,2], decode(depath))
  80     def testGetDistance1(self):
  81         path = [1]
  82         self.assertEquals(0, getDistance(path))
  83     def testGetDistance2(self):
  84         path = [1, 2]
  85         self.assertEquals(10, getDistance(path))
  86     def testGetDistance3(self):
  87         path = [1,2,3]
  88         self.assertEquals(19, getDistance(path))
  89     def testCrossOver1(self):
  90         path1 = [1,2]
  91         path2 = [2,1]
  92         self.assertEquals(([1,2],[2,1]), crossOver(path1, path2, 1))
  93     def testCrossOver2(self):
  94         path1 = [1,2,3,4,5,6]
  95         path2 = [3,1,4,2,6,5]
  96         self.assertEquals(([1,2,3,4,6,5],[3,1,4,2,5,6]),  crossOver(path1, path2, 3))
  97         
  98 if __name__ == '__main__':
  99     unittest.main()