alpar@1: /* glptsp.h (TSP format) */
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@1: *
alpar@1: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@1: *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@1: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@1: *  E-mail: <mao@gnu.org>.
alpar@1: *
alpar@1: *  GLPK is free software: you can redistribute it and/or modify it
alpar@1: *  under the terms of the GNU General Public License as published by
alpar@1: *  the Free Software Foundation, either version 3 of the License, or
alpar@1: *  (at your option) any later version.
alpar@1: *
alpar@1: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@1: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@1: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@1: *  License for more details.
alpar@1: *
alpar@1: *  You should have received a copy of the GNU General Public License
alpar@1: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #ifndef GLPTSP_H
alpar@1: #define GLPTSP_H
alpar@1: 
alpar@1: typedef struct TSP TSP;
alpar@1: 
alpar@1: struct TSP
alpar@1: {     /* TSP (or related problem) instance in the format described in
alpar@1:          the report [G.Reinelt, TSPLIB 95] */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* the specification part */
alpar@1:       char *name;
alpar@1:       /* identifies the data file */
alpar@1:       int type;
alpar@1:       /* specifies the type of data: */
alpar@1: #define TSP_UNDEF             0  /* undefined */
alpar@1: #define TSP_TSP               1  /* symmetric TSP */
alpar@1: #define TSP_ATSP              2  /* asymmetric TSP */
alpar@1: #define TSP_TOUR              3  /* collection of tours */
alpar@1:       char *comment;
alpar@1:       /* additional comments (usually the name of the contributor or
alpar@1:          creator of the problem instance is given here) */
alpar@1:       int dimension;
alpar@1:       /* for a TSP or ATSP, the dimension is the number of its nodes
alpar@1:          for a TOUR it is the dimension of the corresponding problem */
alpar@1:       int edge_weight_type;
alpar@1:       /* specifies how the edge weights (or distances) are given: */
alpar@1: #define TSP_UNDEF             0  /* undefined */
alpar@1: #define TSP_EXPLICIT          1  /* listed explicitly */
alpar@1: #define TSP_EUC_2D            2  /* Eucl. distances in 2-D */
alpar@1: #define TSP_CEIL_2D           3  /* Eucl. distances in 2-D rounded up */
alpar@1: #define TSP_GEO               4  /* geographical distances */
alpar@1: #define TSP_ATT               5  /* special distance function */
alpar@1:       int edge_weight_format;
alpar@1:       /* describes the format of the edge weights if they are given
alpar@1:          explicitly: */
alpar@1: #define TSP_UNDEF             0  /* undefined */
alpar@1: #define TSP_FUNCTION          1  /* given by a function */
alpar@1: #define TSP_FULL_MATRIX       2  /* given by a full matrix */
alpar@1: #define TSP_UPPER_ROW         3  /* upper triangulat matrix (row-wise
alpar@1:                                     without diagonal entries) */
alpar@1: #define TSP_LOWER_DIAG_ROW    4  /* lower triangular matrix (row-wise
alpar@1:                                     including diagonal entries) */
alpar@1:       int display_data_type;
alpar@1:       /* specifies how a graphical display of the nodes can be
alpar@1:          obtained: */
alpar@1: #define TSP_UNDEF             0  /* undefined */
alpar@1: #define TSP_COORD_DISPLAY     1  /* display is generated from the node
alpar@1:                                     coordinates */
alpar@1: #define TSP_TWOD_DISPLAY      2  /* explicit coordinates in 2-D are
alpar@1:                                     given */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* data part */
alpar@1:       /* NODE_COORD_SECTION: */
alpar@1:       double *node_x_coord; /* double node_x_coord[1+dimension]; */
alpar@1:       double *node_y_coord; /* double node_y_coord[1+dimension]; */
alpar@1:       /* DISPLAY_DATA_SECTION: */
alpar@1:       double *dply_x_coord; /* double dply_x_coord[1+dimension]; */
alpar@1:       double *dply_y_coord; /* double dply_y_coord[1+dimension]; */
alpar@1:       /* TOUR_SECTION: */
alpar@1:       int *tour; /* int tour[1+dimension]; */
alpar@1:       /* EDGE_WEIGHT_SECTION: */
alpar@1:       int *edge_weight; /* int edge_weight[1+dimension*dimension]; */
alpar@1: };
alpar@1: 
alpar@1: #define tsp_read_data         _glp_tsp_read_data
alpar@1: #define tsp_free_data         _glp_tsp_free_data
alpar@1: #define tsp_distance          _glp_tsp_distance
alpar@1: 
alpar@1: TSP *tsp_read_data(char *fname);
alpar@1: /* read TSP instance data */
alpar@1: 
alpar@1: void tsp_free_data(TSP *tsp);
alpar@1: /* free TSP instance data */
alpar@1: 
alpar@1: int tsp_distance(TSP *tsp, int i, int j);
alpar@1: /* compute distance between two nodes */
alpar@1: 
alpar@1: #endif
alpar@1: 
alpar@1: /* eof */