5 * read_tsplib - read a symmetric tsp instance
6 * read_atsplib - asymmetric
8 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
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)
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)
39 """Compute the Linfty distance between two points (see TSPLIB documentation)"""
40 return int(max(abs(x2-x1),abs(y2-y1)))
43 """Compute the ATT distance between two points (see TSPLIB documentation)"""
46 rij = math.sqrt((xd*xd + yd*yd) /10.)
54 """returns smallest integer not less than the distance of two points"""
57 return int(math.ceil(math.sqrt(xdiff*xdiff + ydiff*ydiff)))
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.)
88 for data
in line.split():
95 return range(1,n+1),c,
None,
None
102 for data
in line.split():
109 return range(1,n+1),c,
None,
None
116 for data
in line.split():
123 return range(1,n+1),c,
None,
None
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:
177 if line.find(
"UPPER_ROW") != -1:
178 while line.find(
"EDGE_WEIGHT_SECTION") == -1:
181 if line.find(
"UPPER_DIAG_ROW") != -1:
182 while line.find(
"EDGE_WEIGHT_SECTION") == -1:
185 if line.find(
"FULL_MATRIX") != -1:
186 while line.find(
"EDGE_WEIGHT_SECTION") == -1:
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])
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:")