| rev |
line source |
|
alpar@9
|
1 /* glptsp.h (TSP format) */
|
|
alpar@9
|
2
|
|
alpar@9
|
3 /***********************************************************************
|
|
alpar@9
|
4 * This code is part of GLPK (GNU Linear Programming Kit).
|
|
alpar@9
|
5 *
|
|
alpar@9
|
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
|
|
alpar@9
|
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
|
|
alpar@9
|
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
|
|
alpar@9
|
9 * E-mail: <mao@gnu.org>.
|
|
alpar@9
|
10 *
|
|
alpar@9
|
11 * GLPK is free software: you can redistribute it and/or modify it
|
|
alpar@9
|
12 * under the terms of the GNU General Public License as published by
|
|
alpar@9
|
13 * the Free Software Foundation, either version 3 of the License, or
|
|
alpar@9
|
14 * (at your option) any later version.
|
|
alpar@9
|
15 *
|
|
alpar@9
|
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
|
|
alpar@9
|
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
alpar@9
|
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
|
|
alpar@9
|
19 * License for more details.
|
|
alpar@9
|
20 *
|
|
alpar@9
|
21 * You should have received a copy of the GNU General Public License
|
|
alpar@9
|
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
|
|
alpar@9
|
23 ***********************************************************************/
|
|
alpar@9
|
24
|
|
alpar@9
|
25 #ifndef GLPTSP_H
|
|
alpar@9
|
26 #define GLPTSP_H
|
|
alpar@9
|
27
|
|
alpar@9
|
28 typedef struct TSP TSP;
|
|
alpar@9
|
29
|
|
alpar@9
|
30 struct TSP
|
|
alpar@9
|
31 { /* TSP (or related problem) instance in the format described in
|
|
alpar@9
|
32 the report [G.Reinelt, TSPLIB 95] */
|
|
alpar@9
|
33 /*--------------------------------------------------------------*/
|
|
alpar@9
|
34 /* the specification part */
|
|
alpar@9
|
35 char *name;
|
|
alpar@9
|
36 /* identifies the data file */
|
|
alpar@9
|
37 int type;
|
|
alpar@9
|
38 /* specifies the type of data: */
|
|
alpar@9
|
39 #define TSP_UNDEF 0 /* undefined */
|
|
alpar@9
|
40 #define TSP_TSP 1 /* symmetric TSP */
|
|
alpar@9
|
41 #define TSP_ATSP 2 /* asymmetric TSP */
|
|
alpar@9
|
42 #define TSP_TOUR 3 /* collection of tours */
|
|
alpar@9
|
43 char *comment;
|
|
alpar@9
|
44 /* additional comments (usually the name of the contributor or
|
|
alpar@9
|
45 creator of the problem instance is given here) */
|
|
alpar@9
|
46 int dimension;
|
|
alpar@9
|
47 /* for a TSP or ATSP, the dimension is the number of its nodes
|
|
alpar@9
|
48 for a TOUR it is the dimension of the corresponding problem */
|
|
alpar@9
|
49 int edge_weight_type;
|
|
alpar@9
|
50 /* specifies how the edge weights (or distances) are given: */
|
|
alpar@9
|
51 #define TSP_UNDEF 0 /* undefined */
|
|
alpar@9
|
52 #define TSP_EXPLICIT 1 /* listed explicitly */
|
|
alpar@9
|
53 #define TSP_EUC_2D 2 /* Eucl. distances in 2-D */
|
|
alpar@9
|
54 #define TSP_CEIL_2D 3 /* Eucl. distances in 2-D rounded up */
|
|
alpar@9
|
55 #define TSP_GEO 4 /* geographical distances */
|
|
alpar@9
|
56 #define TSP_ATT 5 /* special distance function */
|
|
alpar@9
|
57 int edge_weight_format;
|
|
alpar@9
|
58 /* describes the format of the edge weights if they are given
|
|
alpar@9
|
59 explicitly: */
|
|
alpar@9
|
60 #define TSP_UNDEF 0 /* undefined */
|
|
alpar@9
|
61 #define TSP_FUNCTION 1 /* given by a function */
|
|
alpar@9
|
62 #define TSP_FULL_MATRIX 2 /* given by a full matrix */
|
|
alpar@9
|
63 #define TSP_UPPER_ROW 3 /* upper triangulat matrix (row-wise
|
|
alpar@9
|
64 without diagonal entries) */
|
|
alpar@9
|
65 #define TSP_LOWER_DIAG_ROW 4 /* lower triangular matrix (row-wise
|
|
alpar@9
|
66 including diagonal entries) */
|
|
alpar@9
|
67 int display_data_type;
|
|
alpar@9
|
68 /* specifies how a graphical display of the nodes can be
|
|
alpar@9
|
69 obtained: */
|
|
alpar@9
|
70 #define TSP_UNDEF 0 /* undefined */
|
|
alpar@9
|
71 #define TSP_COORD_DISPLAY 1 /* display is generated from the node
|
|
alpar@9
|
72 coordinates */
|
|
alpar@9
|
73 #define TSP_TWOD_DISPLAY 2 /* explicit coordinates in 2-D are
|
|
alpar@9
|
74 given */
|
|
alpar@9
|
75 /*--------------------------------------------------------------*/
|
|
alpar@9
|
76 /* data part */
|
|
alpar@9
|
77 /* NODE_COORD_SECTION: */
|
|
alpar@9
|
78 double *node_x_coord; /* double node_x_coord[1+dimension]; */
|
|
alpar@9
|
79 double *node_y_coord; /* double node_y_coord[1+dimension]; */
|
|
alpar@9
|
80 /* DISPLAY_DATA_SECTION: */
|
|
alpar@9
|
81 double *dply_x_coord; /* double dply_x_coord[1+dimension]; */
|
|
alpar@9
|
82 double *dply_y_coord; /* double dply_y_coord[1+dimension]; */
|
|
alpar@9
|
83 /* TOUR_SECTION: */
|
|
alpar@9
|
84 int *tour; /* int tour[1+dimension]; */
|
|
alpar@9
|
85 /* EDGE_WEIGHT_SECTION: */
|
|
alpar@9
|
86 int *edge_weight; /* int edge_weight[1+dimension*dimension]; */
|
|
alpar@9
|
87 };
|
|
alpar@9
|
88
|
|
alpar@9
|
89 #define tsp_read_data _glp_tsp_read_data
|
|
alpar@9
|
90 #define tsp_free_data _glp_tsp_free_data
|
|
alpar@9
|
91 #define tsp_distance _glp_tsp_distance
|
|
alpar@9
|
92
|
|
alpar@9
|
93 TSP *tsp_read_data(char *fname);
|
|
alpar@9
|
94 /* read TSP instance data */
|
|
alpar@9
|
95
|
|
alpar@9
|
96 void tsp_free_data(TSP *tsp);
|
|
alpar@9
|
97 /* free TSP instance data */
|
|
alpar@9
|
98
|
|
alpar@9
|
99 int tsp_distance(TSP *tsp, int i, int j);
|
|
alpar@9
|
100 /* compute distance between two nodes */
|
|
alpar@9
|
101
|
|
alpar@9
|
102 #endif
|
|
alpar@9
|
103
|
|
alpar@9
|
104 /* eof */
|
