lemon-project-template-glpk: 33de93886c88 deps/glpk/src/glptsp.c

lemon-project-template-glpk

view deps/glpk/src/glptsp.c @ 9:33de93886c88

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

line source

1 /* glptsp.c */

3 /***********************************************************************

4 * This code is part of GLPK (GNU Linear Programming Kit).

5 *

7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,

9 * E-mail: <mao@gnu.org>.

10 *

11 * GLPK is free software: you can redistribute it and/or modify it

12 * under the terms of the GNU General Public License as published by

13 * the Free Software Foundation, either version 3 of the License, or

14 * (at your option) any later version.

15 *

16 * GLPK is distributed in the hope that it will be useful, but WITHOUT

17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

19 * License for more details.

20 *

21 * You should have received a copy of the GNU General Public License

22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.

23 ***********************************************************************/

25 #define _GLPSTD_ERRNO

26 #define _GLPSTD_STDIO

27 #include "glpenv.h"

28 #include "glptsp.h"

29 #define xfault xerror

31 /*----------------------------------------------------------------------

32 -- tsp_read_data - read TSP instance data.

33 --

34 -- *Synopsis*

35 --

36 -- #include "glptsp.h"

37 -- TSP *tsp_read_data(char *fname);

38 --

39 -- *Description*

40 --

41 -- The routine tsp_read_data reads a TSP (or related problem) instance

42 -- data from the text file, whose name is the character string fname.

43 --

44 -- For detailed description of the format recognized by the routine see

45 -- the report: G.Reinelt, TSPLIB 95.

46 --

47 -- *Returns*

48 --

49 -- If no error occurred, the routine tsp_read_data returns a pointer to

50 -- the TSP instance data block, which contains loaded data. In the case

51 -- of error the routine prints an error message and returns NULL. */

53 struct dsa

54 { /* dynamic storage area used by the routine tsp_read_data */

55 char *fname;

56 /* name of the input text file */

57 FILE *fp;

58 /* stream assigned to the input text file */

59 int seqn;

60 /* line sequential number */

61 int c;

62 /* current character */

63 char token[255+1];

64 /* current token */

65 };

67 static int get_char(struct dsa *dsa)

68 { dsa->c = fgetc(dsa->fp);

69 if (ferror(dsa->fp))

70 { xprintf("%s:%d: read error - %s\n",

71 dsa->fname, dsa->seqn, strerror(errno));

72 return 1;

73 }

74 if (feof(dsa->fp))

75 dsa->c = EOF;

76 else if (dsa->c == '\n')

77 dsa->seqn++;

78 else if (isspace(dsa->c))

79 dsa->c = ' ';

80 else if (iscntrl(dsa->c))

81 { xprintf("%s:%d: invalid control character 0x%02X\n",

82 dsa->fname, dsa->seqn, dsa->c);

83 return 1;

84 }

85 return 0;

86 }

88 static int skip_spaces(struct dsa *dsa, int across)

89 { while (dsa->c == ' ' || (across && dsa->c == '\n'))

90 if (get_char(dsa)) return 1;

91 return 0;

92 }

94 static int scan_keyword(struct dsa *dsa)

95 { int len = 0;

96 if (skip_spaces(dsa, 0)) return 1;

97 dsa->token[0] = '\0';

98 while (isalnum(dsa->c) || dsa->c == '_')

99 { if (len == 31)

100 { xprintf("%s:%d: keyword `%s...' too long\n", dsa->fname,

101 dsa->seqn, dsa->token);

102 return 1;

103 }

104 dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';

105 if (get_char(dsa)) return 1;

106 }

107 if (len == 0)

108 { xprintf("%s:%d: missing keyword\n", dsa->fname, dsa->seqn);

109 return 1;

110 }

111 return 0;

112 }

113

114 static int check_colon(struct dsa *dsa)

115 { if (skip_spaces(dsa, 0)) return 1;

116 if (dsa->c != ':')

117 { xprintf("%s:%d: missing colon after `%s'\n", dsa->fname,

118 dsa->seqn, dsa->token);

119 return 1;

120 }

121 if (get_char(dsa)) return 1;

122 return 0;

123 }

