-
Notifications
You must be signed in to change notification settings - Fork 1
/
graph.py
65 lines (57 loc) · 2.12 KB
/
graph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import random
import math
import itertools
import sys
class Graph:
def __init__(self, n):
self.shortest_tsp = sys.float_info.max
self.order_tsp = []
self.order_tsp_list = []
self.n = n
self.graph = []
for i in range(n):
x = random.random()
y = random.random()
self.graph.append((x, y))
self.each_to_each = [[0 for x in range(self.n)] for y in range(self.n)]
self.compute_each_to_each()
def compute_each_to_each(self):
for i in range(self.n):
for j in range(i, self.n):
if i == j:
self.each_to_each[i][j] = 0
else:
diff_x = self.graph[i][0] - self.graph[j][0]
diff_y = self.graph[i][1] - self.graph[j][1]
self.each_to_each[i][j] = self.each_to_each[j][i] = math.sqrt(diff_x * diff_x + diff_y * diff_y)
def compute_tsp(self):
elements = [i for i in range(self.n)]
for permutation in itertools.permutations(elements):
new_length = 0
for i in range(self.n - 1):
new_length += self.each_to_each[permutation[i]][permutation[i+1]]
new_length += self.each_to_each[permutation[self.n - 1]][permutation[0]]
if new_length < self.shortest_tsp:
self.shortest_tsp = new_length
self.order_tsp = permutation
self.order_tsp_list = list(self.order_tsp)
self.order_tsp = tuple(self.order_tsp_list)
def convert_output(output, N):
order = [0, 0, 0, 0, 0, 0]
for x in range(N):
best_y = None
best_y_value = -1
for y in range(N):
if output[y*N + x] > best_y_value:
best_y = y
best_y_value = output[y*N + x]
order[best_y] = x
for i in range(N):
output[best_y*N + i] = -1
return order
def calculate_tsp(graph, order):
length = 0
for i in range(graph.n - 1):
length += graph.each_to_each[order[i]][order[i+1]]
length += graph.each_to_each[order[graph.n - 1]][order[0]]
return length