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