124

125 static int scan_token(struct dsa *dsa, int across)

126 { int len = 0;

127 if (skip_spaces(dsa, across)) return 1;

128 dsa->token[0] = '\0';

129 while (!(dsa->c == EOF || dsa->c == '\n' || dsa->c == ' '))

130 { if (len == 255)

131 { dsa->token[31] = '\0';

132 xprintf("%s:%d: token `%s...' too long\n", dsa->fname,

133 dsa->seqn, dsa->token);

134 return 1;

135 }

136 dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';

137 if (get_char(dsa)) return 1;

138 }

139 return 0;

140 }

141

142 static int check_newline(struct dsa *dsa)

143 { if (skip_spaces(dsa, 0)) return 1;

144 if (!(dsa->c == EOF || dsa->c == '\n'))

145 { xprintf("%s:%d: extra symbols detected\n", dsa->fname,

146 dsa->seqn);

147 return 1;

148 }

149 if (get_char(dsa)) return 1;

150 return 0;

151 }

152

153 static int scan_comment(struct dsa *dsa)

154 { int len = 0;

155 if (skip_spaces(dsa, 0)) return 1;

156 dsa->token[0] = '\0';

157 while (!(dsa->c == EOF || dsa->c == '\n'))

158 { if (len == 255)

159 { xprintf("%s:%d: comment too long\n", dsa->fname, dsa->seqn)

160 ;

161 return 1;

162 }

163 dsa->token[len++] = (char)dsa->c, dsa->token[len] = '\0';

164 if (get_char(dsa)) return 1;

165 }

166 return 0;

167 }

168

169 static int scan_integer(struct dsa *dsa, int across, int *val)

170 { if (scan_token(dsa, across)) return 1;

171 if (strlen(dsa->token) == 0)

172 { xprintf("%s:%d: missing integer\n", dsa->fname, dsa->seqn);

173 return 1;

174 }

175 if (str2int(dsa->token, val))

176 { xprintf("%s:%d: integer `%s' invalid\n", dsa->fname, dsa->seqn

177 , dsa->token);

178 return 1;

179 }

180 return 0;

181 }

182

183 static int scan_number(struct dsa *dsa, int across, double *val)

184 { if (scan_token(dsa, across)) return 1;

185 if (strlen(dsa->token) == 0)

186 { xprintf("%s:%d: missing number\n", dsa->fname, dsa->seqn);

187 return 1;

188 }

189 if (str2num(dsa->token, val))

190 { xprintf("%s:%d: number `%s' invalid\n", dsa->fname, dsa->seqn,

191 dsa->token);

192 return 1;

193 }

194 return 0;

195 }

196

197 TSP *tsp_read_data(char *fname)

