[1] | 1 | /* glptsp.h (TSP format) */ |
---|
| 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 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 | #ifndef GLPTSP_H |
---|
| 26 | #define GLPTSP_H |
---|
| 27 | |
---|
| 28 | typedef struct TSP TSP; |
---|
| 29 | |
---|
| 30 | struct TSP |
---|
| 31 | { /* TSP (or related problem) instance in the format described in |
---|
| 32 | the report [G.Reinelt, TSPLIB 95] */ |
---|
| 33 | /*--------------------------------------------------------------*/ |
---|
| 34 | /* the specification part */ |
---|
| 35 | char *name; |
---|
| 36 | /* identifies the data file */ |
---|
| 37 | int type; |
---|
| 38 | /* specifies the type of data: */ |
---|
| 39 | #define TSP_UNDEF 0 /* undefined */ |
---|
| 40 | #define TSP_TSP 1 /* symmetric TSP */ |
---|
| 41 | #define TSP_ATSP 2 /* asymmetric TSP */ |
---|
| 42 | #define TSP_TOUR 3 /* collection of tours */ |
---|
| 43 | char *comment; |
---|
| 44 | /* additional comments (usually the name of the contributor or |
---|
| 45 | creator of the problem instance is given here) */ |
---|
| 46 | int dimension; |
---|
| 47 | /* for a TSP or ATSP, the dimension is the number of its nodes |
---|
| 48 | for a TOUR it is the dimension of the corresponding problem */ |
---|
| 49 | int edge_weight_type; |
---|
| 50 | /* specifies how the edge weights (or distances) are given: */ |
---|
| 51 | #define TSP_UNDEF 0 /* undefined */ |
---|
| 52 | #define TSP_EXPLICIT 1 /* listed explicitly */ |
---|
| 53 | #define TSP_EUC_2D 2 /* Eucl. distances in 2-D */ |
---|
| 54 | #define TSP_CEIL_2D 3 /* Eucl. distances in 2-D rounded up */ |
---|
| 55 | #define TSP_GEO 4 /* geographical distances */ |
---|
| 56 | #define TSP_ATT 5 /* special distance function */ |
---|
| 57 | int edge_weight_format; |
---|
| 58 | /* describes the format of the edge weights if they are given |
---|
| 59 | explicitly: */ |
---|
| 60 | #define TSP_UNDEF 0 /* undefined */ |
---|
| 61 | #define TSP_FUNCTION 1 /* given by a function */ |
---|
| 62 | #define TSP_FULL_MATRIX 2 /* given by a full matrix */ |
---|
| 63 | #define TSP_UPPER_ROW 3 /* upper triangulat matrix (row-wise |
---|
| 64 | without diagonal entries) */ |
---|
| 65 | #define TSP_LOWER_DIAG_ROW 4 /* lower triangular matrix (row-wise |
---|
| 66 | including diagonal entries) */ |
---|
| 67 | int display_data_type; |
---|
| 68 | /* specifies how a graphical display of the nodes can be |
---|
| 69 | obtained: */ |
---|
| 70 | #define TSP_UNDEF 0 /* undefined */ |
---|
| 71 | #define TSP_COORD_DISPLAY 1 /* display is generated from the node |
---|
| 72 | coordinates */ |
---|
| 73 | #define TSP_TWOD_DISPLAY 2 /* explicit coordinates in 2-D are |
---|
| 74 | given */ |
---|
| 75 | /*--------------------------------------------------------------*/ |
---|
| 76 | /* data part */ |
---|
| 77 | /* NODE_COORD_SECTION: */ |
---|
| 78 | double *node_x_coord; /* double node_x_coord[1+dimension]; */ |
---|
| 79 | double *node_y_coord; /* double node_y_coord[1+dimension]; */ |
---|
| 80 | /* DISPLAY_DATA_SECTION: */ |
---|
| 81 | double *dply_x_coord; /* double dply_x_coord[1+dimension]; */ |
---|
| 82 | double *dply_y_coord; /* double dply_y_coord[1+dimension]; */ |
---|
| 83 | /* TOUR_SECTION: */ |
---|
| 84 | int *tour; /* int tour[1+dimension]; */ |
---|
| 85 | /* EDGE_WEIGHT_SECTION: */ |
---|
| 86 | int *edge_weight; /* int edge_weight[1+dimension*dimension]; */ |
---|
| 87 | }; |
---|
| 88 | |
---|
| 89 | #define tsp_read_data _glp_tsp_read_data |
---|
| 90 | #define tsp_free_data _glp_tsp_free_data |
---|
| 91 | #define tsp_distance _glp_tsp_distance |
---|
| 92 | |
---|
| 93 | TSP *tsp_read_data(char *fname); |
---|
| 94 | /* read TSP instance data */ |
---|
| 95 | |
---|
| 96 | void tsp_free_data(TSP *tsp); |
---|
| 97 | /* free TSP instance data */ |
---|
| 98 | |
---|
| 99 | int tsp_distance(TSP *tsp, int i, int j); |
---|
| 100 | /* compute distance between two nodes */ |
---|
| 101 | |
---|
| 102 | #endif |
---|
| 103 | |
---|
| 104 | /* eof */ |
---|