COIN-OR::LEMON - Graph Library

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

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: 4.3 KB
Line 
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, 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#ifndef GLPTSP_H
26#define GLPTSP_H
27
28typedef struct TSP TSP;
29
30struct 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
93TSP *tsp_read_data(char *fname);
94/* read TSP instance data */
95
96void tsp_free_data(TSP *tsp);
97/* free TSP instance data */
98
99int tsp_distance(TSP *tsp, int i, int j);
100/* compute distance between two nodes */
101
102#endif
103
104/* eof */
Note: See TracBrowser for help on using the repository browser.