198 { struct dsa _dsa, *dsa = &_dsa;

199 TSP *tsp = NULL;

200 dsa->fname = fname;

201 xprintf("tsp_read_data: reading TSP data from `%s'...\n",

202 dsa->fname);

203 dsa->fp = fopen(dsa->fname, "r");

204 if (dsa->fp == NULL)

205 { xprintf("tsp_read_data: unable to open `%s' - %s\n",

206 dsa->fname, strerror(errno));

207 goto fail;

208 }

209 tsp = xmalloc(sizeof(TSP));

210 tsp->name = NULL;

211 tsp->type = TSP_UNDEF;

212 tsp->comment = NULL;

213 tsp->dimension = 0;

214 tsp->edge_weight_type = TSP_UNDEF;

215 tsp->edge_weight_format = TSP_UNDEF;

216 tsp->display_data_type = TSP_UNDEF;

217 tsp->node_x_coord = NULL;

218 tsp->node_y_coord = NULL;

219 tsp->dply_x_coord = NULL;

220 tsp->dply_y_coord = NULL;

221 tsp->tour = NULL;

222 tsp->edge_weight = NULL;

223 dsa->seqn = 1;

224 if (get_char(dsa)) goto fail;

225 loop: if (scan_keyword(dsa)) goto fail;

226 if (strcmp(dsa->token, "NAME") == 0)

227 { if (tsp->name != NULL)

228 { xprintf("%s:%d: NAME entry multiply defined\n", dsa->fname,

229 dsa->seqn);

230 goto fail;

231 }

232 if (check_colon(dsa)) goto fail;

233 if (scan_token(dsa, 0)) goto fail;

234 if (strlen(dsa->token) == 0)

235 { xprintf("%s:%d: NAME entry incomplete\n", dsa->fname,

236 dsa->seqn);

237 goto fail;

238 }

239 tsp->name = xmalloc(strlen(dsa->token) + 1);

240 strcpy(tsp->name, dsa->token);

241 xprintf("tsp_read_data: NAME: %s\n", tsp->name);

242 if (check_newline(dsa)) goto fail;

243 }

244 else if (strcmp(dsa->token, "TYPE") == 0)

245 { if (tsp->type != TSP_UNDEF)

246 { xprintf("%s:%d: TYPE entry multiply defined\n", dsa->fname,

247 dsa->seqn);

248 goto fail;

249 }

250 if (check_colon(dsa)) goto fail;

251 if (scan_keyword(dsa)) goto fail;

252 if (strcmp(dsa->token, "TSP") == 0)

253 tsp->type = TSP_TSP;

254 else if (strcmp(dsa->token, "ATSP") == 0)

255 tsp->type = TSP_ATSP;

256 else if (strcmp(dsa->token, "TOUR") == 0)

257 tsp->type = TSP_TOUR;

258 else

259 { xprintf("%s:%d: data type `%s' not recognized\n",

260 dsa->fname, dsa->seqn, dsa->token);

261 goto fail;

262 }

263 xprintf("tsp_read_data: TYPE: %s\n", dsa->token);

264 if (check_newline(dsa)) goto fail;

265 }

266 else if (strcmp(dsa->token, "COMMENT") == 0)

267 { if (tsp->comment != NULL)

268 { xprintf("%s:%d: COMMENT entry multiply defined\n",

269 dsa->fname, dsa->seqn);

270 goto fail;

271 }

272 if (check_colon(dsa)) goto fail;

273 if (scan_comment(dsa)) goto fail;

274 tsp->comment = xmalloc(strlen(dsa->token) + 1);

275 strcpy(tsp->comment, dsa->token);

276 xprintf("tsp_read_data: COMMENT: %s\n", tsp->comment);

277 if (check_newline(dsa)) goto fail;

278 }

279 else if (strcmp(dsa->token, "DIMENSION") == 0)

280 { if (tsp->dimension != 0)

281 { xprintf("%s:%d: DIMENSION entry multiply defined\n",

282 dsa->fname, dsa->seqn);

283 goto fail;

284 }

285 if (check_colon(dsa)) goto fail;

286 if (scan_integer(dsa, 0, &tsp->dimension)) goto fail;

287 if (tsp->dimension < 1)

288 { xprintf("%s:%d: invalid dimension\n", dsa->fname,

289 dsa->seqn);

290 goto fail;

291 }

292 xprintf("tsp_read_data: DIMENSION: %d\n", tsp->dimension);

293 if (check_newline(dsa)) goto fail;

294 }

295 else if (strcmp(dsa->token, "EDGE_WEIGHT_TYPE") == 0)

296 { if (tsp->edge_weight_type != TSP_UNDEF)

297 { xprintf("%s:%d: EDGE_WEIGHT_TYPE entry multiply defined\n",

298 dsa->fname, dsa->seqn);

299 goto fail;

300 }

301 if (check_colon(dsa)) goto fail;

302 if (scan_keyword(dsa)) goto fail;

303 if (strcmp(dsa->token, "GEO") == 0)

304 tsp->edge_weight_type = TSP_GEO;

305 else if (strcmp(dsa->token, "EUC_2D") == 0)

306 tsp->edge_weight_type = TSP_EUC_2D;

307 else if (strcmp(dsa->token, "ATT") == 0)

308 tsp->edge_weight_type = TSP_ATT;

309 else if (strcmp(dsa->token, "EXPLICIT") == 0)

310 tsp->edge_weight_type = TSP_EXPLICIT;

311 else if (strcmp(dsa->token, "CEIL_2D") == 0)

312 tsp->edge_weight_type = TSP_CEIL_2D;

313 else

314 { xprintf("%s:%d: edge weight type `%s' not recognized\n",

315 dsa->fname, dsa->seqn, dsa->token);

316 goto fail;

317 }

318 xprintf("tsp_read_data: EDGE_WEIGHT_TYPE: %s\n", dsa->token);

319 if (check_newline(dsa)) goto fail;

320 }

321 else if (strcmp(dsa->token, "EDGE_WEIGHT_FORMAT") == 0)

322 { if (tsp->edge_weight_format != TSP_UNDEF)

323 { xprintf(

324 "%s:%d: EDGE_WEIGHT_FORMAT entry multiply defined\n",

325 dsa->fname, dsa->seqn);

326 goto fail;

327 }

328 if (check_colon(dsa)) goto fail;

329 if (scan_keyword(dsa)) goto fail;

330 if (strcmp(dsa->token, "UPPER_ROW") == 0)

331 tsp->edge_weight_format = TSP_UPPER_ROW;

332 else if (strcmp(dsa->token, "FULL_MATRIX") == 0)

333 tsp->edge_weight_format = TSP_FULL_MATRIX;

334 else if (strcmp(dsa->token, "FUNCTION") == 0)

335 tsp->edge_weight_format = TSP_FUNCTION;

336 else if (strcmp(dsa->token, "LOWER_DIAG_ROW") == 0)

337 tsp->edge_weight_format = TSP_LOWER_DIAG_ROW;

338 else

339 { xprintf("%s:%d: edge weight format `%s' not recognized\n",

340 dsa->fname, dsa->seqn, dsa->token);

341 goto fail;

342 }

343 xprintf("tsp_read_data: EDGE_WEIGHT_FORMAT: %s\n", dsa->token);

344 if (check_newline(dsa)) goto fail;

345 }

346 else if (strcmp(dsa->token, "DISPLAY_DATA_TYPE") == 0)

347 { if (tsp->display_data_type != TSP_UNDEF)

348 { xprintf("%s:%d: DISPLAY_DATA_TYPE entry multiply defined\n",

349 dsa->fname, dsa->seqn);

350 goto fail;

351 }

352 if (check_colon(dsa)) goto fail;

353 if (scan_keyword(dsa)) goto fail;

354 if (strcmp(dsa->token, "COORD_DISPLAY") == 0)

355 tsp->display_data_type = TSP_COORD_DISPLAY;

356 else if (strcmp(dsa->token, "TWOD_DISPLAY") == 0)

357 tsp->display_data_type = TSP_TWOD_DISPLAY;

358 else

359 { xprintf("%s:%d: display data type `%s' not recognized\n",

360 dsa->fname, dsa->seqn, dsa->token);

361 goto fail;

362 }

363 xprintf("tsp_read_data: DISPLAY_DATA_TYPE: %s\n", dsa->token);

364 if (check_newline(dsa)) goto fail;

365 }

366 else if (strcmp(dsa->token, "NODE_COORD_SECTION") == 0)

367 { int n = tsp->dimension, k, node;

368 if (n == 0)

369 { xprintf("%s:%d: DIMENSION entry not specified\n",

370 dsa->fname, dsa->seqn);

371 goto fail;

372 }

373 if (tsp->node_x_coord != NULL)

374 { xprintf("%s:%d: NODE_COORD_SECTION multiply specified\n",

375 dsa->fname, dsa->seqn);

376 goto fail;

377 }

378 if (check_newline(dsa)) goto fail;

379 tsp->node_x_coord = xcalloc(1+n, sizeof(double));

380 tsp->node_y_coord = xcalloc(1+n, sizeof(double));

381 for (node = 1; node <= n; node++)

382 tsp->node_x_coord[node] = tsp->node_y_coord[node] = DBL_MAX;

383 for (k = 1; k <= n; k++)

384 { if (scan_integer(dsa, 0, &node)) goto fail;

385 if (!(1 <= node && node <= n))

386 { xprintf("%s:%d: invalid node number %d\n", dsa->fname,

387 dsa->seqn, node);

388 goto fail;

389 }

390 if (tsp->node_x_coord[node] != DBL_MAX)

391 { xprintf("%s:%d: node number %d multiply specified\n",

392 dsa->fname, dsa->seqn, node);

393 goto fail;

394 }

395 if (scan_number(dsa, 0, &tsp->node_x_coord[node]))

396 goto fail;

397 if (scan_number(dsa, 0, &tsp->node_y_coord[node]))

398 goto fail;

399 if (check_newline(dsa)) goto fail;

400 }

401 }

402 else if (strcmp(dsa->token, "DISPLAY_DATA_SECTION") == 0)

403 { int n = tsp->dimension, k, node;

404 if (n == 0)

405 { xprintf("%s:%d: DIMENSION entry not specified\n",

406 dsa->fname, dsa->seqn);

407 goto fail;

408 }

409 if (tsp->dply_x_coord != NULL)

410 { xprintf("%s:%d: DISPLAY_DATA_SECTION multiply specified\n",

411 dsa->fname, dsa->seqn);

412 goto fail;

413 }

414 if (check_newline(dsa)) goto fail;

415 tsp->dply_x_coord = xcalloc(1+n, sizeof(double));

416 tsp->dply_y_coord = xcalloc(1+n, sizeof(double));

417 for (node = 1; node <= n; node++)

418 tsp->dply_x_coord[node] = tsp->dply_y_coord[node] = DBL_MAX;

419 for (k = 1; k <= n; k++)

420 { if (scan_integer(dsa, 0, &node)) goto fail;

421 if (!(1 <= node && node <= n))

422 { xprintf("%s:%d: invalid node number %d\n", dsa->fname,

423 dsa->seqn, node);

424 goto fail;

425 }

426 if (tsp->dply_x_coord[node] != DBL_MAX)

427 { xprintf("%s:%d: node number %d multiply specified\n",

428 dsa->fname, dsa->seqn, node);

429 goto fail;

430 }

431 if (scan_number(dsa, 0, &tsp->dply_x_coord[node]))

432 goto fail;

433 if (scan_number(dsa, 0, &tsp->dply_y_coord[node]))

434 goto fail;

435 if (check_newline(dsa)) goto fail;

436 }

437 }

438 else if (strcmp(dsa->token, "TOUR_SECTION") == 0)

439 { int n = tsp->dimension, k, node;

440 if (n == 0)

441 { xprintf("%s:%d: DIMENSION entry not specified\n",

442 dsa->fname, dsa->seqn);

443 goto fail;

444 }

445 if (tsp->tour != NULL)

446 { xprintf("%s:%d: TOUR_SECTION multiply specified\n",

447 dsa->fname, dsa->seqn);

448 goto fail;

449 }

450 if (check_newline(dsa)) goto fail;

451 tsp->tour = xcalloc(1+n, sizeof(int));

452 for (k = 1; k <= n; k++)

453 { if (scan_integer(dsa, 1, &node)) goto fail;

454 if (!(1 <= node && node <= n))

455 { xprintf("%s:%d: invalid node number %d\n", dsa->fname,

456 dsa->seqn, node);

457 goto fail;

458 }

459 tsp->tour[k] = node;

460 }

461 if (scan_integer(dsa, 1, &node)) goto fail;

462 if (node != -1)

463 { xprintf("%s:%d: extra node(s) detected\n", dsa->fname,

464 dsa->seqn);

465 goto fail;

466 }

467 if (check_newline(dsa)) goto fail;

468 }

469 else if (strcmp(dsa->token, "EDGE_WEIGHT_SECTION") == 0)

470 { int n = tsp->dimension, i, j, temp;

471 if (n == 0)

472 { xprintf("%s:%d: DIMENSION entry not specified\n",

473 dsa->fname, dsa->seqn);

474 goto fail;

475 }

476 if (tsp->edge_weight_format == TSP_UNDEF)

477 { xprintf("%s:%d: EDGE_WEIGHT_FORMAT entry not specified\n",

478 dsa->fname, dsa->seqn);

479 goto fail;

480 }

481 if (tsp->edge_weight != NULL)

482 { xprintf("%s:%d: EDGE_WEIGHT_SECTION multiply specified\n",

483 dsa->fname, dsa->seqn);

484 goto fail;

485 }

486 if (check_newline(dsa)) goto fail;

487 tsp->edge_weight = xcalloc(1+n*n, sizeof(int));

488 switch (tsp->edge_weight_format)

489 { case TSP_FULL_MATRIX:

490 for (i = 1; i <= n; i++)

491 { for (j = 1; j <= n; j++)

492 { if (scan_integer(dsa, 1, &temp)) goto fail;

493 tsp->edge_weight[(i - 1) * n + j] = temp;

494 }

495 }

496 break;

497 case TSP_UPPER_ROW:

498 for (i = 1; i <= n; i++)

499 { tsp->edge_weight[(i - 1) * n + i] = 0;

500 for (j = i + 1; j <= n; j++)

501 { if (scan_integer(dsa, 1, &temp)) goto fail;

502 tsp->edge_weight[(i - 1) * n + j] = temp;

503 tsp->edge_weight[(j - 1) * n + i] = temp;

504 }

505 }

506 break;

507 case TSP_LOWER_DIAG_ROW:

508 for (i = 1; i <= n; i++)

509 { for (j = 1; j <= i; j++)

510 { if (scan_integer(dsa, 1, &temp)) goto fail;

511 tsp->edge_weight[(i - 1) * n + j] = temp;

512 tsp->edge_weight[(j - 1) * n + i] = temp;

513 }

514 }

515 break;

516 default:

517 goto fail;

518 }

519 if (check_newline(dsa)) goto fail;

520 }

521 else if (strcmp(dsa->token, "EOF") == 0)

522 { if (check_newline(dsa)) goto fail;

523 goto done;

524 }

525 else

526 { xprintf("%s:%d: keyword `%s' not recognized\n", dsa->fname,

527 dsa->seqn, dsa->token);

528 goto fail;

529 }

530 goto loop;

531 done: xprintf("tsp_read_data: %d lines were read\n", dsa->seqn-1);

532 fclose(dsa->fp);

533 return tsp;

534 fail: if (tsp != NULL)

535 { if (tsp->name != NULL) xfree(tsp->name);

536 if (tsp->comment != NULL) xfree(tsp->comment);

537 if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord);

538 if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord);

