1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glptsp.h Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,104 @@
1.4 +/* glptsp.h (TSP format) */
1.5 +
1.6 +/***********************************************************************
1.7 +* This code is part of GLPK (GNU Linear Programming Kit).
1.8 +*
1.9 +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
1.10 +* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
1.11 +* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
1.12 +* E-mail: <mao@gnu.org>.
1.13 +*
1.14 +* GLPK is free software: you can redistribute it and/or modify it
1.15 +* under the terms of the GNU General Public License as published by
1.16 +* the Free Software Foundation, either version 3 of the License, or
1.17 +* (at your option) any later version.
1.18 +*
1.19 +* GLPK is distributed in the hope that it will be useful, but WITHOUT
1.20 +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.21 +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
1.22 +* License for more details.
1.23 +*
1.24 +* You should have received a copy of the GNU General Public License
1.25 +* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
1.26 +***********************************************************************/
1.27 +
1.28 +#ifndef GLPTSP_H
1.29 +#define GLPTSP_H
1.30 +
1.31 +typedef struct TSP TSP;
1.32 +
1.33 +struct TSP
1.34 +{ /* TSP (or related problem) instance in the format described in
1.35 + the report [G.Reinelt, TSPLIB 95] */
1.36 + /*--------------------------------------------------------------*/
1.37 + /* the specification part */
1.38 + char *name;
1.39 + /* identifies the data file */
1.40 + int type;
1.41 + /* specifies the type of data: */
1.42 +#define TSP_UNDEF 0 /* undefined */
1.43 +#define TSP_TSP 1 /* symmetric TSP */
1.44 +#define TSP_ATSP 2 /* asymmetric TSP */
1.45 +#define TSP_TOUR 3 /* collection of tours */
1.46 + char *comment;
1.47 + /* additional comments (usually the name of the contributor or
1.48 + creator of the problem instance is given here) */
1.49 + int dimension;
1.50 + /* for a TSP or ATSP, the dimension is the number of its nodes
1.51 + for a TOUR it is the dimension of the corresponding problem */
1.52 + int edge_weight_type;
1.53 + /* specifies how the edge weights (or distances) are given: */
1.54 +#define TSP_UNDEF 0 /* undefined */
1.55 +#define TSP_EXPLICIT 1 /* listed explicitly */
1.56 +#define TSP_EUC_2D 2 /* Eucl. distances in 2-D */
1.57 +#define TSP_CEIL_2D 3 /* Eucl. distances in 2-D rounded up */
1.58 +#define TSP_GEO 4 /* geographical distances */
1.59 +#define TSP_ATT 5 /* special distance function */
1.60 + int edge_weight_format;
1.61 + /* describes the format of the edge weights if they are given
1.62 + explicitly: */
1.63 +#define TSP_UNDEF 0 /* undefined */
1.64 +#define TSP_FUNCTION 1 /* given by a function */
1.65 +#define TSP_FULL_MATRIX 2 /* given by a full matrix */
1.66 +#define TSP_UPPER_ROW 3 /* upper triangulat matrix (row-wise
1.67 + without diagonal entries) */
1.68 +#define TSP_LOWER_DIAG_ROW 4 /* lower triangular matrix (row-wise
1.69 + including diagonal entries) */
1.70 + int display_data_type;
1.71 + /* specifies how a graphical display of the nodes can be
1.72 + obtained: */
1.73 +#define TSP_UNDEF 0 /* undefined */
1.74 +#define TSP_COORD_DISPLAY 1 /* display is generated from the node
1.75 + coordinates */
1.76 +#define TSP_TWOD_DISPLAY 2 /* explicit coordinates in 2-D are
1.77 + given */
1.78 + /*--------------------------------------------------------------*/
1.79 + /* data part */
1.80 + /* NODE_COORD_SECTION: */
1.81 + double *node_x_coord; /* double node_x_coord[1+dimension]; */
1.82 + double *node_y_coord; /* double node_y_coord[1+dimension]; */
1.83 + /* DISPLAY_DATA_SECTION: */
1.84 + double *dply_x_coord; /* double dply_x_coord[1+dimension]; */
1.85 + double *dply_y_coord; /* double dply_y_coord[1+dimension]; */
1.86 + /* TOUR_SECTION: */
1.87 + int *tour; /* int tour[1+dimension]; */
1.88 + /* EDGE_WEIGHT_SECTION: */
1.89 + int *edge_weight; /* int edge_weight[1+dimension*dimension]; */
1.90 +};
1.91 +
1.92 +#define tsp_read_data _glp_tsp_read_data
1.93 +#define tsp_free_data _glp_tsp_free_data
1.94 +#define tsp_distance _glp_tsp_distance
1.95 +
1.96 +TSP *tsp_read_data(char *fname);
1.97 +/* read TSP instance data */
1.98 +
1.99 +void tsp_free_data(TSP *tsp);
1.100 +/* free TSP instance data */
1.101 +
1.102 +int tsp_distance(TSP *tsp, int i, int j);
1.103 +/* compute distance between two nodes */
1.104 +
1.105 +#endif
1.106 +
1.107 +/* eof */