1 /****************************************************************************/
2 /* */
3 /* This file is part of CONCORDE */
4 /* */
5 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */
6 /* Vasek Chvatal, and William Cook */
7 /* */
8 /* Permission is granted for academic research use. For other uses, */
9 /* contact the authors for licensing options. */
10 /* */
11 /* Use at your own risk. We make no guarantees about the */
12 /* correctness or usefulness of this code. */
13 /* */
14 /****************************************************************************/
15
16 /****************************************************************************/
17 /* */
18 /* A PROGRAM TO ADD LENGTHS TO A FILE OF EDGES */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: October 5, 1999 */
25 /* */
26 /* SEE short decsribtion in usage (). */
27 /* */
28 /****************************************************************************/
29
30 #include "machdefs.h"
31 #include "util.h"
32
33 static char *tspfname = (char *) NULL;
34 static char *edgefname = (char *) NULL;
35 static char *outfname = (char *) NULL;
36 static int eformat = 0;
37 static int binary_out = 0;
38 static int seed = 0;
39
40
41
42 int
43 main (int ac, char **av);
44
45 static int
46 parseargs (int ac, char **av),
47 get_edges (char *fname, int thirdfield, int ncount, int *ecount,
48 int **elist);
49
50 static void
51 usage (char *fname);
52
53
main(int ac,char ** av)54 int main (int ac, char **av)
55 {
56 int ncount, ecount, rval = 0;
57 int *elist = (int *) NULL;
58 CCdatagroup dat;
59 CCrandstate rstate;
60
61 CCutil_init_datagroup (&dat);
62
63 seed = (int) CCutil_real_zeit ();
64
65 rval = parseargs (ac, av);
66 if (rval) return 1;
67
68 if ((!edgefname || !tspfname)) {
69 usage (av[0]);
70 return 1;
71 }
72
73 CCutil_sprand (seed, &rstate);
74
75 rval = CCutil_gettsplib (tspfname, &ncount, &dat);
76 if (rval) {
77 fprintf (stderr, "CCutil_gettsplib failed\n"); goto CLEANUP;
78 }
79
80 rval = get_edges (edgefname, eformat, ncount, &ecount, &elist);
81 if (rval) {
82 fprintf (stderr, "get_edges failed\n"); goto CLEANUP;
83 }
84
85 printf ("Number of Edges: %d\n", ecount); fflush (stdout);
86 if (outfname) {
87 rval = CCutil_writeedges (ncount, outfname, ecount, elist, &dat,
88 binary_out);
89 if (rval) {
90 fprintf (stderr, "CCutil_writeedges failed\n");
91 }
92 }
93
94 CLEANUP:
95
96 CC_IFFREE (elist, int);
97 CCutil_freedatagroup (&dat);
98
99 return rval;
100 }
101
parseargs(int ac,char ** av)102 static int parseargs (int ac, char **av)
103 {
104 int c;
105 int boptind = 1;
106 char *boptarg = (char *) NULL;
107
108 while ((c = CCutil_bix_getopt (ac, av, "beE:o:T:", &boptind, &boptarg)) != EOF) {
109 switch (c) {
110 case 'b':
111 binary_out = 1;
112 break;
113 case 'e':
114 eformat = 1;
115 break;
116 case 'E':
117 edgefname = boptarg;
118 break;
119 case 'o':
120 outfname = boptarg;
121 break;
122 case 'T':
123 tspfname = boptarg;
124 break;
125 case CC_BIX_GETOPT_UNKNOWN:
126 case '?':
127 default:
128 usage (av[0]);
129 return 1;
130 }
131 }
132
133 return 0;
134 }
135
usage(char * fname)136 static void usage (char *fname)
137 {
138 fprintf (stderr, "Usage: %s [-flags below]\n", fname);
139 fprintf (stderr, " -b write a binary file\n");
140 fprintf (stderr, " -e the edge file has floating point third field (ignore it)\n");
141 fprintf (stderr, " -E f file with list of edges (default is no length field\n");
142 fprintf (stderr, " -T f TSPLIB file to specify lengths\n");
143 fprintf (stderr, " -o f output file (for the edge list)\n");
144 fprintf (stderr, " NOTE: -E and -T must be specified\n");
145 }
146
147
get_edges(char * fname,int thirdfield,int ncount,int * ecount,int ** elist)148 static int get_edges (char *fname, int thirdfield, int ncount, int *ecount,
149 int **elist)
150 {
151 FILE *f = (FILE *) NULL;
152 int i, k;
153 int rval = 0;
154
155 f = fopen (fname, "r");
156 if (f == (FILE *) NULL) {
157 perror (fname);
158 fprintf (stderr, "Unable to open %s for input\n", fname);
159 return 1;
160 }
161
162 k = CCutil_readint (f);
163 if (k != ncount) {
164 fprintf (stderr, "TSP file and edge file do not match\n");
165 rval = 1; goto CLEANUP;
166 }
167
168 *ecount = CCutil_readint (f);
169 *elist = CC_SAFE_MALLOC(2 * (*ecount), int);
170 if (!(*elist)) {
171 fprintf (stderr, "out of memory n get_edges\n");
172 rval = 1; goto CLEANUP;
173 }
174
175 for (i = 0; i < *ecount; i++) {
176 (*elist)[2*i] = CCutil_readint (f);
177 (*elist)[2*i+1] = CCutil_readint (f);
178 if (thirdfield) {
179 fscanf (f, "%*f");
180 }
181 }
182
183 CLEANUP:
184
185 fclose (f);
186 return rval;
187 }
188