539 if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord);

540 if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord);

541 if (tsp->tour != NULL) xfree(tsp->tour);

542 if (tsp->edge_weight != NULL) xfree(tsp->edge_weight);

543 xfree(tsp);

544 }

545 if (dsa->fp != NULL) fclose(dsa->fp);

546 return NULL;

547 }

548

549 /*----------------------------------------------------------------------

550 -- tsp_free_data - free TSP instance data.

551 --

552 -- *Synopsis*

553 --

554 -- #include "glptsp.h"

555 -- void tsp_free_data(TSP *tsp);

556 --

557 -- *Description*

558 --

559 -- The routine tsp_free_data frees all the memory allocated to the TSP

560 -- instance data block, which the parameter tsp points to. */

561

562 void tsp_free_data(TSP *tsp)

563 { if (tsp->name != NULL) xfree(tsp->name);

564 if (tsp->comment != NULL) xfree(tsp->comment);

565 if (tsp->node_x_coord != NULL) xfree(tsp->node_x_coord);

566 if (tsp->node_y_coord != NULL) xfree(tsp->node_y_coord);

567 if (tsp->dply_x_coord != NULL) xfree(tsp->dply_x_coord);

568 if (tsp->dply_y_coord != NULL) xfree(tsp->dply_y_coord);

569 if (tsp->tour != NULL) xfree(tsp->tour);

570 if (tsp->edge_weight != NULL) xfree(tsp->edge_weight);

571 xfree(tsp);

572 return;

573 }

