Context Navigation

← Previous Revision
Next Revision →
Blame
Revision Log

glptsp.c

subpack-glpk

Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago
Import GLPK 4.47
File size: 23.6 KB

Line
1	/* glptsp.c */
2
3	/***********************************************************************
4	* This code is part of GLPK (GNU Linear Programming Kit).
5	*
6	* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7	* 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
8	* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
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	***********************************************************************/
24
25	#define _GLPSTD_ERRNO
26	#define _GLPSTD_STDIO
27	#include "glpenv.h"
28	#include "glptsp.h"
29	#define xfault xerror
30
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. */
52
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	};
66
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	}
87
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	}
93
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 */

Note: See TracBrowser for help on using the repository browser.

Context Navigation

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

Download in other formats: