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 /* COMPUTING INITIAL EDGE SETS */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: May 9, 1995 */
25 /* Changes: 6.8.1996 (bico) fixed bug in f2match nearest */
26 /* */
27 /* */
28 /* EXPORTED FUNCTIONS: */
29 /* */
30 /* int CCedgegen_read (char *egname, CCedgegengroup *plan) */
31 /* READS an edgegen description from file egname. */
32 /* -egname the name of a file */
33 /* -plan returns the description of the mix of edges (can be used */
34 /* in a call to CCedgegen_edges () to obtain the edgeset). */
35 /* */
36 /* int CCedgegen_edges (CCedgegengroup *plan, int ncount, */
37 /* CCdatagroup *dat, double *wcoord, int *ecount, int **elist, */
38 /* int silent, CCrandstate *rstate) */
39 /* RETURNS the set of edges described in plan. */
40 /* -plan describes the mix of edges */
41 /* -ncount is the number of nodes */
42 /* -dat contains the info to generate edge lengths */
43 /* -wcoord are nodeweights for Held-Karp style edge lengths, using */
44 /* len[i,j] + wcoord[i] + wcoord[j] (wcoord can be NULL) */
45 /* -ecount returns the number of edges */
46 /* -elist returns the edges in end1 end2 format */
47 /* -silent will suppress print messages if set to a nonzero value. */
48 /* */
49 /* void CCedgegen_init_edgegengroup (CCedgegengroup *plan) */
50 /* SETS the fields in plan to 0 (since there are so many fields to */
51 /* to deal with) */
52 /* */
53 /* NOTES: */
54 /* To use CCedgegen_edges, look at the defintion of CCedgegengroup */
55 /* in edgegen.h - you should be able to guess what the parmeters mean. */
56 /* Note that wcoord is only used by a limited number of the generating */
57 /* routines, for example nearest, but not linkern. */
58 /* The functions CCedgegen_edges and CCedgegen_read will return */
59 /* nonzero values if they fail (for example, if they run out of memory. */
60 /* The description file passed to CCedgegen_read should contain a */
61 /* list of some of the following commands: */
62 /* EDGEGEN RANDOM # */
63 /* -find # random edges */
64 /* EDGEGEN NEAREST # */
65 /* -find the nearest # edges */
66 /* EDGEGEN QUADNEAREST # */
67 /* -find the quadrant-nearest # edges */
68 /* EDGEGEN FRAC_TWOMATCH_NEAREST # [PRICED] [BASIC] */
69 /* -find the nearest # using the reduced costs of a */
70 /* fractional 2-matching as the edgelengths. If either */
71 /* of the optional arguments PRICED or BASIC is */
72 /* specified then the 2-matching used will be either */
73 /* priced against the complete edgeset or converted to */
74 /* a basic optimal solution (or both). */
75 /* EDGEGEN GREEDY_TOUR */
76 /* -find a greedy tour */
77 /* EDGEGEN BORUVKA_TOUR */
78 /* -find a Boruvka tour */
79 /* EDGEGEN QBORUVKA_TOUR */
80 /* -find a quick Boruvka tour */
81 /* EDGEGEN NN_TOUR # */
82 /* -find # nearest-neighbor tours */
83 /* EDGEGEN RANDOM_TOUR # */
84 /* -find # random tours */
85 /* EDGEGEN TWOOPT_TOUR # */
86 /* -find # 2-opt tours */
87 /* EDGEGEN TWOPT5_TOUR # */
88 /* -find # 2.5-opt tours */
89 /* EDGEGEN THREEOPT_TOUR # */
90 /* -find # 3-opt tours */
91 /* EDGEGEN LINKERN #1 #2 [QUADNEAREST #3] [NEAREST #4] */
92 /* [GREEDY_START | NN_START | RANDOM_START */
93 /* | BORUVKA_START | QBORUVKA_START] */
94 /* -find #1 Iterated Lin-Kernighan tours using #2 */
95 /* kicks. */
96 /* The good edgeset can be specified by the optional */
97 /* arguments QUADNEAREST and NEAREST (the two can be */
98 /* used together). The initial tours can be specfied */
99 /* by using one of GREEDY_START, NN_START, */
100 /* BORUVKA_START, QBORUVKA_START, or RANDOM_START. */
101 /* EDGEGEN NN_TWOMATCH # */
102 /* -find # nearest-neighbor 2-matchings */
103 /* EDGEGEN TREE */
104 /* -find a minimum weight spanning tree. */
105 /* EDGEGEN FRAC_TWOMATCH [PRICED] [BASIC] */
106 /* -find a minmum weight 2-matching (priced against the */
107 /* complete edgeset) (that is a basic optimal */
108 /* solution) */
109 /* EDGEGEN DELAUNAY */
110 /* -find the edges in the (Euclidean-norm) Delaunay */
111 /* triangulation (using Steve Fortune's sweep2 code). */
112 /* M_LINKERN */
113 /* -find # lin ker matchings */
114 /* */
115 /****************************************************************************/
116
117 #include "machdefs.h"
118 #include "util.h"
119 #include "edgegen.h"
120 #include "kdtree.h"
121 #include "linkern.h"
122 #include "fmatch.h"
123 #include "delaunay.h"
124 #include "mlinkern.h"
125 #include "macrorus.h"
126
127 typedef struct intptr {
128 int this;
129 struct intptr *next;
130 } intptr;
131
132 typedef struct tabledat {
133 intptr **table;
134 int tabletotal;
135 CCptrworld *intptr_world;
136 } tabledat;
137
138
139 static int
140 call_kdtree_build (CCkdtree *kt, int ncount, CCdatagroup *dat,
141 double *wcoord, int *built_a_tree, int silent, CCrandstate *rstate),
142 call_random_edge (int ncount, CCdatagroup *dat, int ecount, tabledat *td,
143 int silent, CCrandstate *rstate),
144 call_nearest (int ncount, CCdatagroup *dat, double *wcoord, int nearnum,
145 CCkdtree *kt, tabledat *td, int silent, CCrandstate *rstate),
146 work_nearest (CCkdtree *kt, int ncount, int nearnum, CCdatagroup *dat,
147 double *wcoord, int *ecount, int **elist, int silent,
148 CCrandstate *rstate),
149 call_quadnearest (int ncount, CCdatagroup *dat, double *wcoord,
150 int nearnum, CCkdtree *kt, tabledat *td, int silent,
151 CCrandstate *rstate),
152 work_quadnearest (CCkdtree *kt, int ncount, int nearnum, CCdatagroup *dat,
153 double *wcoord, int *ecount, int **elist, int silent,
154 CCrandstate *rstate),
155 call_delaunay (int ncount, CCdatagroup *dat, tabledat *td, int silent),
156 call_mlinkern (int ncount, CCdatagroup *dat, CCkdtree *kt, int iterations,
157 tabledat *td, int silent, CCrandstate *rstate),
158 call_random_tour (int ncount, CCdatagroup *dat, int number, tabledat *td,
159 int silent, CCrandstate *rstate),
160 call_nearest_tour (int ncount, CCdatagroup *dat, int number, CCkdtree *kt,
161 tabledat *td, int silent, CCrandstate *rstate),
162 work_nearest_tour (CCkdtree *kt, int ncount, int start, CCdatagroup *dat,
163 int *tour, double *val, int silent, CCrandstate *rstate),
164 call_greedy_tour (int ncount, CCdatagroup *dat, CCkdtree *kt,
165 tabledat *td, int silent, CCrandstate *rstate),
166 call_boruvka_tour (int ncount, CCdatagroup *dat, CCkdtree *kt,
167 tabledat *td, int silent, CCrandstate *rstate),
168 call_qboruvka_tour (int ncount, CCdatagroup *dat, CCkdtree *kt,
169 tabledat *td, int silent, CCrandstate *rstate),
170 call_twoopt_tour (int ncount, CCdatagroup *dat, CCkdtree *kt, int number,
171 int two_and_a_half, int use_3opt, tabledat *td, int silent,
172 CCrandstate *rstate),
173 call_linkern (int ncount, CCdatagroup *dat, CCkdtree *kt,
174 CCedgegengroup *plan, tabledat *td, int silent, CCrandstate *rstate),
175 call_nearest_twomatch (int ncount, CCdatagroup *dat, int number,
176 CCkdtree *kt, tabledat *td, int silent, CCrandstate *rstate),
177 call_f2match (int ncount, CCdatagroup *dat, CCkdtree *kt, int priceit,
178 int basic, tabledat *td, int silent, CCrandstate *rstate),
179 call_f2match_nearest (int ncount, CCdatagroup *dat, CCkdtree *kt,
180 int number, int priceit, int basic, tabledat *td, int silent,
181 CCrandstate *rstate),
182 call_spanning_tree (int ncount, CCdatagroup *dat, double *wcoord,
183 CCkdtree *kt, tabledat *td, int silent, CCrandstate *rstate),
184 f2match_initial_edgeset (int ncount, CCdatagroup *dat, CCkdtree *kt,
185 int *ecount, int **elist, int **elen, tabledat *td, int silent,
186 CCrandstate *rstate),
187 put_tour_in_table (tabledat *td, int ncount, int *tour),
188 put_list_in_table (tabledat *td, int ecount, int *elist),
189 put_in_table (tabledat *td, int i, int j),
190 collect_table_edges (tabledat *td, int ncount, int *ecount, int **elist),
191 collect_edge_lengths (int ecount, int *elist, CCdatagroup *dat,
192 int **elen);
193
194 static void
195 randcycle (int ncount, int *cyc, CCdatagroup *dat, double *val,
196 CCrandstate *rstate);
197
198
CC_PTRWORLD_LIST_ROUTINES(intptr,int,intptralloc,intptr_bulk_alloc,intptrfree,intptr_listadd,intptr_listfree)199 CC_PTRWORLD_LIST_ROUTINES (intptr, int, intptralloc, intptr_bulk_alloc,
200 intptrfree, intptr_listadd, intptr_listfree)
201 CC_PTRWORLD_LEAKS_ROUTINE (intptr, intptr_check_leaks, this, int)
202
203
204 int CCedgegen_edges (CCedgegengroup *plan, int ncount, CCdatagroup *dat,
205 double *wcoord, int *ecount, int **elist, int silent,
206 CCrandstate *rstate)
207 {
208 int rval = 0;
209 int i;
210 int total, onlist;
211 CCkdtree kt;
212 int built_a_tree = 0;
213 double szeit = CCutil_zeit ();
214 int norm;
215 tabledat td;
216 CCptrworld intptr_world;
217
218 td.table = (intptr **) NULL;
219 td.tabletotal = 0;
220 CCptrworld_init (&intptr_world);
221 td.intptr_world = &intptr_world;
222
223 *ecount = 0;
224 *elist = (int *) NULL;
225
226 if (ncount < 3) {
227 fprintf (stderr, "Cannot run CCedgegen_edges in an %d node graph\n",
228 ncount);
229 return 1;
230 }
231
232 td.table = CC_SAFE_MALLOC (ncount, intptr *);
233 if (!td.table) {
234 rval = 1;
235 goto CLEANUP;
236 }
237 for (i = 0; i < ncount; i++)
238 td.table[i] = (intptr *) NULL;
239 td.tabletotal = 0;
240
241 if (plan->random) {
242 rval = call_random_edge (ncount, dat, plan->random, &td, silent,
243 rstate);
244 if (rval) {
245 fprintf (stderr, "call_random_edge failed\n"); goto CLEANUP;
246 }
247 }
248
249 if (plan->nearest) {
250 if (!built_a_tree) {
251 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
252 silent, rstate)) {
253 fprintf (stderr, "call_kdtree_build failed\n");
254 rval = 1;
255 goto CLEANUP;
256 }
257 }
258 if (call_nearest (ncount, dat, wcoord, plan->nearest, &kt, &td,
259 silent, rstate)) {
260 fprintf (stderr, "call_nearest failed\n");
261 rval = 1;
262 goto CLEANUP;
263 }
264 }
265 if (plan->quadnearest) {
266 if (!built_a_tree) {
267 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
268 silent, rstate)) {
269 fprintf (stderr, "call_kdtree_build failed\n");
270 rval = 1;
271 goto CLEANUP;
272 }
273 }
274 if (call_quadnearest (ncount, dat, wcoord, plan->quadnearest, &kt, &td,
275 silent, rstate)) {
276 fprintf (stderr, "call_quadnearest failed\n");
277 rval = 1;
278 goto CLEANUP;
279 }
280 }
281 if (plan->delaunay) {
282 if (call_delaunay (ncount, dat, &td, silent)) {
283 fprintf (stderr, "call_delaunay failed\n");
284 rval = 1;
285 goto CLEANUP;
286 }
287 }
288 CCutil_dat_getnorm (dat, &norm);
289 if (plan->mlinkern) {
290 if (!built_a_tree) {
291 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
292 silent, rstate)) {
293 fprintf (stderr, "call_kdtree_build failed\n");
294 rval = 1;
295 goto CLEANUP;
296 }
297 }
298 if ((norm & CC_NORM_BITS) != CC_KD_NORM_TYPE) {
299 printf ("Cannot run matching Lin-Kernighan with this norm\n");
300 fflush (stdout);
301 } else {
302 if (call_mlinkern (ncount, dat, &kt, plan->mlinkern, &td,
303 silent, rstate)) {
304 fprintf (stderr, "call_mlinkern failed\n");
305 rval = 1;
306 goto CLEANUP;
307 }
308 }
309 }
310 if (plan->tour.random_count) {
311 if (call_random_tour (ncount, dat, plan->tour.random_count, &td,
312 silent, rstate)) {
313 fprintf (stderr, "call_random_tour failed\n");
314 rval = 1;
315 goto CLEANUP;
316 }
317 }
318 if (plan->tour.nearest_count) {
319 if (!built_a_tree) {
320 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
321 silent, rstate)) {
322 fprintf (stderr, "call_kdtree_build failed\n");
323 rval = 1;
324 goto CLEANUP;
325 }
326 }
327 if (call_nearest_tour (ncount, dat, plan->tour.nearest_count, &kt,
328 &td, silent, rstate)) {
329 fprintf (stderr, "call_nearest_tour failed\n");
330 rval = 1;
331 goto CLEANUP;
332 }
333 }
334 if (plan->tour.greedy) {
335 if (!built_a_tree) {
336 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
337 silent, rstate)) {
338 fprintf (stderr, "call_kdtree_build failed\n");
339 rval = 1;
340 goto CLEANUP;
341 }
342 }
343 if (call_greedy_tour (ncount, dat, &kt, &td, silent, rstate)) {
344 fprintf (stderr, "call_greedy_tour failed\n");
345 rval = 1;
346 goto CLEANUP;
347 }
348 }
349 if (plan->tour.boruvka) {
350 if (!built_a_tree) {
351 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
352 silent, rstate)) {
353 fprintf (stderr, "call_kdtree_build failed\n");
354 rval = 1;
355 goto CLEANUP;
356 }
357 }
358 if (call_boruvka_tour (ncount, dat, &kt, &td, silent, rstate)) {
359 fprintf (stderr, "call_boruvka_tour failed\n");
360 rval = 1;
361 goto CLEANUP;
362 }
363 }
364 if (plan->tour.qboruvka) {
365 if (!built_a_tree) {
366 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
367 silent, rstate)) {
368 fprintf (stderr, "call_kdtree_build failed\n");
369 rval = 1;
370 goto CLEANUP;
371 }
372 }
373 if (call_qboruvka_tour (ncount, dat, &kt, &td, silent, rstate)) {
374 fprintf (stderr, "call_qboruvka_tour failed\n");
375 rval = 1;
376 goto CLEANUP;
377 }
378 }
379 if (plan->tour.twoopt_count) {
380 if (!built_a_tree) {
381 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
382 silent, rstate)) {
383 fprintf (stderr, "call_kdtree_build failed\n");
384 rval = 1;
385 goto CLEANUP;
386 }
387 }
388 if (call_twoopt_tour (ncount, dat, &kt, plan->tour.twoopt_count,
389 0, 0, &td, silent, rstate)) {
390 fprintf (stderr, "call_twoopt_tour failed\n");
391 rval = 1;
392 goto CLEANUP;
393 }
394 }
395 if (plan->tour.twoopt5_count) {
396 if (!built_a_tree) {
397 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
398 silent, rstate)) {
399 fprintf (stderr, "call_kdtree_build failed\n");
400 rval = 1;
401 goto CLEANUP;
402 }
403 }
404 if (call_twoopt_tour (ncount, dat, &kt, plan->tour.twoopt5_count,
405 1, 0, &td, silent, rstate)) {
406 fprintf (stderr, "call_twoopt_tour failed\n");
407 rval = 1;
408 goto CLEANUP;
409 }
410 }
411 if (plan->tour.threeopt_count) {
412 if (!built_a_tree) {
413 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
414 silent, rstate)) {
415 fprintf (stderr, "call_kdtree_build failed\n");
416 rval = 1;
417 goto CLEANUP;
418 }
419 }
420 if (call_twoopt_tour (ncount, dat, &kt, plan->tour.threeopt_count,
421 0, 1, &td, silent, rstate)) {
422 fprintf (stderr, "call_threeopt_tour failed\n");
423 rval = 1;
424 goto CLEANUP;
425 }
426 }
427 if (plan->linkern.count) {
428 if (!built_a_tree) {
429 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
430 silent, rstate)) {
431 fprintf (stderr, "call_kdtree_build failed\n");
432 rval = 1;
433 goto CLEANUP;
434 }
435 }
436 if (call_linkern (ncount, dat, &kt, plan, &td, silent, rstate)) {
437 fprintf (stderr, "call_linkern failed\n");
438 rval = 1;
439 goto CLEANUP;
440 }
441 }
442 if (plan->want_tree) {
443 if (!built_a_tree) {
444 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
445 silent, rstate)) {
446 fprintf (stderr, "call_kdtree_build failed\n");
447 rval = 1;
448 goto CLEANUP;
449 }
450 }
451 if (call_spanning_tree (ncount, dat, wcoord, &kt, &td, silent,
452 rstate)) {
453 fprintf (stderr, "call_spanning_tree failed\n");
454 rval = 1;
455 goto CLEANUP;
456 }
457 }
458 if (plan->nearest_twomatch_count) {
459 if (!built_a_tree) {
460 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
461 silent, rstate)) {
462 fprintf (stderr, "call_kdtree_build failed\n");
463 rval = 1;
464 goto CLEANUP;
465 }
466 }
467 if (call_nearest_twomatch (ncount, dat, plan->nearest_twomatch_count,
468 &kt, &td, silent, rstate)) {
469 fprintf (stderr, "call_nearest_twomatch failed\n");
470 rval = 1;
471 goto CLEANUP;
472 }
473 }
474 if (plan->f2match.wantit) {
475 if (!built_a_tree) {
476 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
477 silent, rstate)) {
478 fprintf (stderr, "call_kdtree_build failed\n");
479 rval = 1;
480 goto CLEANUP;
481 }
482 }
483 if (call_f2match (ncount, dat, &kt, plan->f2match.priced,
484 plan->f2match.basic, &td, silent, rstate)) {
485 fprintf (stderr, "call_f2match failed\n");
486 rval = 1;
487 goto CLEANUP;
488 }
489 }
490 if (plan->f2match_nearest.number) {
491 if (!built_a_tree) {
492 if (call_kdtree_build (&kt, ncount, dat, wcoord, &built_a_tree,
493 silent, rstate)) {
494 fprintf (stderr, "call_kdtree_build failed\n");
495 rval = 1;
496 goto CLEANUP;
497 }
498 }
499 if (call_f2match_nearest (ncount, dat, &kt,
500 plan->f2match_nearest.number, plan->f2match_nearest.priced,
501 plan->f2match_nearest.basic, &td, silent, rstate)) {
502 fprintf (stderr, "call f2match_nearest failed\n");
503 rval = 1;
504 goto CLEANUP;
505 }
506 }
507
508 if (!silent) {
509 printf ("Edgegen total edges: %d (%.2f seconds)\n", td.tabletotal,
510 CCutil_zeit () - szeit);
511 fflush (stdout);
512 }
513
514 rval = collect_table_edges (&td, ncount, ecount, elist);
515 if (rval) {
516 fprintf (stderr, "collect_table_edges failed\n");
517 goto CLEANUP;
518 }
519
520 if (intptr_check_leaks (&intptr_world, &total, &onlist)) {
521 fprintf (stderr, "WARNING: %d outstanding intptrs in kdnear\n",
522 total - onlist);
523 }
524
525 CLEANUP:
526
527 if (built_a_tree)
528 CCkdtree_free (&kt);
529 CCptrworld_delete (&intptr_world);
530
531 CC_IFFREE (td.table, intptr *);
532
533 return rval;
534 }
535
call_kdtree_build(CCkdtree * kt,int ncount,CCdatagroup * dat,double * wcoord,int * built_a_tree,int silent,CCrandstate * rstate)536 static int call_kdtree_build (CCkdtree *kt, int ncount, CCdatagroup *dat,
537 double *wcoord, int *built_a_tree, int silent, CCrandstate *rstate)
538 {
539 double tzeit;
540 int norm;
541
542 *built_a_tree = 0;
543 CCutil_dat_getnorm (dat, &norm);
544 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
545 tzeit = CCutil_zeit ();
546 if (CCkdtree_build (kt, ncount, dat, wcoord, rstate)) {
547 fprintf (stderr, "CCkdtree_build failed\n");
548 return 1;
549 }
550 if (!silent) {
551 printf ("Built CCkdtree: %.2f (seconds)\n", CCutil_zeit () - tzeit);
552 fflush (stdout);
553 }
554 *built_a_tree = 1;
555 }
556 return 0;
557 }
558
CCedgegen_init_edgegengroup(CCedgegengroup * plan)559 void CCedgegen_init_edgegengroup (CCedgegengroup *plan)
560 {
561 plan->linkern.count = 0;
562 plan->linkern.quadnearest = 0;
563 plan->linkern.nearest = 0;
564 plan->linkern.greedy_start = 0;
565 plan->linkern.random_start = 0;
566 plan->linkern.nearest_start = 0;
567 plan->linkern.boruvka_start = 0;
568 plan->linkern.qboruvka_start = 0;
569 plan->linkern.nkicks = 0;
570
571 plan->tour.twoopt_count = 0;
572 plan->tour.twoopt5_count = 0;
573 plan->tour.threeopt_count = 0;
574 plan->tour.greedy = 0;
575 plan->tour.boruvka = 0;
576 plan->tour.qboruvka = 0;
577 plan->tour.nearest_count = 0;
578 plan->tour.random_count = 0;
579
580 plan->f2match.wantit = 0;
581 plan->f2match.basic = 0;
582 plan->f2match.priced = 0;
583
584 plan->f2match_nearest.number = 0;
585 plan->f2match_nearest.basic = 0;
586 plan->f2match_nearest.priced = 0;
587
588 plan->random = 0;
589 plan->nearest = 0;
590 plan->quadnearest = 0;
591 plan->want_tree = 0;
592 plan->nearest_twomatch_count = 0;
593
594 plan->delaunay = 0;
595 plan->mlinkern = 0;
596 }
597
call_random_edge(int ncount,CCdatagroup * dat,int ecount,tabledat * td,int silent,CCrandstate * rstate)598 static int call_random_edge (int ncount, CCdatagroup *dat, int ecount,
599 tabledat *td, int silent, CCrandstate *rstate)
600 {
601 double szeit = CCutil_zeit ();
602 int current = td->tabletotal, rval = 0;
603 int *elist = (int *) NULL;
604 int *elen = (int *) NULL;
605
606 rval = CCutil_genedgelist (ncount, ecount, &elist, &elen, dat, 0, rstate);
607 if (rval) {
608 fprintf (stderr, "CCutil_genedgelist failed\n"); goto CLEANUP;
609 }
610
611 rval = put_list_in_table (td, ecount, elist);
612 if (rval) {
613 fprintf (stderr, "put_list_in_table failed\n"); goto CLEANUP;
614 }
615
616 if (silent) {
617 printf ("Random added %d edges (%.2f seconds)\n",
618 td->tabletotal - current, CCutil_zeit () - szeit);
619 fflush (stdout);
620 }
621
622 CLEANUP:
623
624 CC_IFFREE (elist, int);
625 CC_IFFREE (elen, int);
626
627 return rval;
628 }
629
call_nearest(int ncount,CCdatagroup * dat,double * wcoord,int nearnum,CCkdtree * kt,tabledat * td,int silent,CCrandstate * rstate)630 static int call_nearest (int ncount, CCdatagroup *dat, double *wcoord,
631 int nearnum, CCkdtree *kt, tabledat *td, int silent,
632 CCrandstate *rstate)
633 {
634 double szeit = CCutil_zeit ();
635 int current = td->tabletotal;
636 int tcount = 0;
637 int *tlist = (int *) NULL;
638
639
640 if (work_nearest (kt, ncount, nearnum, dat, wcoord, &tcount, &tlist,
641 silent, rstate)) {
642 fprintf (stderr, "work_nearest failed\n");
643 return 1;
644 }
645
646 if (put_list_in_table (td, tcount, tlist)) {
647 fprintf (stderr, "put_list_in_table failed\n");
648 CC_IFFREE (tlist, int);
649 return 1;
650 }
651
652 if (!silent) {
653 printf ("Nearest added %d edges (%.2f seconds)\n",
654 td->tabletotal - current, CCutil_zeit () - szeit);
655 fflush (stdout);
656 }
657
658 CC_IFFREE (tlist, int);
659
660 return 0;
661 }
662
work_nearest(CCkdtree * kt,int ncount,int nearnum,CCdatagroup * dat,double * wcoord,int * ecount,int ** elist,int silent,CCrandstate * rstate)663 static int work_nearest (CCkdtree *kt, int ncount, int nearnum,
664 CCdatagroup *dat, double *wcoord, int *ecount, int **elist,
665 int silent, CCrandstate *rstate)
666 {
667 int norm;
668
669 CCutil_dat_getnorm (dat, &norm);
670 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
671 if (CCkdtree_k_nearest (kt, ncount, nearnum, dat, wcoord,
672 1, ecount, elist, silent, rstate)) {
673 fprintf (stderr, "CCkdtree_k_nearest failed\n");
674 return 1;
675 }
676 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
677 if (CCedgegen_x_k_nearest (ncount, nearnum, dat, wcoord, 1, ecount,
678 elist, silent)) {
679 fprintf (stderr, "CCedgegen_x_k_nearest failed\n");
680 return 1;
681 }
682 } else {
683 if (CCedgegen_junk_k_nearest (ncount, nearnum, dat, wcoord, 1, ecount,
684 elist, silent)) {
685 fprintf (stderr, "CCedgegen_junk_k_nearest failed\n");
686 return 1;
687 }
688 }
689 return 0;
690 }
691
692
call_quadnearest(int ncount,CCdatagroup * dat,double * wcoord,int nearnum,CCkdtree * kt,tabledat * td,int silent,CCrandstate * rstate)693 static int call_quadnearest (int ncount, CCdatagroup *dat, double *wcoord,
694 int nearnum, CCkdtree *kt, tabledat *td, int silent,
695 CCrandstate *rstate)
696 {
697 double szeit = CCutil_zeit ();
698 int current = td->tabletotal;
699 int tcount = 0;
700 int *tlist = (int *) NULL;
701
702 if (work_quadnearest (kt, ncount, nearnum, dat, wcoord, &tcount, &tlist,
703 silent, rstate)) {
704 fprintf (stderr, "work_quadnearest failed\n");
705 return 1;
706 }
707
708 if (put_list_in_table (td, tcount, tlist)) {
709 fprintf (stderr, "put_list_in_table failed\n");
710 CC_IFFREE (tlist, int);
711 return 1;
712 }
713
714 if (!silent) {
715 printf ("Quad Nearest added %d edges (%.2f seconds)\n",
716 td->tabletotal - current, CCutil_zeit () - szeit);
717 fflush (stdout);
718 }
719
720 CC_IFFREE (tlist, int);
721
722 return 0;
723 }
724
work_quadnearest(CCkdtree * kt,int ncount,int nearnum,CCdatagroup * dat,double * wcoord,int * ecount,int ** elist,int silent,CCrandstate * rstate)725 static int work_quadnearest (CCkdtree *kt, int ncount, int nearnum,
726 CCdatagroup *dat, double *wcoord, int *ecount, int **elist,
727 int silent, CCrandstate *rstate)
728 {
729 int norm;
730
731 CCutil_dat_getnorm (dat, &norm);
732 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
733 if (CCkdtree_quadrant_k_nearest (kt, ncount, nearnum, dat, wcoord,
734 1, ecount, elist, silent, rstate)) {
735 fprintf (stderr, "CCkdtree_quadrant_k_nearest failed\n");
736 return 1;
737 }
738 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
739 if (CCedgegen_x_quadrant_k_nearest (ncount, nearnum, dat, wcoord, 1,
740 ecount, elist, silent)) {
741 fprintf (stderr, "CCedgegen_x_quadrant_k_nearest failed\n");
742 return 1;
743 }
744 } else {
745 if (!silent) {
746 printf ("Cannot run quadrant nearest with JUNK norms\n");
747 printf ("Trying %d-nearest instead\n", 2 * nearnum);
748 fflush (stdout);
749 }
750 if (CCedgegen_junk_k_nearest (ncount, 2 * nearnum, dat, wcoord, 1,
751 ecount, elist, silent)) {
752 fprintf (stderr, "CCedgegen_junk_k_nearest failed\n");
753 return 1;
754 }
755 }
756 return 0;
757 }
758
call_random_tour(int ncount,CCdatagroup * dat,int number,tabledat * td,int silent,CCrandstate * rstate)759 static int call_random_tour (int ncount, CCdatagroup *dat, int number,
760 tabledat *td, int silent, CCrandstate *rstate)
761 {
762 double szeit = CCutil_zeit ();
763 int current = td->tabletotal;
764 int round;
765 int *tour = (int *) NULL;
766 double tzeit, val;
767 int k;
768
769 if (!silent) {
770 printf ("Generate %d Random Tours\n", number); fflush (stdout);
771 }
772
773 tour = CC_SAFE_MALLOC (ncount, int);
774 if (!tour)
775 return 1;
776
777 for (round = 0; round < number; round++) {
778 k = td->tabletotal;
779 tzeit = CCutil_zeit ();
780 randcycle (ncount, tour, dat, &val, rstate);
781 if (put_tour_in_table (td, ncount, tour)) {
782 fprintf (stderr, "put_tour_in_table failed\n");
783 CC_FREE (tour, int);
784 return 1;
785 }
786 if (!silent) {
787 printf (" Random tour %d: %.0f, added %d edges (%.2f seconds)\n",
788 round, val, td->tabletotal - k, CCutil_zeit () - tzeit);
789 fflush (stdout);
790 }
791 }
792
793 if (!silent) {
794 printf (" TOTAL: Random tours added %d edges (%.2f seconds)\n",
795 td->tabletotal - current, CCutil_zeit () - szeit);
796 fflush (stdout);
797 }
798
799 CC_IFFREE (tour, int);
800 return 0;
801 }
802
803
call_nearest_tour(int ncount,CCdatagroup * dat,int number,CCkdtree * kt,tabledat * td,int silent,CCrandstate * rstate)804 static int call_nearest_tour (int ncount, CCdatagroup *dat, int number,
805 CCkdtree *kt, tabledat *td, int silent, CCrandstate *rstate)
806 {
807 double szeit = CCutil_zeit ();
808 int current = td->tabletotal;
809 int round;
810 int *tour = (int *) NULL;
811 double tzeit, val;
812 int k;
813
814 if (!silent) {
815 printf ("Generate %d Nearest Neighbor Tours\n", number);
816 fflush (stdout);
817 }
818
819 tour = CC_SAFE_MALLOC (ncount, int);
820 if (!tour)
821 return 1;
822
823 for (round = 0; round < number; round++) {
824 k = td->tabletotal;
825 tzeit = CCutil_zeit ();
826 if (work_nearest_tour (kt, ncount, CCutil_lprand (rstate) % ncount,
827 dat, tour, &val, silent, rstate)) {
828 fprintf (stderr, "work_nearest_tour failed\n");
829 CC_FREE (tour, int);
830 return 1;
831 }
832 if (put_tour_in_table (td, ncount, tour)) {
833 fprintf (stderr, "put_tour_in_table failed\n");
834 CC_FREE (tour, int);
835 return 1;
836 }
837 if (!silent) {
838 printf (" NN tour %d: %.0f, added %d edges (%.2f seconds)\n",
839 round, val, td->tabletotal - k, CCutil_zeit () - tzeit);
840 fflush (stdout);
841 }
842 }
843
844 if (!silent) {
845 printf (" TOTAL: Nearest tours added %d edges (%.2f seconds)\n",
846 td->tabletotal - current, CCutil_zeit () - szeit);
847 fflush (stdout);
848 }
849
850 CC_IFFREE (tour, int);
851 return 0;
852 }
853
work_nearest_tour(CCkdtree * kt,int ncount,int start,CCdatagroup * dat,int * tour,double * val,int silent,CCrandstate * rstate)854 static int work_nearest_tour (CCkdtree *kt, int ncount, int start,
855 CCdatagroup *dat, int *tour, double *val, int silent,
856 CCrandstate *rstate)
857 {
858 int norm;
859
860 CCutil_dat_getnorm (dat, &norm);
861 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
862 if (CCkdtree_nearest_neighbor_tour (kt, ncount, start, dat, tour,
863 val, rstate)) {
864 fprintf (stderr, "CCkdtree_nearest_neighbor_tour failed\n");
865 return 1;
866 }
867 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
868 if (CCedgegen_x_nearest_neighbor_tour (ncount, start, dat, tour,
869 val)) {
870 fprintf (stderr, "CCedgegen_x_nearest_neighbor_tour failed\n");
871 return 1;
872 }
873 } else {
874 if (CCedgegen_junk_nearest_neighbor_tour (ncount, start, dat, tour,
875 val, silent)) {
876 fprintf (stderr, "CCedgegen_junk_nearest_neighbor_tour failed\n");
877 return 1;
878 }
879 }
880 return 0;
881 }
882
call_greedy_tour(int ncount,CCdatagroup * dat,CCkdtree * kt,tabledat * td,int silent,CCrandstate * rstate)883 static int call_greedy_tour (int ncount, CCdatagroup *dat, CCkdtree *kt,
884 tabledat *td, int silent, CCrandstate *rstate)
885 {
886 double szeit = CCutil_zeit ();
887 int current = td->tabletotal;
888 int *tour = (int *) NULL;
889 int tempcount;
890 int *templist = (int *) NULL;
891 double val;
892 int t, norm;
893 int rval = 0;
894
895 tour = CC_SAFE_MALLOC (ncount, int);
896 if (!tour) {
897 fprintf (stderr, "Out of memory in call_greedy_tour\n");
898 rval = 1; goto CLEANUP;
899 }
900
901 CCutil_dat_getnorm (dat, &norm);
902 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
903 if (CCkdtree_greedy_tour (kt, ncount, dat, tour, &val, silent,
904 rstate)) {
905 fprintf (stderr, "CCkdtree_greedy_tour failed\n");
906 rval = 1; goto CLEANUP;
907 }
908 if (put_tour_in_table (td, ncount, tour)) {
909 fprintf (stderr, "put_tour_in_table failed\n");
910 rval = 1; goto CLEANUP;
911 }
912 if (!silent) {
913 printf ("Greedy tour: %.0f, added %d edges (%.2f seconds)\n",
914 val, td->tabletotal - current, CCutil_zeit () - szeit);
915 fflush (stdout);
916 }
917 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
918 if (CCedgegen_x_quadrant_k_nearest (ncount, 2, dat, (double *) NULL,
919 1, &tempcount, &templist, silent)) {
920 fprintf (stderr, "CCedgegen_x_quadrant_k_nearest failed\n");
921 rval = 1; goto CLEANUP;
922 }
923 if (CCedgegen_x_greedy_tour (ncount, dat, tour, &val, tempcount,
924 templist, silent)) {
925 fprintf (stderr, "CCedgegen_x_greedy_tour failed\n");
926 rval = 1; goto CLEANUP;
927 }
928 if (put_tour_in_table (td, ncount, tour)) {
929 fprintf (stderr, "put_tour_in_table failed\n");
930 rval = 1; goto CLEANUP;
931 }
932 } else {
933 if (ncount < 9) {
934 t = ncount - 1;
935 } else {
936 t = 8;
937 }
938 if (CCedgegen_junk_k_nearest (ncount, t, dat, (double *) NULL,
939 1, &tempcount, &templist, silent)) {
940 fprintf (stderr, "CCedgegen_junk_k_nearest failed\n");
941 rval = 1; goto CLEANUP;
942 }
943 if (CCedgegen_junk_greedy_tour (ncount, dat, tour, &val, tempcount,
944 templist, silent)) {
945 fprintf (stderr, "CCedgegen_junk_greedy_tour failed\n");
946 rval = 1; goto CLEANUP;
947 }
948 if (put_tour_in_table (td, ncount, tour)) {
949 fprintf (stderr, "put_tour_in_table failed\n");
950 rval = 1; goto CLEANUP;
951 }
952 }
953 rval = 0;
954
955 CLEANUP:
956 CC_IFFREE (tour, int);
957 CC_IFFREE (templist, int);
958 return rval;
959 }
960
call_boruvka_tour(int ncount,CCdatagroup * dat,CCkdtree * kt,tabledat * td,int silent,CCrandstate * rstate)961 static int call_boruvka_tour (int ncount, CCdatagroup *dat, CCkdtree *kt,
962 tabledat *td, int silent, CCrandstate *rstate)
963 {
964 double szeit = CCutil_zeit ();
965 int current = td->tabletotal;
966 int *tour = (int *) NULL;
967 double val;
968 int norm;
969
970 tour = CC_SAFE_MALLOC (ncount, int);
971 if (!tour)
972 return 1;
973
974 CCutil_dat_getnorm (dat, &norm);
975 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
976 if (CCkdtree_boruvka_tour (kt, ncount, dat, tour, &val, rstate)) {
977 fprintf (stderr, "CCkdtree_boruvka_tour failed\n");
978 CC_FREE (tour, int);
979 return 1;
980 }
981 if (put_tour_in_table (td, ncount, tour)) {
982 fprintf (stderr, "put_tour_in_table failed\n");
983 CC_FREE (tour, int);
984 return 1;
985 }
986 if (!silent) {
987 printf ("Boruvka tour: %.0f, added %d edges (%.2f seconds)\n",
988 val, td->tabletotal - current, CCutil_zeit () - szeit);
989 fflush (stdout);
990 }
991 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
992 if (!silent) {
993 printf ("No X_NORM boruvka tours, using nearest neighbor\n");
994 fflush (stdout);
995 }
996 CC_FREE (tour, int);
997 return call_nearest_tour (ncount, dat, 1, kt, td, silent, rstate);
998 } else {
999 if (!silent) {
1000 printf ("No JUNK_NORM boruvka tours, using nearest neighbor\n");
1001 fflush (stdout);
1002 }
1003 CC_FREE (tour, int);
1004 return call_nearest_tour (ncount, dat, 1, kt, td, silent, rstate);
1005 }
1006
1007 CC_IFFREE (tour, int);
1008 return 0;
1009 }
1010
call_qboruvka_tour(int ncount,CCdatagroup * dat,CCkdtree * kt,tabledat * td,int silent,CCrandstate * rstate)1011 static int call_qboruvka_tour (int ncount, CCdatagroup *dat, CCkdtree *kt,
1012 tabledat *td, int silent, CCrandstate *rstate)
1013 {
1014 double szeit = CCutil_zeit ();
1015 int current = td->tabletotal;
1016 int *tour = (int *) NULL;
1017 int tempcount;
1018 int *templist = (int *) NULL;
1019 double val;
1020 int norm;
1021 int rval;
1022
1023 tour = CC_SAFE_MALLOC (ncount, int);
1024 if (!tour) {
1025 fprintf (stderr, "Out of memory in call_qboruvka_tour\n");
1026 rval = 1; goto CLEANUP;
1027 }
1028
1029 CCutil_dat_getnorm (dat, &norm);
1030 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
1031 if (CCkdtree_qboruvka_tour (kt, ncount, dat, tour, &val, rstate)) {
1032 fprintf (stderr, "CCkdtree_qboruvka_tour failed\n");
1033 rval = 1; goto CLEANUP;
1034 }
1035 if (put_tour_in_table (td, ncount, tour)) {
1036 fprintf (stderr, "put_tour_in_table failed\n");
1037 rval = 1; goto CLEANUP;
1038 }
1039 if (!silent) {
1040 printf ("Quick boruvka tour: %.0f, added %d edges (%.2f seconds)\n",
1041 val, td->tabletotal - current, CCutil_zeit () - szeit);
1042 fflush (stdout);
1043 }
1044 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
1045 if (CCedgegen_x_quadrant_k_nearest (ncount, 2, dat, (double *) NULL,
1046 1, &tempcount, &templist, silent)) {
1047 fprintf (stderr, "CCedgegen_x_quadrant_k_nearest failed\n");
1048 rval = 1; goto CLEANUP;
1049 }
1050 if (CCedgegen_x_qboruvka_tour (ncount, dat, tour, &val, tempcount,
1051 templist, silent)) {
1052 fprintf (stderr, "CCedgegen_x_qboruvka_tour failed\n");
1053 rval = 1; goto CLEANUP;
1054 }
1055 if (put_tour_in_table (td, ncount, tour)) {
1056 fprintf (stderr, "put_tour_in_table failed\n");
1057 rval = 1; goto CLEANUP;
1058 }
1059 } else {
1060 if (CCedgegen_junk_k_nearest (ncount, 8, dat, (double *) NULL,
1061 1, &tempcount, &templist, silent)) {
1062 fprintf (stderr, "CCedgegen_junk_k_nearest failed\n");
1063 rval = 1; goto CLEANUP;
1064 }
1065 if (CCedgegen_junk_qboruvka_tour (ncount, dat, tour, &val, tempcount,
1066 templist, silent)) {
1067 fprintf (stderr, "CCedgegen_junk_qboruvka_tour failed\n");
1068 rval = 1; goto CLEANUP;
1069 }
1070 if (put_tour_in_table (td, ncount, tour)) {
1071 fprintf (stderr, "put_tour_in_table failed\n");
1072 rval = 1; goto CLEANUP;
1073 }
1074 }
1075 rval = 0;
1076
1077 CLEANUP:
1078 CC_IFFREE (tour, int);
1079 CC_IFFREE (templist, int);
1080 return rval;
1081 }
1082
call_twoopt_tour(int ncount,CCdatagroup * dat,CCkdtree * kt,int number,int two_and_a_half,int use_3opt,tabledat * td,int silent,CCrandstate * rstate)1083 static int call_twoopt_tour (int ncount, CCdatagroup *dat, CCkdtree *kt,
1084 int number, int two_and_a_half, int use_3opt, tabledat *td,
1085 int silent, CCrandstate *rstate)
1086 {
1087 double szeit = CCutil_zeit ();
1088 double ival, val, tzeit;
1089 int k, round, current = td->tabletotal;
1090 int *tour1 = (int *) NULL, *tour2 = (int *) NULL;
1091 int norm;
1092
1093 if (!silent) {
1094 if (use_3opt)
1095 printf ("Generate %d 3OPT Tours from Nearest Neighbor\n", number);
1096 else if (two_and_a_half)
1097 printf ("Generate %d 2.5OPT Tours from Nearest Neighbor\n", number);
1098 else
1099 printf ("Generate %d 2OPT Tours from Nearest Neighbor\n", number);
1100 fflush (stdout);
1101 }
1102
1103 tour1 = CC_SAFE_MALLOC (ncount, int);
1104 if (!tour1)
1105 return 1;
1106 tour2 = CC_SAFE_MALLOC (ncount, int);
1107 if (!tour2) {
1108 CC_FREE (tour1, int);
1109 return 1;
1110 }
1111
1112 CCutil_dat_getnorm (dat, &norm);
1113 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
1114 for (round = 0; round < number; round++) {
1115 k = td->tabletotal;
1116 tzeit = CCutil_zeit ();
1117 if (work_nearest_tour (kt, ncount, CCutil_lprand (rstate) % ncount,
1118 dat, tour1, &val, silent, rstate)) {
1119 fprintf (stderr, "work_nearest_tour failed\n");
1120 CC_FREE (tour1, int);
1121 CC_FREE (tour2, int);
1122 return 1;
1123 }
1124 ival = val;
1125 if (use_3opt) {
1126 if (CCkdtree_3opt_tour (kt, ncount, dat, tour1, tour2, &val,
1127 1, rstate)) {
1128 fprintf (stderr, "CCkdtree_3opt_tour failed\n");
1129 CC_FREE (tour1, int);
1130 CC_FREE (tour2, int);
1131 return 1;
1132 }
1133
1134 } else {
1135 if (CCkdtree_twoopt_tour (kt, ncount, dat, tour1, tour2, &val,
1136 two_and_a_half, 1, rstate)) {
1137 fprintf (stderr, "CCkdtree_twoopt_tour failed\n");
1138 CC_FREE (tour1, int);
1139 CC_FREE (tour2, int);
1140 return 1;
1141 }
1142 }
1143 if (put_tour_in_table (td, ncount, tour2)) {
1144 fprintf (stderr, "put_tour_in_table failed\n");
1145 CC_FREE (tour1, int);
1146 CC_FREE (tour2, int);
1147 return 1;
1148 }
1149 if (!silent) {
1150 if (use_3opt)
1151 printf (" 3OPT tour %d (from %.0f): %.0f, added %d edges (%.2f sec)\n",
1152 round, ival, val, td->tabletotal - k,
1153 CCutil_zeit () - tzeit);
1154 else if (two_and_a_half)
1155 printf (" 2.5OPT tour %d (from %.0f): %.0f, added %d edges (%.2f sec)\n",
1156 round, ival, val, td->tabletotal - k,
1157 CCutil_zeit () - tzeit);
1158 else
1159 printf (" 2OPT tour %d (from %.0f): %.0f, added %d edges (%.2f sec)\n",
1160 round, ival, val, td->tabletotal - k,
1161 CCutil_zeit () - tzeit);
1162 fflush (stdout);
1163 }
1164 }
1165 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
1166 if (!silent) {
1167 if (use_3opt)
1168 printf ("No X_NORM three-opt, using nearest neighbor\n");
1169 else
1170 printf ("No X_NORM two-opt, using nearest neighbor\n");
1171 fflush (stdout);
1172 }
1173 CC_FREE (tour1, int);
1174 CC_FREE (tour2, int);
1175 return call_nearest_tour (ncount, dat, number, kt, td, silent, rstate);
1176 } else {
1177 if (!silent) {
1178 if (use_3opt)
1179 printf ("No JUNK_NORM three-opt, using nearest neighbor\n");
1180 else
1181 printf ("No JUNK_NORM two-opt, using nearest neighbor\n");
1182 fflush (stdout);
1183 }
1184 CC_FREE (tour1, int);
1185 CC_FREE (tour2, int);
1186 return call_nearest_tour (ncount, dat, number, kt, td, silent, rstate);
1187 }
1188
1189 if (!silent) {
1190 if (use_3opt)
1191 printf (" TOTAL: 3-opt tours added %d edges (%.2f seconds)\n",
1192 td->tabletotal - current, CCutil_zeit () - szeit);
1193 else if (two_and_a_half)
1194 printf (" TOTAL: 2.5-opt tours added %d edges (%.2f seconds)\n",
1195 td->tabletotal - current, CCutil_zeit () - szeit);
1196 else
1197 printf (" TOTAL: 2-opt tours added %d edges (%.2f seconds)\n",
1198 td->tabletotal - current, CCutil_zeit () - szeit);
1199 fflush (stdout);
1200 }
1201
1202 CC_IFFREE (tour1, int);
1203 CC_IFFREE (tour2, int);
1204
1205 return 0;
1206 }
1207
call_linkern(int ncount,CCdatagroup * dat,CCkdtree * kt,CCedgegengroup * plan,tabledat * td,int silent,CCrandstate * rstate)1208 static int call_linkern (int ncount, CCdatagroup *dat, CCkdtree *kt,
1209 CCedgegengroup *plan, tabledat *td, int silent, CCrandstate *rstate)
1210 {
1211 int *tour = (int *) NULL, *gtour = (int *) NULL, *itour = (int *) NULL;
1212 double val, gval, ival;
1213 double szeit = CCutil_zeit ();
1214 double tzeit;
1215 int i, k, round;
1216 int current = td->tabletotal;
1217 int ecount = 0, *elist = (int *) NULL;
1218 int rval = 0;
1219 int norm;
1220
1221 if (!silent) {
1222 printf ("Generate %d Linkern Tours (", plan->linkern.count);
1223 if (plan->linkern.greedy_start)
1224 printf ("Greedy, ");
1225 else if (plan->linkern.boruvka_start)
1226 printf ("Boruvka, ");
1227 else if (plan->linkern.qboruvka_start)
1228 printf ("Quick Boruvka, ");
1229 else if (plan->linkern.random_start)
1230 printf ("Random, ");
1231 else
1232 printf ("Nneigh, ");
1233 printf ("%d kicks, ", plan->linkern.nkicks);
1234
1235 if (plan->linkern.nearest == 0) {
1236 printf ("Quad-%d Edgeset)\n", (plan->linkern.quadnearest ?
1237 plan->linkern.quadnearest : 3));
1238 } else {
1239 if (plan->linkern.quadnearest == 0) {
1240 printf ("Near-%d Edgeset)\n", plan->linkern.nearest);
1241 } else {
1242 printf ("Quad-%d + Near-%d Edgeset)\n",
1243 plan->linkern.quadnearest, plan->linkern.nearest);
1244 }
1245 }
1246 }
1247
1248 /* Build an initial edgeset */
1249
1250 if (plan->linkern.nearest == 0 && plan->linkern.quadnearest == 0) {
1251 if (work_quadnearest (kt, ncount, 3, dat, (double *) NULL,
1252 &ecount, &elist, silent, rstate)) {
1253 fprintf (stderr, "work_quadnearest failed\n");
1254 return 1;
1255 }
1256 } else {
1257 if (plan->linkern.nearest == 0) {
1258 if (work_quadnearest (kt, ncount, plan->linkern.quadnearest,
1259 dat, (double *) NULL, &ecount, &elist, silent, rstate)) {
1260 fprintf (stderr, "work_quadnearest failed\n");
1261 return 1;
1262 }
1263 } else if (plan->linkern.quadnearest == 0) {
1264 if (work_nearest (kt, ncount, plan->linkern.nearest,
1265 dat, (double *) NULL, &ecount, &elist,
1266 silent, rstate)) {
1267 fprintf (stderr, "work_nearest failed\n");
1268 return 1;
1269 }
1270 } else {
1271 tabledat tab;
1272 int tcount, *tlist = (int *) NULL;
1273
1274 tab.table = (intptr **) NULL;
1275 tab.tabletotal = 0;
1276 tab.intptr_world = td->intptr_world;
1277
1278 tab.table = CC_SAFE_MALLOC (ncount, intptr *);
1279 if (!tab.table)
1280 return 1;
1281 for (i = 0; i < ncount; i++)
1282 tab.table[i] = (intptr *) NULL;
1283
1284 if (work_quadnearest (kt, ncount, plan->linkern.quadnearest,
1285 dat, (double *) NULL, &tcount, &tlist, silent, rstate)) {
1286 fprintf (stderr, "work_quadnearest failed\n");
1287 return 1;
1288 }
1289 if (put_list_in_table (&tab, tcount, tlist)) {
1290 fprintf (stderr, "put_list_in_table failed\n");
1291 CC_FREE (tab.table, intptr *);
1292 CC_IFFREE (tlist, int);
1293 return 1;
1294 }
1295
1296 if (work_nearest (kt, ncount, plan->linkern.nearest, dat,
1297 (double *) NULL, &tcount, &tlist, silent, rstate)) {
1298 fprintf (stderr, "work_nearest failed\n");
1299 return 1;
1300 }
1301 if (put_list_in_table (&tab, tcount, tlist)) {
1302 fprintf (stderr, "put_list_in_table failed\n");
1303 CC_FREE (tab.table, intptr *);
1304 CC_IFFREE (tlist, int);
1305 return 1;
1306 }
1307 CC_IFFREE (tlist, int);
1308
1309 if (collect_table_edges (&tab, ncount, &ecount, &elist)) {
1310 CC_FREE (tab.table, intptr *);
1311 return 1;
1312 }
1313 CC_FREE (tab.table, intptr *);
1314 }
1315 }
1316 if (!silent) {
1317 printf ("Initial Edgeset: %d\n", ecount); fflush (stdout);
1318 }
1319
1320 CCutil_dat_getnorm (dat, &norm);
1321 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
1322 if (plan->linkern.greedy_start) {
1323 gtour = CC_SAFE_MALLOC (ncount, int);
1324 if (!gtour) {
1325 rval = 1;
1326 goto CLEANUP;
1327 }
1328 tzeit = CCutil_zeit ();
1329 if (CCkdtree_greedy_tour (kt, ncount, dat, gtour, &gval, silent,
1330 rstate)) {
1331 fprintf (stderr, "CCkdtree_greedy_tour failed\n");
1332 rval = 1;
1333 goto CLEANUP;
1334 }
1335 if (!silent) {
1336 printf ("Greedy tour: %.0f (%.2f seconds)\n",
1337 gval, CCutil_zeit () - tzeit);
1338 fflush (stdout);
1339 }
1340 } else if (plan->linkern.boruvka_start) {
1341 gtour = CC_SAFE_MALLOC (ncount, int);
1342 if (!gtour) {
1343 rval = 1;
1344 goto CLEANUP;
1345 }
1346 tzeit = CCutil_zeit ();
1347 if (CCkdtree_boruvka_tour (kt, ncount, dat, gtour, &gval, rstate)) {
1348 fprintf (stderr, "CCkdtree_boruvka_tour failed\n");
1349 rval = 1;
1350 goto CLEANUP;
1351 }
1352 if (!silent) {
1353 printf ("Boruvka tour: %.0f (%.2f seconds)\n",
1354 gval, CCutil_zeit () - tzeit);
1355 fflush (stdout);
1356 }
1357 } else if (plan->linkern.qboruvka_start) {
1358 gtour = CC_SAFE_MALLOC (ncount, int);
1359 if (!gtour) {
1360 rval = 1;
1361 goto CLEANUP;
1362 }
1363 tzeit = CCutil_zeit ();
1364 if (CCkdtree_qboruvka_tour (kt, ncount, dat, gtour, &gval, rstate)) {
1365 fprintf (stderr, "CCkdtree_qboruvka_tour failed\n");
1366 rval = 1;
1367 goto CLEANUP;
1368 }
1369 if (!silent) {
1370 printf ("Quick Boruvka tour: %.0f (%.2f seconds)\n",
1371 gval, CCutil_zeit () - tzeit);
1372 fflush (stdout);
1373 }
1374 }
1375 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
1376 if (plan->linkern.greedy_start) {
1377 gtour = CC_SAFE_MALLOC (ncount, int);
1378 if (!gtour) {
1379 rval = 1;
1380 goto CLEANUP;
1381 }
1382 tzeit = CCutil_zeit ();
1383 if (CCedgegen_x_greedy_tour (ncount, dat, gtour, &gval, ecount,
1384 elist, silent)) {
1385 fprintf (stderr, "CCedgegen_x_greedy_tour failed\n");
1386 rval = 1;
1387 goto CLEANUP;
1388 }
1389 if (!silent) {
1390 printf ("Greedy tour: %.0f (%.2f seconds)\n",
1391 gval, CCutil_zeit () - tzeit);
1392 fflush (stdout);
1393 }
1394 } else if (plan->linkern.qboruvka_start) {
1395 gtour = CC_SAFE_MALLOC (ncount, int);
1396 if (!gtour) {
1397 rval = 1;
1398 goto CLEANUP;
1399 }
1400 tzeit = CCutil_zeit ();
1401 if (CCedgegen_x_qboruvka_tour (ncount, dat, gtour, &gval,
1402 ecount, elist, silent)) {
1403 fprintf (stderr, "CCedgegen_x_qboruvka_tour failed\n");
1404 rval = 1;
1405 goto CLEANUP;
1406 }
1407 if (!silent) {
1408 printf ("Quick Boruvka tour: %.0f (%.2f seconds)\n",
1409 gval, CCutil_zeit () - tzeit);
1410 fflush (stdout);
1411 }
1412 }
1413 } else {
1414 if (plan->linkern.greedy_start) {
1415 gtour = CC_SAFE_MALLOC (ncount, int);
1416 if (!gtour) {
1417 rval = 1;
1418 goto CLEANUP;
1419 }
1420 tzeit = CCutil_zeit ();
1421 if (CCedgegen_junk_greedy_tour (ncount, dat, gtour, &gval, ecount,
1422 elist, silent)) {
1423 fprintf (stderr, "CCedgegen_x_greedy_tour failed\n");
1424 rval = 1;
1425 goto CLEANUP;
1426 }
1427 if (!silent) {
1428 printf ("Greedy tour: %.0f (%.2f seconds)\n",
1429 gval, CCutil_zeit () - tzeit);
1430 fflush (stdout);
1431 }
1432 } else if (plan->linkern.qboruvka_start) {
1433 gtour = CC_SAFE_MALLOC (ncount, int);
1434 if (!gtour) {
1435 rval = 1;
1436 goto CLEANUP;
1437 }
1438 tzeit = CCutil_zeit ();
1439 if (CCedgegen_junk_qboruvka_tour (ncount, dat, gtour, &gval,
1440 ecount, elist, silent)) {
1441 fprintf (stderr, "CCedgegen_x_qboruvka_tour failed\n");
1442 rval = 1;
1443 goto CLEANUP;
1444 }
1445 if (!silent) {
1446 printf ("Quick Boruvka tour: %.0f (%.2f seconds)\n",
1447 gval, CCutil_zeit () - tzeit);
1448 fflush (stdout);
1449 }
1450 }
1451 }
1452
1453
1454 tour = CC_SAFE_MALLOC (ncount, int);
1455 if (!tour) {
1456 rval = 1;
1457 goto CLEANUP;
1458 }
1459 itour = CC_SAFE_MALLOC (ncount, int);
1460 if (!itour) {
1461 rval = 1;
1462 goto CLEANUP;
1463 }
1464
1465 for (round = 0; round < plan->linkern.count; round++) {
1466 tzeit = CCutil_zeit ();
1467 k = td->tabletotal;
1468 if (gtour != (int *) NULL) {
1469 for (i = 0; i < ncount; i++)
1470 itour[i] = gtour[i];
1471 val = gval;
1472 ival = gval;
1473 } else if (plan->linkern.random_start) {
1474 randcycle (ncount, itour, dat, &val, rstate);
1475 ival = val;
1476 } else {
1477 if (work_nearest_tour (kt, ncount, CCutil_lprand (rstate) % ncount,
1478 dat, itour, &val, silent, rstate)) {
1479 fprintf (stderr, "work_nearest_tour failed\n");
1480 rval = 1;
1481 goto CLEANUP;
1482 }
1483 ival = val;
1484 }
1485
1486 if (CClinkern_tour (ncount, dat, ecount, elist, 100000000,
1487 plan->linkern.nkicks, itour, tour, &val, 1, -1.0, -1.0,
1488 (char *) NULL, CC_LK_GEOMETRIC_KICK, rstate)) {
1489 fprintf (stderr, "CClinkern_tour failed\n");
1490 rval = 1;
1491 goto CLEANUP;
1492 }
1493
1494 if (put_tour_in_table (td, ncount, tour)) {
1495 fprintf (stderr, "put_tour_in_table failed\n");
1496 rval = 1;
1497 goto CLEANUP;
1498 }
1499 if (!silent) {
1500 printf (" LK tour %d (from %.0f): %.0f, added %d edges (%.2f sec)\n",
1501 round, ival, val, td->tabletotal - k, CCutil_zeit () - tzeit);
1502 fflush (stdout);
1503 }
1504 }
1505
1506 if (!silent) {
1507 printf (" TOTAL: Linkern tours added %d edges (%.2f seconds)\n",
1508 td->tabletotal - current, CCutil_zeit () - szeit);
1509 fflush (stdout);
1510 }
1511
1512 CLEANUP:
1513
1514 CC_IFFREE (tour, int);
1515 CC_IFFREE (itour, int);
1516 CC_IFFREE (gtour, int);
1517 CC_IFFREE (elist, int);
1518
1519 return rval;
1520 }
1521
call_f2match(int ncount,CCdatagroup * dat,CCkdtree * kt,int priceit,int basic,tabledat * td,int silent,CCrandstate * rstate)1522 static int call_f2match (int ncount, CCdatagroup *dat, CCkdtree *kt,
1523 int priceit, int basic, tabledat *td, int silent, CCrandstate *rstate)
1524 {
1525 int *mat = (int *) NULL;
1526 int ecount;
1527 int *elist = (int *) NULL;
1528 int *elen = (int *) NULL;
1529 int i;
1530 double val;
1531
1532 if (f2match_initial_edgeset (ncount, dat, kt, &ecount, &elist, &elen,
1533 td, silent, rstate)) {
1534 fprintf (stderr, "f2match_initial_edgeset failed\n");
1535 return 1;
1536 }
1537
1538 mat = CC_SAFE_MALLOC((6 * ncount) + 1, int);
1539 if (!mat) {
1540 CC_FREE (elist, int);
1541 CC_FREE (elen, int);
1542 return 1;
1543 }
1544
1545 if (priceit)
1546 i = CCfmatch_fractional_2match (ncount, ecount, elist, elen, dat, &val,
1547 mat, (int *) NULL, (int *) NULL, basic, silent, rstate);
1548 else
1549 i = CCfmatch_fractional_2match (ncount, ecount, elist, elen,
1550 (CCdatagroup *) NULL, &val, mat, (int *) NULL,
1551 (int *) NULL, basic, silent, rstate);
1552 if (i) {
1553 fprintf (stderr, "CCfmatch_fractional_2match failed\n");
1554 CC_FREE (mat, int);
1555 CC_FREE (elist, int);
1556 CC_FREE (elen, int);
1557 return 1;
1558 }
1559
1560 i = 0;
1561 while (mat[i] != -1) {
1562 if (put_in_table (td, mat[i], mat[i + 1])) {
1563 fprintf (stderr, "put_in_table failed\n");
1564 CC_FREE (mat, int);
1565 CC_FREE (elist, int);
1566 CC_FREE (elen, int);
1567 return 1;
1568 }
1569 i += 3;
1570 }
1571
1572 CC_IFFREE (mat, int);
1573 CC_IFFREE (elist, int);
1574 CC_IFFREE (elen, int);
1575
1576 return 0;
1577 }
1578
call_f2match_nearest(int ncount,CCdatagroup * dat,CCkdtree * kt,int number,int priceit,int basic,tabledat * td,int silent,CCrandstate * rstate)1579 static int call_f2match_nearest (int ncount, CCdatagroup *dat, CCkdtree *kt,
1580 int number, int priceit, int basic, tabledat *td, int silent,
1581 CCrandstate *rstate)
1582 {
1583 int ecount;
1584 int *elist = (int *) NULL;
1585 int *elen = (int *) NULL;
1586 int *dual = (int *) NULL;
1587 int dualmax, i;
1588 double *dcoord = (double *) NULL;
1589 double val;
1590 int rval = 0;
1591 int current = td->tabletotal;
1592 double szeit = CCutil_zeit ();
1593
1594 if (f2match_initial_edgeset (ncount, dat, kt, &ecount, &elist, &elen,
1595 td, silent, rstate)) {
1596 fprintf (stderr, "f2match_initial_edgeset failed\n");
1597 return 1;
1598 }
1599
1600 dual = CC_SAFE_MALLOC (ncount, int);
1601 if (!dual) {
1602 rval = 1;
1603 goto CLEANUP;
1604 }
1605
1606 if (priceit)
1607 i = CCfmatch_fractional_2match (ncount, ecount, elist, elen, dat, &val,
1608 (int *) NULL, dual, (int *) NULL, basic, silent,
1609 rstate);
1610 else
1611 i = CCfmatch_fractional_2match (ncount, ecount, elist, elen,
1612 (CCdatagroup *) NULL, &val, (int *) NULL, dual,
1613 (int *) NULL, basic, silent, rstate);
1614 if (i) {
1615 fprintf (stderr, "CCfmatch_fractional_2match failed\n");
1616 rval = 1;
1617 goto CLEANUP;
1618 }
1619 CC_FREE (elist, int);
1620 CC_FREE (elen, int);
1621 ecount = 0;
1622
1623 dualmax = dual[0];
1624 for (i = 1; i < ncount; i++) {
1625 if (dual[i] > dualmax)
1626 dualmax = dual[i];
1627 }
1628
1629 dcoord = CC_SAFE_MALLOC (ncount, double);
1630 if (!dcoord) {
1631 rval = 1;
1632 goto CLEANUP;
1633 }
1634 for (i = 0; i < ncount; i++)
1635 dcoord[i] = (dualmax - dual[i]) * 0.5;
1636 CC_FREE (dual, int);
1637
1638 if (work_nearest (kt, ncount, number, dat, dcoord, &ecount, &elist,
1639 silent, rstate)) {
1640 fprintf (stderr, "work_nearest failed\n");
1641 rval = 1;
1642 goto CLEANUP;
1643 }
1644 if (put_list_in_table (td, ecount, elist)) {
1645 fprintf (stderr, "put_list_in_table failed\n");
1646 rval = 1; goto CLEANUP;
1647 }
1648
1649 if (!silent) {
1650 printf ("Fractional 2-match Nearest-%d added %d edges (%.2f seconds)\n",
1651 number, td->tabletotal - current, CCutil_zeit () - szeit);
1652 fflush (stdout);
1653 }
1654
1655 CLEANUP:
1656
1657 CC_IFFREE (elist, int);
1658 CC_IFFREE (elen, int);
1659 CC_IFFREE (dual, int);
1660 CC_IFFREE (dcoord, double);
1661
1662 return rval;
1663 }
1664
f2match_initial_edgeset(int ncount,CCdatagroup * dat,CCkdtree * kt,int * ecount,int ** elist,int ** elen,tabledat * td,int silent,CCrandstate * rstate)1665 static int f2match_initial_edgeset (int ncount, CCdatagroup *dat, CCkdtree *kt,
1666 int *ecount, int **elist, int **elen, tabledat *td, int silent,
1667 CCrandstate *rstate)
1668 {
1669 tabledat tab;
1670 int tcount, *tlist = (int *) NULL;
1671 int *ttour = (int *) NULL;
1672 int i;
1673 double tval;
1674
1675 tab.tabletotal = 0;
1676 tab.table = (intptr **) NULL;
1677 tab.intptr_world = td->intptr_world;
1678
1679 *ecount = 0;
1680 *elist = (int *) NULL;
1681 *elen = (int *) NULL;
1682
1683 tab.table = CC_SAFE_MALLOC (ncount, intptr *);
1684 if (!tab.table)
1685 return 1;
1686 for (i = 0; i < ncount; i++)
1687 tab.table[i] = (intptr *) NULL;
1688
1689 if (work_quadnearest (kt, ncount, 3, dat, (double *) NULL, &tcount,
1690 &tlist, silent, rstate)) {
1691 fprintf (stderr, "work_quadnearest failed\n");
1692 CC_FREE (tab.table, intptr *);
1693 return 1;
1694 }
1695 if (put_list_in_table (&tab, tcount, tlist)) {
1696 fprintf (stderr, "put_list_in_table failed\n");
1697 CC_FREE (tab.table, intptr *);
1698 CC_FREE (tlist, int);
1699 return 1;
1700 }
1701 CC_IFFREE (tlist, int);
1702
1703 ttour = CC_SAFE_MALLOC (ncount, int);
1704 if (!ttour) {
1705 CC_FREE (tab.table, intptr *);
1706 return 1;
1707 }
1708 if (work_nearest_tour (kt, ncount, CCutil_lprand (rstate) % ncount, dat,
1709 ttour, &tval, silent, rstate)) {
1710 fprintf (stderr, "work_nearest_tour failed\n");
1711 CC_FREE (tab.table, intptr *);
1712 CC_FREE (ttour, int);
1713 return 1;
1714 }
1715 if (put_tour_in_table (&tab, ncount, ttour)) {
1716 fprintf (stderr, "put_tour_in_table failed\n");
1717 CC_FREE (tab.table, intptr *);
1718 CC_FREE (ttour, int);
1719 return 1;
1720 }
1721 CC_FREE (ttour, int);
1722
1723 if (collect_table_edges (&tab, ncount, ecount, elist)) {
1724 fprintf (stderr, "collect_table_edges failed\n");
1725 CC_FREE (tab.table, intptr *);
1726 return 1;
1727 }
1728 CC_FREE (tab.table, intptr *);
1729
1730 if (collect_edge_lengths (*ecount, *elist, dat, elen)) {
1731 fprintf (stderr, "collect_edge_lengths failed\n");
1732 CC_FREE (*elist, int);
1733 return 1;
1734 }
1735
1736 return 0;
1737 }
1738
call_spanning_tree(int ncount,CCdatagroup * dat,double * wcoord,CCkdtree * kt,tabledat * td,int silent,CCrandstate * rstate)1739 static int call_spanning_tree (int ncount, CCdatagroup *dat, double *wcoord,
1740 CCkdtree *kt, tabledat *td, int silent, CCrandstate *rstate)
1741 {
1742 double szeit = CCutil_zeit ();
1743 int current = td->tabletotal;
1744 int *tree = (int *) NULL;
1745 double val;
1746 int norm;
1747
1748 tree = CC_SAFE_MALLOC ((2 * ncount) - 2, int);
1749 if (!tree)
1750 return 1;
1751
1752 CCutil_dat_getnorm (dat, &norm);
1753 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
1754 if (CCkdtree_prim_spanningtree (kt, ncount, dat, wcoord, tree, &val,
1755 rstate)) {
1756 fprintf (stderr, "CCkdtree_prim_spanningtree failed\n");
1757 CC_FREE (tree, int);
1758 return 1;
1759 }
1760 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
1761 if (!silent) printf ("No X_NORM spanning tree\n");
1762 CC_FREE (tree, int);
1763 return 0;
1764 } else {
1765 if (!silent) printf ("No JUNK_NORM spanning tree\n");
1766 CC_FREE (tree, int);
1767 return 0;
1768 }
1769
1770 if (put_list_in_table (td, ncount-1, tree)) {
1771 fprintf (stderr, "put_list_in_table failed\n");
1772 CC_FREE (tree, int);
1773 return 1;
1774 }
1775
1776 if (!silent) {
1777 printf ("Spanning tree: %.0f, added %d edges (%.2f seconds)\n",
1778 val, td->tabletotal - current, CCutil_zeit () - szeit);
1779 fflush (stdout);
1780 }
1781
1782 CC_IFFREE (tree, int);
1783
1784 return 0;
1785 }
1786
call_delaunay(int ncount,CCdatagroup * dat,tabledat * td,int silent)1787 static int call_delaunay (int ncount, CCdatagroup *dat, tabledat *td,
1788 int silent)
1789 {
1790 double szeit = CCutil_zeit ();
1791 int current = td->tabletotal;
1792 int tcount = 0;
1793 int *tlist = (int *) NULL;
1794 int norm;
1795
1796 CCutil_dat_getnorm (dat, &norm);
1797 if (norm == CC_EUCLIDEAN || norm == CC_EUCLIDEAN_CEIL) {
1798 if (CCedgegen_delaunay (ncount, dat, 1, &tcount, &tlist)) {
1799 fprintf (stderr, "delaunay failed\n");
1800 return 1;
1801 }
1802 } else {
1803 printf ("No Delaunay triangulation with norm %d\n", norm);
1804 fflush (stdout);
1805 return 0;
1806 }
1807
1808 if (put_list_in_table (td, tcount, tlist)) {
1809 fprintf (stderr, "put_list_in_table failed\n");
1810 CC_IFFREE (tlist, int);
1811 return 1;
1812 }
1813
1814 if (!silent) {
1815 printf ("Delaunay Triangulation added %d edges (%.2f seconds)\n",
1816 td->tabletotal - current, CCutil_zeit () - szeit);
1817 fflush (stdout);
1818 }
1819
1820 CC_IFFREE (tlist, int);
1821
1822 return 0;
1823 }
1824
call_mlinkern(int ncount,CCdatagroup * dat,CCkdtree * kt,int iterations,tabledat * td,int silent,CCrandstate * rstate)1825 static int call_mlinkern (int ncount, CCdatagroup *dat, CCkdtree *kt,
1826 int iterations, tabledat *td, int silent, CCrandstate *rstate)
1827 {
1828 double szeit = CCutil_zeit ();
1829 int current = td->tabletotal;
1830 int tcount = 0;
1831 int *tlist = (int *) NULL;
1832
1833
1834 if (CCedgegen_mlinkern (ncount, dat, 1, &tcount, &tlist, kt, iterations,
1835 rstate)) {
1836 fprintf (stderr, "mlinkern failed\n");
1837 return 1;
1838 }
1839
1840 if (put_list_in_table (td, tcount, tlist)) {
1841 fprintf (stderr, "put_list_in_table failed\n");
1842 CC_IFFREE (tlist, int);
1843 return 1;
1844 }
1845
1846 if (!silent) {
1847 printf ("Matching LinKer added %d edges (%.2f seconds)\n",
1848 td->tabletotal - current, CCutil_zeit () - szeit);
1849 fflush (stdout);
1850 }
1851
1852 CC_IFFREE (tlist, int);
1853
1854 return 0;
1855 }
1856
call_nearest_twomatch(int ncount,CCdatagroup * dat,int number,CCkdtree * kt,tabledat * td,int silent,CCrandstate * rstate)1857 static int call_nearest_twomatch (int ncount, CCdatagroup *dat, int number,
1858 CCkdtree *kt, tabledat *td, int silent, CCrandstate *rstate)
1859 {
1860 double szeit = CCutil_zeit ();
1861 int current = td->tabletotal;
1862 int round;
1863 int *mat = (int *) NULL;
1864 double tzeit, val;
1865 int k;
1866 int norm;
1867
1868 if (!silent) {
1869 printf ("Generate %d Nearest Neighbor 2-matchings\n", number);
1870 fflush (stdout);
1871 }
1872
1873 mat = CC_SAFE_MALLOC (2 * ncount, int);
1874 if (!mat)
1875 return 1;
1876
1877 CCutil_dat_getnorm (dat, &norm);
1878 if ((norm & CC_NORM_BITS) == CC_KD_NORM_TYPE) {
1879 for (round = 0; round < number; round++) {
1880 k = td->tabletotal;
1881 tzeit = CCutil_zeit ();
1882 if (CCkdtree_nearest_neighbor_2match (kt, ncount,
1883 CCutil_lprand (rstate) % ncount, dat, mat, &val, rstate)) {
1884 fprintf (stderr, "CCkdtree_nearest_neighbor_2match failed\n");
1885 CC_FREE (mat, int);
1886 return 1;
1887 }
1888 if (put_list_in_table (td, ncount, mat)) {
1889 fprintf (stderr, "put_list_in_table failed\n");
1890 CC_FREE (mat, int);
1891 return 1;
1892 }
1893 if (!silent) {
1894 printf (" NN 2-mat %d: %.0f, added %d edges (%.2f seconds)\n",
1895 round, val, td->tabletotal - k, CCutil_zeit () - tzeit);
1896 fflush (stdout);
1897 }
1898 }
1899 } else if ((norm & CC_NORM_BITS) == CC_X_NORM_TYPE) {
1900 if (!silent) {
1901 printf ("No X_NORM NN-2match, using NN-tour instead\n");
1902 fflush (stdout);
1903 }
1904 CC_FREE (mat, int);
1905 return call_nearest_tour (ncount, dat, number, kt, td, silent, rstate);
1906 } else {
1907 if (!silent) {
1908 printf ("No JUNK_NORM NN-2match, using NN-tour instead\n");
1909 fflush (stdout);
1910 }
1911 CC_FREE (mat, int);
1912 return call_nearest_tour (ncount, dat, number, kt, td, silent, rstate);
1913 }
1914
1915 if (!silent) {
1916 printf (" TOTAL: Nearest 2-matchings added %d edges (%.2f seconds)\n",
1917 td->tabletotal - current, CCutil_zeit () - szeit);
1918 fflush (stdout);
1919 }
1920
1921 CC_IFFREE (mat, int);
1922 return 0;
1923 }
1924
put_tour_in_table(tabledat * td,int ncount,int * tour)1925 static int put_tour_in_table (tabledat *td, int ncount, int *tour)
1926 {
1927 int i;
1928
1929 for (i = 1; i < ncount; i++) {
1930 if (put_in_table (td, tour[i-1], tour[i])) {
1931 fprintf (stderr, "put_in_table failed\n");
1932 return 1;
1933 }
1934 }
1935 if (put_in_table (td, tour[ncount - 1], tour[0])) {
1936 fprintf (stderr, "put_in_table failed\n");
1937 return 1;
1938 }
1939
1940 return 0;
1941 }
1942
put_list_in_table(tabledat * td,int ecount,int * elist)1943 static int put_list_in_table (tabledat *td, int ecount, int *elist)
1944 {
1945 int i;
1946
1947 for (i = 0; i < ecount; i++) {
1948 if (put_in_table (td, elist[2 * i], elist[(2 * i) + 1])) {
1949 fprintf (stderr, "put_in_table failed\n");
1950 return 1;
1951 }
1952 }
1953 return 0;
1954 }
1955
put_in_table(tabledat * td,int i,int j)1956 static int put_in_table (tabledat *td, int i, int j)
1957 {
1958 intptr *ip;
1959
1960 if (j < i) {
1961 int temp;
1962 CC_SWAP(i, j, temp);
1963 }
1964
1965 for (ip = td->table[i]; ip; ip = ip->next) {
1966 if (ip->this == j) {
1967 return 0;
1968 }
1969 }
1970 if (intptr_listadd(&td->table[i], j, td->intptr_world)) {
1971 return 1;
1972 }
1973 td->tabletotal++;
1974 return 0;
1975 }
1976
collect_table_edges(tabledat * td,int ncount,int * ecount,int ** elist)1977 static int collect_table_edges (tabledat *td, int ncount, int *ecount,
1978 int **elist)
1979 {
1980 *ecount = 0;
1981 *elist = (int *) NULL;
1982
1983 if (td->tabletotal) {
1984 int i = 0;
1985 int j = 0;
1986 intptr *ip, *ipnext;
1987
1988 *elist = CC_SAFE_MALLOC (2 * td->tabletotal, int);
1989 if (!(*elist)) {
1990 fprintf (stderr, "Out of memory in collect_table_edges\n");
1991 return 1;
1992 }
1993 *ecount = td->tabletotal;
1994 for (i = 0; i < ncount; i++) {
1995 for (ip = td->table[i]; ip; ip = ipnext) {
1996 ipnext = ip->next;
1997 (*elist)[j++] = i;
1998 (*elist)[j++] = ip->this;
1999 intptrfree (td->intptr_world, ip);
2000 }
2001 td->table[i] = (intptr *) NULL;
2002 }
2003 }
2004 return 0;
2005 }
2006
collect_edge_lengths(int ecount,int * elist,CCdatagroup * dat,int ** elen)2007 static int collect_edge_lengths (int ecount, int *elist, CCdatagroup *dat,
2008 int **elen)
2009 {
2010 int i;
2011
2012 *elen = CC_SAFE_MALLOC (ecount, int);
2013 if ((*elen) == (int *) NULL) {
2014 fprintf (stderr, "Out of memory in collect_edge_lengths\n");
2015 return 1;
2016 }
2017 for (i=0; i<ecount; i++) {
2018 (*elen)[i] = CCutil_dat_edgelen (elist[2*i],elist[2*i+1], dat);
2019 }
2020 return 0;
2021 }
2022
randcycle(int ncount,int * cyc,CCdatagroup * dat,double * val,CCrandstate * rstate)2023 static void randcycle (int ncount, int *cyc, CCdatagroup *dat, double *val,
2024 CCrandstate *rstate)
2025 {
2026 int i, k, temp;
2027
2028 for (i = 0; i < ncount; i++)
2029 cyc[i] = i;
2030
2031 for (i = ncount; i > 1; i--) {
2032 k = CCutil_lprand (rstate) % i;
2033 CC_SWAP (cyc[i - 1], cyc[k], temp);
2034 }
2035
2036 *val = CCutil_dat_edgelen (cyc[ncount - 1], cyc[0], dat);
2037 for (i = 1; i < ncount; i++)
2038 (*val) += CCutil_dat_edgelen (cyc[i - 1], cyc[i], dat);
2039 }
2040
2041
CCedgegen_read(char * egname,CCedgegengroup * plan)2042 int CCedgegen_read (char *egname, CCedgegengroup *plan)
2043 {
2044 char buf[256];
2045 char area[256];
2046 char key[256];
2047 char field[256];
2048 char *p;
2049 FILE *in;
2050
2051 CCedgegen_init_edgegengroup (plan);
2052
2053 in = fopen (egname, "r");
2054 if (!in) {
2055 perror (egname);
2056 fprintf (stderr, "can't open %s for input\n", egname);
2057 return 1;
2058 }
2059
2060 while (fgets (buf, 254, in) != (char *) NULL) {
2061 p = buf;
2062 while (*p != '\0') {
2063 if (*p == ':')
2064 *p = ' ';
2065 p++;
2066 }
2067 p = buf;
2068 if (sscanf (p, "%s", area) != EOF) {
2069 p += strlen (area);
2070 while (*p == ' ')
2071 p++;
2072 if (!strcmp (area, "EDGEGEN")) {
2073 if (sscanf (p, "%s", key) == EOF) {
2074 fprintf (stderr, "ERROR in EDGEGEN LINE - no keyword\n");
2075 return 1;
2076 }
2077 if (!strcmp (key, "RANDOM")) {
2078 p += strlen (key);
2079 while (*p == ' ')
2080 p++;
2081 if (sscanf (p, "%s", field) != EOF) {
2082 plan->random = atoi (field);
2083 } else {
2084 printf ("RANDOM count not given, using 0\n");
2085 plan->random = 0;
2086 }
2087 } else if (!strcmp (key, "NEAREST")) {
2088 p += strlen (key);
2089 while (*p == ' ')
2090 p++;
2091 if (sscanf (p, "%s", field) != EOF) {
2092 plan->nearest = atoi (field);
2093 } else {
2094 printf ("NEAREST count not given, using 1\n");
2095 plan->nearest = 1;
2096 }
2097 } else if (!strcmp (key, "QUADNEAREST")) {
2098 p += strlen (key);
2099 while (*p == ' ')
2100 p++;
2101 if (sscanf (p, "%s", field) != EOF) {
2102 plan->quadnearest = atoi (field);
2103 } else {
2104 printf ("QUADNEAREST count not given, using 1\n");
2105 plan->quadnearest = 1;
2106 }
2107 } else if (!strcmp (key, "DELAUNAY")) {
2108 plan->delaunay = 1;
2109 } else if (!strcmp (key, "M_LINKERN")) {
2110 p += strlen (key);
2111 while (*p == ' ')
2112 p++;
2113 if (sscanf (p, "%s", field) != EOF) {
2114 plan->mlinkern = atoi (field);
2115 } else {
2116 printf ("M_LINKERN count not given, using 1\n");
2117 plan->mlinkern = 1;
2118 }
2119 } else if (!strcmp (key, "TREE")) {
2120 plan->want_tree = 1;
2121 } else if (!strcmp (key, "NN_TWOMATCH")) {
2122 p += strlen (key);
2123 while (*p == ' ')
2124 p++;
2125 if (sscanf (p, "%s", field) != EOF) {
2126 plan->nearest_twomatch_count = atoi (field);
2127 } else {
2128 printf ("NN_TWOMATCH count not given, using 1\n");
2129 plan->nearest_twomatch_count = 1;
2130 }
2131 } else if (!strcmp (key, "GREEDY_TOUR")) {
2132 plan->tour.greedy = 1;
2133 } else if (!strcmp (key, "BORUVKA_TOUR")) {
2134 plan->tour.boruvka = 1;
2135 } else if (!strcmp (key, "QBORUVKA_TOUR")) {
2136 plan->tour.qboruvka = 1;
2137 } else if (!strcmp (key, "NN_TOUR")) {
2138 p += strlen (key);
2139 while (*p == ' ')
2140 p++;
2141 if (sscanf (p, "%s", field) != EOF) {
2142 plan->tour.nearest_count = atoi (field);
2143 } else {
2144 printf ("NN_TOUR count not given, using 1\n");
2145 plan->tour.nearest_count = 1;
2146 }
2147 } else if (!strcmp (key, "RANDOM_TOUR")) {
2148 p += strlen (key);
2149 while (*p == ' ')
2150 p++;
2151 if (sscanf (p, "%s", field) != EOF) {
2152 plan->tour.random_count = atoi (field);
2153 } else {
2154 printf ("RANDOM_TOUR count not given, using 1\n");
2155 plan->tour.random_count = 1;
2156 }
2157 } else if (!strcmp (key, "TWOOPT_TOUR")) {
2158 p += strlen (key);
2159 while (*p == ' ')
2160 p++;
2161 if (sscanf (p, "%s", field) != EOF) {
2162 plan->tour.twoopt_count = atoi (field);
2163 } else {
2164 printf ("TWOOPT_TOUR count not given, using 1\n");
2165 plan->tour.twoopt_count = 1;
2166 }
2167 } else if (!strcmp (key, "TWOOPT5_TOUR")) {
2168 p += strlen (key);
2169 while (*p == ' ')
2170 p++;
2171 if (sscanf (p, "%s", field) != EOF) {
2172 plan->tour.twoopt5_count = atoi (field);
2173 } else {
2174 printf ("TWOOPT5_TOUR count not given, using 1\n");
2175 plan->tour.twoopt5_count = 1;
2176 }
2177 } else if (!strcmp (key, "THREEOPT_TOUR")) {
2178 p += strlen (key);
2179 while (*p == ' ')
2180 p++;
2181 if (sscanf (p, "%s", field) != EOF) {
2182 plan->tour.threeopt_count = atoi (field);
2183 } else {
2184 printf ("THREEOPT_TOUR count not given, using 1\n");
2185 plan->tour.threeopt_count = 1;
2186 }
2187 } else if (!strcmp (key, "FRAC_TWOMATCH")) {
2188 plan->f2match.wantit = 1;
2189 p += strlen (key);
2190 while (*p == ' ')
2191 p++;
2192 while (sscanf (p, "%s", field) != EOF) {
2193 if (!strcmp (field, "BASIC"))
2194 plan->f2match.basic = 1;
2195 else if (!strcmp (field, "PRICED"))
2196 plan->f2match.priced = 1;
2197 else
2198 printf ("Unknown option in FRAC_TWOMATCH\n");
2199 p += strlen (field);
2200 while (*p == ' ')
2201 p++;
2202 }
2203 } else if (!strcmp (key, "FRAC_TWOMATCH_NEAREST")) {
2204 p += strlen (key);
2205 while (*p == ' ')
2206 p++;
2207 while (sscanf (p, "%s", field) != EOF) {
2208 if (!strcmp (field, "BASIC"))
2209 plan->f2match_nearest.basic = 1;
2210 else if (!strcmp (field, "PRICED"))
2211 plan->f2match_nearest.priced = 1;
2212 else
2213 plan->f2match_nearest.number = atoi (field);
2214 p += strlen (field);
2215 while (*p == ' ')
2216 p++;
2217 }
2218 if (plan->f2match_nearest.number == 0) {
2219 printf ("FRAC_TWOMATCH_NEAREST count not given, using 1\n");
2220 plan->f2match_nearest.number = 1;
2221 }
2222 } else if (!strcmp (key, "LINKERN")) {
2223 p += strlen (key);
2224 while (*p == ' ')
2225 p++;
2226 if (sscanf (p, "%s", field) != EOF) {
2227 plan->linkern.count = atoi (field);
2228 p += strlen (field);
2229 while (*p == ' ')
2230 p++;
2231 } else {
2232 printf ("LINKERN count not given, using 1\n");
2233 plan->linkern.count = 1;
2234 }
2235 if (sscanf (p, "%s", field) != EOF) {
2236 plan->linkern.nkicks = atoi (field);
2237 p += strlen (field);
2238 while (*p == ' ')
2239 p++;
2240 } else {
2241 printf ("LINKERN nkicks not given, using 10\n");
2242 plan->linkern.nkicks = 10;
2243 }
2244 while (sscanf (p, "%s", field) != EOF) {
2245 if (!strcmp (field, "GREEDY_START"))
2246 plan->linkern.greedy_start = 1;
2247 else if (!strcmp (field, "BORUVKA_START"))
2248 plan->linkern.boruvka_start = 1;
2249 else if (!strcmp (field, "QBORUVKA_START"))
2250 plan->linkern.qboruvka_start = 1;
2251 else if (!strcmp (field, "RANDOM_START"))
2252 plan->linkern.random_start = 1;
2253 else if (!strcmp (field, "NN_START"))
2254 plan->linkern.nearest_start = 1;
2255 else if (!strcmp (field, "NEAREST")) {
2256 p += strlen (field);
2257 while (*p == ' ')
2258 p++;
2259 if (sscanf (p, "%s", field) != EOF) {
2260 plan->linkern.nearest = atoi (field);
2261 } else {
2262 printf ("LINKERN NEAREST COUNT not given, using 5\n");
2263 plan->linkern.nearest = 5;
2264 break;
2265 }
2266 } else if (!strcmp (field, "QUADNEAREST")) {
2267 p += strlen (field);
2268 while (*p == ' ')
2269 p++;
2270 if (sscanf (p, "%s", field) != EOF) {
2271 plan->linkern.quadnearest = atoi (field);
2272 } else {
2273 printf ("LINKERN QUADNEAREST COUNT not given, using 3\n");
2274 plan->linkern.quadnearest = 3;
2275 break;
2276 }
2277 } else {
2278 printf ("Unknown EDGEGEN LINKERN command %s\n",
2279 field);
2280 fflush (stdout);
2281 }
2282 p += strlen (field);
2283 while (*p == ' ')
2284 p++;
2285 }
2286 } else {
2287 printf ("Unknown EDGEGEN command: %s\n", key);
2288 fflush (stdout);
2289 }
2290 } else {
2291 printf ("Cannot parse command line: %s\n", area);
2292 fflush (stdout);
2293 }
2294 }
2295 }
2296 fclose (in);
2297 printf ("\n");
2298
2299 if (plan->linkern.count) {
2300 if (!plan->linkern.quadnearest && !plan->linkern.nearest)
2301 plan->linkern.quadnearest = 3;
2302 if (!plan->linkern.greedy_start && !plan->linkern.random_start &&
2303 !plan->linkern.boruvka_start && !plan->linkern.qboruvka_start)
2304 plan->linkern.nearest_start = 1;
2305 if (!plan->linkern.nkicks)
2306 plan->linkern.nkicks = 10;
2307 }
2308
2309 printf ("Edgegen Request:\n");
2310 if (plan->nearest)
2311 printf (" Nearest %d\n", plan->nearest);
2312 if (plan->quadnearest)
2313 printf (" Quad-Nearest %d\n", plan->quadnearest);
2314 if (plan->f2match_nearest.number) {
2315 printf (" Frac 2-match Nearest %d (", plan->f2match_nearest.number);
2316 if (plan->f2match_nearest.basic)
2317 printf ("Basic ");
2318 if (plan->f2match_nearest.priced)
2319 printf ("Priced)\n");
2320 else
2321 printf ("Not Priced)\n");
2322 }
2323 if (plan->delaunay)
2324 printf (" Delaunay Triangulation\n");
2325 if (plan->want_tree)
2326 printf (" Minimum Spanning Tree\n");
2327 if (plan->nearest_twomatch_count)
2328 printf (" NN 2-matchings: %d\n", plan->nearest_twomatch_count);
2329 if (plan->tour.random_count)
2330 printf (" Random Tours: %d\n", plan->tour.random_count);
2331 if (plan->tour.nearest_count)
2332 printf (" NN Tours: %d\n", plan->tour.nearest_count);
2333 if (plan->tour.greedy)
2334 printf (" Greedy Tour\n");
2335 if (plan->tour.boruvka)
2336 printf (" Boruvka Tour\n");
2337 if (plan->tour.qboruvka)
2338 printf (" Quick Boruvka Tour\n");
2339 if (plan->tour.twoopt_count)
2340 printf (" 2OPT Tours: %d\n", plan->tour.twoopt_count);
2341 if (plan->tour.twoopt5_count)
2342 printf (" 2.5OPT Tours: %d\n", plan->tour.twoopt5_count);
2343 if (plan->tour.threeopt_count)
2344 printf (" 3OPT Tours: %d\n", plan->tour.threeopt_count);
2345 if (plan->linkern.count) {
2346 printf (" LK Tours: %d (", plan->linkern.count);
2347 if (plan->linkern.greedy_start)
2348 printf ("Greedy, ");
2349 else if (plan->linkern.boruvka_start)
2350 printf ("Boruvka, ");
2351 else if (plan->linkern.qboruvka_start)
2352 printf ("Quick Boruvka, ");
2353 else if (plan->linkern.random_start)
2354 printf ("Random, ");
2355 else
2356 printf ("NN, ");
2357 if (!plan->linkern.nearest) {
2358 printf ("Quad-%d, ", plan->linkern.quadnearest);
2359 } else {
2360 if (!plan->linkern.quadnearest) {
2361 printf ("Near-%d, ", plan->linkern.nearest);
2362 } else {
2363 printf ("Quad-%d + Near-%d, ", plan->linkern.quadnearest,
2364 plan->linkern.nearest);
2365 }
2366 }
2367 printf ("%d Kicks)\n", plan->linkern.nkicks);
2368 }
2369 if (plan->f2match.wantit) {
2370 printf (" Frac 2-matching (");
2371 if (plan->f2match.basic)
2372 printf ("Basic ");
2373 if (plan->f2match.priced)
2374 printf ("Priced)\n");
2375 else
2376 printf ("Not Priced)\n");
2377 }
2378 if (plan->mlinkern) {
2379 printf (" LK matchings: %d\n", plan->mlinkern);
2380 }
2381 printf ("\n");
2382 fflush (stdout);
2383
2384 return 0;
2385 }
2386