574

575 /*----------------------------------------------------------------------

576 -- tsp_distance - compute distance between two nodes.

577 --

578 -- *Synopsis*

579 --

580 -- #include "glptsp.h"

581 -- int tsp_distance(TSP *tsp, int i, int j);

582 --

583 -- *Description*

584 --

585 -- The routine tsp_distance computes the distance between i-th and j-th

586 -- nodes for the TSP instance, which tsp points to.

587 --

588 -- *Returns*

589 --

590 -- The routine tsp_distance returns the computed distance. */

591

592 #define nint(x) ((int)((x) + 0.5))

593

594 static double rad(double x)

595 { /* convert input coordinate to longitude/latitude, in radians */

596 double pi = 3.141592, deg, min;

597 deg = (int)x;

598 min = x - deg;

599 return pi * (deg + 5.0 * min / 3.0) / 180.0;

600 }

601

602 int tsp_distance(TSP *tsp, int i, int j)

603 { int n = tsp->dimension, dij;

604 if (!(tsp->type == TSP_TSP || tsp->type == TSP_ATSP))

605 xfault("tsp_distance: invalid TSP instance\n");

606 if (!(1 <= i && i <= n && 1 <= j && j <= n))

607 xfault("tsp_distance: node number out of range\n");

608 switch (tsp->edge_weight_type)

609 { case TSP_UNDEF:

610 xfault("tsp_distance: edge weight type not specified\n");

611 case TSP_EXPLICIT:

612 if (tsp->edge_weight == NULL)

613 xfault("tsp_distance: edge weights not specified\n");

614 dij = tsp->edge_weight[(i - 1) * n + j];

615 break;

616 case TSP_EUC_2D:

617 if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)

618 xfault("tsp_distance: node coordinates not specified\n");

619 { double xd, yd;

620 xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];

621 yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];

