1 /***************************************************************************/
2 /* */
3 /* ROUTINES FOR CONSTRUCTING TOURS FROM x-VECTORS */
4 /* */
5 /* TSP CODE */
6 /* */
7 /* */
8 /* Written by: Applegate, Bixby, Chvatal, and Cook */
9 /* Date: July 21, 1997 */
10 /* */
11 /* EXPORTED FUNCTIONS: */
12 /* int CCtsp_x_greedy_tour (CCdatagroup *dat, int ncount, int ecount, */
13 /* int *elist, double *x, int *cyc, double *val) */
14 /* FINDS a tour by adding in edges by nonincreasing x-value. */
15 /* -cyc should be an array of length at least ncount */
16 /* -val returns the length of the tour */
17 /* */
18 /* int CCtsp_x_greedy_tour_lk (CCdatagroup *dat, int ncount, int ecount,*/
19 /* int *elist, double *x, int *cyc, double *val) */
20 /* FINDS the x-greedy tour then calls a short LK. */
21 /* */
22 /* NOTES: */
23 /* */
24 /* */
25 /***************************************************************************/
26
27 #include "machdefs.h"
28 #include "util.h"
29 #include "edgegen.h"
30 #include "linkern.h"
31 #include "tsp.h"
32
33 #ifdef CC_PROTOTYPE_ANSI
34
35 static void
36 update_tail (int *tail, int a, int b);
37
38 #else
39
40 static void
41 update_tail ();
42
43 #endif
44
45 #ifdef CC_PROTOTYPE_ANSI
CCtsp_x_greedy_tour_lk(CCdatagroup * dat,int ncount,int ecount,int * elist,double * x,int * cyc,double * val)46 int CCtsp_x_greedy_tour_lk (CCdatagroup *dat, int ncount, int ecount,
47 int *elist, double *x, int *cyc, double *val)
48 #else
49 int CCtsp_x_greedy_tour_lk (dat, ncount, ecount, elist, x, cyc, val)
50 CCdatagroup *dat;
51 int ncount, ecount;
52 int *elist;
53 double *x;
54 int *cyc;
55 double *val;
56 #endif
57 {
58 int rval = 0;
59 int *gcyc = (int *) NULL;
60 int *tlist = (int *) NULL;
61 int tcount;
62 double gval;
63 CCedgegengroup plan;
64
65 *val = 1e30;
66 if (!dat) {
67 fprintf (stderr, "no dat in CCtsp_x_greedy_tour_lk\n");
68 rval = 1; goto CLEANUP;
69 }
70
71 gcyc = CC_SAFE_MALLOC (ncount, int);
72 if (!gcyc) {
73 fprintf (stderr, "out of memory in CCtsp_x_greedy_tour_lk\n");
74 rval = 1; goto CLEANUP;
75 }
76
77 rval = CCtsp_x_greedy_tour (dat, ncount, ecount, elist, x, gcyc,
78 &gval);
79 if (rval) {
80 fprintf (stderr, "CCtsp_x_greedy_tour failed\n"); goto CLEANUP;
81 }
82
83 CCedgegen_init_edgegengroup (&plan);
84 plan.quadnearest = 2;
85
86 rval = CCedgegen_edges (&plan, ncount, dat, (double *) NULL, &tcount,
87 &tlist);
88 if (rval) {
89 fprintf (stderr, "CCedgegen_edges failed\n"); goto CLEANUP;
90 }
91
92 rval = CClinkern_tour (ncount, dat, tcount, tlist, ncount,
93 ncount > 1000 ? 500 : ncount/2, gcyc, cyc, val, 0, 0.0,
94 0.0, (char *) NULL);
95 if (rval) {
96 fprintf (stderr, "CClinkern_tour failed\n"); goto CLEANUP;
97 }
98
99 CLEANUP:
100
101 CC_IFFREE (tlist, int);
102 CC_IFFREE (gcyc, int);
103 return rval;
104 }
105
106 #ifdef CC_PROTOTYPE_ANSI
CCtsp_x_greedy_tour(CCdatagroup * dat,int ncount,int ecount,int * elist,double * x,int * cyc,double * val)107 int CCtsp_x_greedy_tour (CCdatagroup *dat, int ncount, int ecount, int *elist,
108 double *x, int *cyc, double *val)
109 #else
110 int CCtsp_x_greedy_tour (dat, ncount, ecount, elist, x, cyc, val)
111 CCdatagroup *dat;
112 int ncount, ecount;
113 int *elist;
114 double *x;
115 int *cyc;
116 double *val;
117 #endif
118 {
119 int rval = 0;
120 int tcount = 0;
121 int i, a, b;
122 double szeit = CCutil_zeit ();
123 double len;
124 int *perm = (int *) NULL;
125 int *tail = (int *) NULL;
126 int *tcyc = (int *) NULL;
127 char *degree = (char *) NULL;
128
129 printf ("CCtsp_x_greedy_tour ...\n"); fflush (stdout);
130
131 *val = 1e30;
132 if (!dat) {
133 fprintf (stderr, "no dat in CCtsp_x_greedy_tour\n");
134 rval = 1; goto CLEANUP;
135 }
136
137 perm = CC_SAFE_MALLOC (ecount, int);
138 degree = CC_SAFE_MALLOC (ncount, char);
139 tail = CC_SAFE_MALLOC (ncount, int);
140 tcyc = CC_SAFE_MALLOC (2 * ncount, int);
141 if (!perm || !degree || !tail || !tcyc) {
142 fprintf (stderr, "out of memory in CCtsp_x_greedy_tour\n");
143 rval = 1; goto CLEANUP;
144 }
145
146 for (i = 0; i < ncount; i++) {
147 degree[i] = 0;
148 tail[i] = -1;
149 }
150 for (i = 0; i < ecount; i++) {
151 perm[i] = i;
152 }
153
154 CCutil_double_perm_quicksort (perm, x, ecount);
155 len = 0;
156 for (i = ecount - 1; i >= 0; i--) {
157 a = elist[2*perm[i]];
158 b = elist[(2*perm[i]) + 1];
159 if (degree[a] != 2 && degree[b] != 2 && tail[a] != b) {
160 /* add (a, b) to the tour */
161 tcyc[tcount++] = a;
162 tcyc[tcount++] = b;
163 len += (double) CCutil_dat_edgelen (a, b, dat);
164 degree[a]++;
165 degree[b]++;
166 update_tail (tail, a, b);
167 }
168 }
169
170 printf ("%d edges in x-tour\n", tcount / 2); fflush (stdout);
171 a = 0;
172 b = 0;
173 while (tcount < (2*ncount - 2)) {
174 for (; degree[a] == 2; a++);
175 for (b = a + 1; degree[b] == 2 || tail[a] == b; b++);
176 tcyc[tcount++] = a;
177 tcyc[tcount++] = b;
178 degree[a]++;
179 degree[b]++;
180 update_tail (tail, a, b);
181 len += (double) CCutil_dat_edgelen (a, b, dat);
182 }
183
184 if (tcount < 2*ncount) {
185 for (a = 0; degree[a] != 1; a++);
186 for (b = a + 1; degree[b] != 1; b++);
187 tcyc[tcount++] = a;
188 tcyc[tcount++] = b;
189 len += (double) CCutil_dat_edgelen (a, b, dat);
190 }
191
192 printf ("tour length: %.2f (%.2f seconds)\n", len, CCutil_zeit () - szeit);
193 fflush (stdout);
194 *val = len;
195
196 rval = CCutil_edge_to_cycle (ncount, tcyc, cyc);
197 if (rval) {
198 fprintf (stderr, "CCutil_edge_to_cycle failed\n");
199 goto CLEANUP;
200 }
201
202 CLEANUP:
203
204 CC_IFFREE (perm, int);
205 CC_IFFREE (tail, int);
206 CC_IFFREE (tcyc, int);
207 CC_IFFREE (degree, char);
208 return rval;
209 }
210
211 #ifdef CC_PROTOTYPE_ANSI
update_tail(int * tail,int a,int b)212 static void update_tail (int *tail, int a, int b)
213 #else
214 static void update_tail (tail, a, b)
215 int *tail;
216 int a, b;
217 #endif
218 {
219 if (tail[a] == -1) {
220 if (tail[b] == -1) {
221 tail[a] = b;
222 tail[b] = a;
223 } else {
224 tail[a] = tail[b];
225 tail[tail[b]] = a;
226 }
227 } else if (tail[b] == -1) {
228 tail[tail[a]] = b;
229 tail[b] = tail[a];
230 } else {
231 tail[tail[a]] = tail[b];
232 tail[tail[b]] = tail[a];
233 }
234 }
235