5 * read_tsplib - read a symmetric tsp instance 6 * read_atsplib - asymmetric 8 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012 14 def distL2(x1,y1,x2,y2):
15 """Compute the L2-norm (Euclidean) distance between two points. 17 The distance is rounded to the closest integer, for compatibility 18 with the TSPLIB convention. 20 The two points are located on coordinates (x1,y1) and (x2,y2), 24 return int(math.sqrt(xdiff*xdiff + ydiff*ydiff) + .5)
27 def distL1(x1,y1,x2,y2):
28 """Compute the L1-norm (Manhattan) distance between two points. 30 The distance is rounded to the closest integer, for compatibility 31 with the TSPLIB convention. 33 The two points are located on coordinates (x1,y1) and (x2,y2), 35 return int(abs(x2-x1) + abs(y2-y1)+.5)
38 def distLinf(x1,y1,x2,y2):
39 """Compute the Linfty distance between two points (see TSPLIB documentation)""" 40 return int(max(abs(x2-x1),abs(y2-y1)))
42 def distATT(x1,y1,x2,y2):
43 """Compute the ATT distance between two points (see TSPLIB documentation)""" 46 rij = math.sqrt((xd*xd + yd*yd) /10.)
53 def distCEIL2D(x1,y1,x2,y2):
54 """returns smallest integer not less than the distance of two points""" 57 return int(math.ceil(math.sqrt(xdiff*xdiff + ydiff*ydiff)))
59 def distGEO(x1,y1,x2,y2):
60 print(
"Implementation is wrong")
65 lat1 = PI * (deg + 5.*min_/3)/180.
68 long1 = PI * (deg + 5.*min_/3)/180.
71 lat2 = PI * (deg + 5.*min_/3)/180.
74 long2 = PI * (deg + 5.*min_/3)/180.
78 q1 = math.cos( long1 - long2 );
79 q2 = math.cos( lat1 - lat2 );
80 q3 = math.cos( lat1 + lat2 );
81 return int(RRR * math.acos(.5*((1.+q1)*q2 - (1.-q1)*q3)) + 1.)
83 def read_explicit_lowerdiag(f,n):
88 for data
in line.split():
95 return range(1,n+1),c,
None,
None 97 def read_explicit_upper(f,n):
102 for data
in line.split():
109 return range(1,n+1),c,
None,
None 111 def read_explicit_upperdiag(f,n):
116 for data
in line.split():
123 return range(1,n+1),c,
None,
None 125 def read_explicit_matrix(f,n):
130 for data
in line.split():
138 return range(1,n+1),c,
None,
None 141 "basic function for reading a symmetric problem in the TSPLIB format" 142 "data is stored in an upper triangular matrix" 143 "NOTE: some distance types are not handled yet" 144 if filename[-3:] ==
".gz":
145 f = gzip.open(filename,
"rt")
150 while line.find(
"DIMENSION") == -1:
152 n = int(line.split()[-1])
154 while line.find(
"EDGE_WEIGHT_TYPE") == -1:
157 if line.find(
"EUC_2D") != -1:
159 elif line.find(
"MAN_2D") != -1:
161 elif line.find(
"MAX_2D") != -1:
163 elif line.find(
"ATT") != -1:
165 elif line.find(
"CEIL_2D") != -1:
170 elif line.find(
"EXPLICIT") != -1:
171 while line.find(
"EDGE_WEIGHT_FORMAT") == -1:
173 if line.find(
"LOWER_DIAG_ROW") != -1:
174 while line.find(
"EDGE_WEIGHT_SECTION") == -1:
176 return read_explicit_lowerdiag(f,n)
177 if line.find(
"UPPER_ROW") != -1:
178 while line.find(
"EDGE_WEIGHT_SECTION") == -1:
180 return read_explicit_upper(f,n)
181 if line.find(
"UPPER_DIAG_ROW") != -1:
182 while line.find(
"EDGE_WEIGHT_SECTION") == -1:
184 return read_explicit_upperdiag(f,n)
185 if line.find(
"FULL_MATRIX") != -1:
186 while line.find(
"EDGE_WEIGHT_SECTION") == -1:
188 return read_explicit_matrix(f,n)
189 print(
"error reading line " + line)
192 print(
"cannot deal with '%s' distances" % line)
195 while line.find(
"NODE_COORD_SECTION") == -1:
201 if line.find(
"EOF") != -1
or not line:
break 202 (i,xi,yi) = line.split()
210 c[i,j] = dist(x[i],y[i],x[j],y[j])
216 def read_atsplib(filename):
217 "basic function for reading a ATSP problem on the TSPLIB format" 218 "NOTE: only works for explicit matrices" 220 if filename[-3:] ==
".gz":
221 f = gzip.open(filename,
'r') 224 f = open(filename,
'r') 228 if line.find(
"DIMENSION") >= 0:
229 n = int(line.split()[1])
232 raise IOError(
"'DIMENSION' keyword not found in file '%s'" % filename)
235 if line.find(
"EDGE_WEIGHT_TYPE") >= 0:
236 if line.split()[1] ==
"EXPLICIT":
239 raise IOError(
"'EDGE_WEIGHT_TYPE' is not 'EXPLICIT' in file '%s'" % filename)
241 for k,line
in enumerate(data):
242 if line.find(
"EDGE_WEIGHT_SECTION") >= 0:
245 raise IOError(
"'EDGE_WEIGHT_SECTION' not found in file '%s'" % filename)
250 for line
in data[k+1:]:
251 if line.find(
"EOF") >= 0:
253 for val
in line.split():
254 dist.append(int(val))
266 if __name__ ==
"__main__":
269 if len(sys.argv) < 2:
270 print(
'Usage: %s instance' % sys.argv[0])
273 from read_tsplib
import read_tsplib
275 print(len(V),
"vertices,", len(c),
"arcs")
276 print(
"distance matrix:")