622 dij = nint(sqrt(xd * xd + yd * yd));

623 }

624 break;

625 case TSP_CEIL_2D:

626 if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)

627 xfault("tsp_distance: node coordinates not specified\n");

628 { double xd, yd;

629 xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];

630 yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];

631 dij = (int)ceil(sqrt(xd * xd + yd * yd));

632 }

633 break;

634 case TSP_GEO:

635 if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)

636 xfault("tsp_distance: node coordinates not specified\n");

637 { double rrr = 6378.388;

638 double latitude_i = rad(tsp->node_x_coord[i]);

639 double latitude_j = rad(tsp->node_x_coord[j]);

640 double longitude_i = rad(tsp->node_y_coord[i]);

641 double longitude_j = rad(tsp->node_y_coord[j]);

642 double q1 = cos(longitude_i - longitude_j);

643 double q2 = cos(latitude_i - latitude_j);

644 double q3 = cos(latitude_i + latitude_j);

645 dij = (int)(rrr * acos(0.5 * ((1.0 + q1) * q2 -

646 (1.0 - q1) *q3)) + 1.0);

647 }

648 break;

649 case TSP_ATT:

650 if (tsp->node_x_coord == NULL || tsp->node_y_coord == NULL)

651 xfault("tsp_distance: node coordinates not specified\n");

652 { int tij;

653 double xd, yd, rij;

654 xd = tsp->node_x_coord[i] - tsp->node_x_coord[j];

655 yd = tsp->node_y_coord[i] - tsp->node_y_coord[j];

656 rij = sqrt((xd * xd + yd * yd) / 10.0);

657 tij = nint(rij);

658 if (tij < rij) dij = tij + 1; else dij = tij;

659 }

660 break;

661 default:

662 xassert(tsp->edge_weight_type != tsp->edge_weight_type);

663 }

664 return dij;

665 }

666

667 /* eof */