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 DISPLAY RESTART FILES */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: January 6, 1998 */
25 /* */
26 /* SEE short decsribtion in usage (). */
27 /* */
28 /* This file currently has a copy of the restart reading code from */
29 /* TSP/bcontrol.c. In the long run, this code should be shared instead */
30 /* of copied. */
31 /* */
32 /****************************************************************************/
33
34 #include "machdefs.h"
35 #include "util.h"
36 #include "tsp.h"
37
38 typedef struct tsp_bbnode {
39 int id;
40 int status;
41 int workstatus;
42 int numtentative;
43 struct tsp_bbnode *prev;
44 struct tsp_bbnode *next;
45 struct tsp_bbnode *parent;
46 struct tsp_bbnode *child0;
47 struct tsp_bbnode *child1;
48 struct tsp_tnode *tentative_nodes;
49 struct tsp_tnode *tparent;
50 double lowerbound;
51 double cputime;
52 int number;
53 } tsp_bbnode;
54
55 typedef struct tsp_tnode {
56 tsp_bbnode *parent;
57 tsp_bbnode *child0;
58 tsp_bbnode *child1;
59 } tsp_tnode;
60
61 #define BB_NEEDS_CUTTING (1)
62 #define BB_NEEDS_TENTATIVE_CUTTING (2)
63 #define BB_NEEDS_BRANCHING (3)
64 #define BB_NEEDS_TENTATIVE_BRANCHING (4)
65 #define BB_DONE (5)
66 #define BB_IDLE (1)
67 #define BB_WORKING (2)
68 #define BB_PRUNED (3)
69
70 #define TASK_WAIT_SECONDS (60)
71
72 #define DRAWING_WIDTH (6.5*72)
73 #define DRAWING_HEIGHT (9*72)
74 #define DRAWING_BOTTOM (72)
75 #define DRAWING_LEFT (36+72)
76 #define DRAWING_TIC (7)
77 #define DRAWING_TICGAP (5)
78 #define DRAWING_TICMARGIN (5)
79 #define DRAWING_TITLEGAP (20)
80
81 CC_PTRWORLD_ROUTINES (tsp_bbnode, tsp_bbnode_alloc, tsp_bbnode_bulkalloc,
82 tsp_bbnode_free)
83 CC_PTRWORLD_LEAKS_ROUTINE (tsp_bbnode, tsp_bbnode_check_leaks, id, int)
84
85 static char *resfname = (char *) NULL;
86 static int arg_maxdepth = -1;
87 static int leafsummary = 0;
88 static int nodelist = 0;
89 static int dig_before = -1;
90 static int dig_after = 2;
91 static int use_graphics = 0;
92
93 static int
94 draw_tree (char *probname, double restart_upbound,
95 CC_UNUSED int bbcount, CC_UNUSED double branchzeit, int maxdepth,
96 tsp_bbnode *rootbbnode),
97 report_leaves (char *probname, double restart_upbound,
98 int bbcount, double branchzeit, double mod, char *format,
99 tsp_bbnode *rootbbnode, int shownodes),
100 report_tree (char *probname, double restart_upbound,
101 int bbcount, double branchzeit, int maxdepth, double mod, char *format,
102 tsp_bbnode *rootbbnode),
103 read_restart (char *restart_name, char **p_probname,
104 tsp_bbnode **p_rootbbnode, double *p_upbound, int *p_ncount,
105 int *p_bbcount, double *p_branchzeit, CCptrworld *bbnode_world),
106 read_bbtree (FILE *f, tsp_bbnode **p_b, CCptrworld *bbnode_world),
107 read_tentative_nodes (FILE *f, int count, tsp_tnode **list,
108 tsp_bbnode *parent, CCptrworld *bbnode_world),
109 prob_name (char *buf, size_t buflen, const char *f, int n),
110 parseargs (int ac, char **av);
111
112 static void
113 number_tree (tsp_bbnode *bbnode, int *cnt, int depth, int maxdepth,
114 double upbound),
115 draw_prelude (int drawcnt, double lobound, double upbound, char *probname),
116 draw_postlude (void),
117 draw_node (tsp_bbnode *bbnode, int depth),
118 draw_edge (tsp_bbnode *bfrom, tsp_bbnode *bto),
119 draw_subtree_edges (tsp_bbnode *bbnode, int depth, int maxdepth,
120 double upbound),
121 draw_subtree_nodes (tsp_bbnode *bbnode, int depth, int maxdepth,
122 double upbound),
123 print_node (tsp_bbnode *bbnode, double mod, char *format),
124 show_node (tsp_bbnode *bbnode, double mod, char *format),
125 output_tree (tsp_bbnode *bbnode, char *buf, int buflen,
126 int depth, int maxdepth, double mod, char *format),
127 collect_leaves (tsp_bbnode *bbnode, double *lower, int *leafcount,
128 double *leafvals, tsp_bbnode **leafbbs),
129 init_bbnode (tsp_bbnode *bbnode),
130 free_tree (tsp_bbnode **bbnode, CCptrworld *bbnode_world),
131 usage (char *fname);
132
133 static double
134 stepsize (double lo, double hi, int maxsteps);
135
136
main(int ac,char ** av)137 int main (int ac, char **av)
138 {
139 int rval = 0;
140 tsp_bbnode *rootbbnode = (tsp_bbnode *) NULL;
141 char *probname = (char *) NULL;
142 double restart_upbound = 0.0;
143 int restart_ncount = 0;
144 int bbcount = 0;
145 double branchzeit = 0.0;
146 char format[1024];
147 double mod = -1.0;
148 CCptrworld bbnode_world;
149
150 CCptrworld_init (&bbnode_world);
151
152 rval = parseargs (ac, av);
153 if (rval) return 1;
154
155 if (dig_before > 0) {
156 int i;
157 mod = 1.0;
158 for (i=0; i<dig_before; i++) mod = mod * 10.0;
159 sprintf (format, "%%0%d.%df", dig_before + dig_after + 1,
160 dig_after);
161 } else {
162 mod = -1.0;
163 sprintf (format, "%%.%df", dig_after);
164 }
165
166 rval = read_restart (resfname, &probname, &rootbbnode, &restart_upbound,
167 &restart_ncount, &bbcount, &branchzeit, &bbnode_world);
168 if (rval) {
169 fprintf (stderr, "read_restart failed\n");
170 goto CLEANUP;
171 }
172
173 if (use_graphics) {
174 rval = draw_tree (probname, restart_upbound, bbcount, branchzeit,
175 arg_maxdepth, rootbbnode);
176 if (rval) {
177 fprintf (stderr, "draw_tree failed\n");
178 goto CLEANUP;
179 }
180 } else if (leafsummary || nodelist) {
181 rval = report_leaves (probname, restart_upbound, bbcount, branchzeit,
182 mod, format, rootbbnode, nodelist);
183 if (rval) {
184 fprintf (stderr, "report_leaves failed\n");
185 goto CLEANUP;
186 }
187 } else {
188 rval = report_tree (probname, restart_upbound, bbcount, branchzeit,
189 arg_maxdepth, mod, format, rootbbnode);
190 if (rval) {
191 fprintf (stderr, "report_tree failed\n");
192 goto CLEANUP;
193 }
194 }
195
196 rval = 0;
197
198 CLEANUP:
199 CC_IFFREE (probname, char);
200 free_tree (&rootbbnode, &bbnode_world);
201 CCptrworld_delete (&bbnode_world);
202 return rval;
203 }
204
number_tree(tsp_bbnode * bbnode,int * cnt,int depth,int maxdepth,double upbound)205 static void number_tree (tsp_bbnode *bbnode, int *cnt, int depth, int maxdepth,
206 double upbound)
207 {
208 if (bbnode->child0 != (tsp_bbnode *) NULL &&
209 (maxdepth <= 0 || depth < maxdepth) &&
210 bbnode->child0->lowerbound <= upbound - 1.0) {
211 number_tree (bbnode->child0, cnt, depth + 1, maxdepth, upbound);
212 }
213 bbnode->number = *cnt;
214 (*cnt)++;
215 if (bbnode->child1 != (tsp_bbnode *) NULL &&
216 (maxdepth <= 0 || depth < maxdepth) &&
217 bbnode->child1->lowerbound <= upbound - 1.0) {
218 number_tree (bbnode->child1, cnt, depth + 1, maxdepth, upbound);
219 }
220 }
221
draw_tree(char * probname,double restart_upbound,CC_UNUSED int bbcount,CC_UNUSED double branchzeit,int maxdepth,tsp_bbnode * rootbbnode)222 static int draw_tree (char *probname, double restart_upbound,
223 CC_UNUSED int bbcount, CC_UNUSED double branchzeit, int maxdepth,
224 tsp_bbnode *rootbbnode)
225 {
226 int drawcnt = 0;
227
228 number_tree (rootbbnode, &drawcnt, 0, maxdepth, restart_upbound);
229 draw_prelude (drawcnt, rootbbnode->lowerbound, restart_upbound, probname);
230 draw_subtree_edges (rootbbnode, 0, maxdepth, restart_upbound);
231 draw_subtree_nodes (rootbbnode, 0, maxdepth, restart_upbound);
232 draw_postlude ();
233 return 0;
234 }
235
stepsize(double lo,double hi,int maxsteps)236 static double stepsize (double lo, double hi, int maxsteps)
237 {
238 double step = 1.0;
239
240 if (hi <= lo) hi = lo + 1.0;
241
242 while ((hi - lo) / step <= maxsteps) {
243 step = step / 10.0;
244 }
245 while ((hi - lo) / step > maxsteps) {
246 if ((hi - lo) / (2.0 * step) <= maxsteps) return 2.0*step;
247 if ((hi - lo) / (5.0 * step) <= maxsteps) return 5.0*step;
248 step = step * 10.0;
249 }
250 return step;
251 }
252
draw_prelude(int drawcnt,double lobound,double upbound,char * probname)253 static void draw_prelude (int drawcnt, double lobound, double upbound,
254 char *probname)
255 {
256 double labelstep = stepsize (lobound, upbound, 60);
257 double labello;
258 double m;
259
260 printf ("%%!PS-Adobe-2.0\n");
261 printf ("/yloc {%.2f exch sub %.2f mul %.2f div %.2f add} def\n", upbound,
262 (double) DRAWING_HEIGHT, upbound - lobound,
263 (double) DRAWING_BOTTOM);
264 printf ("/xloc {%.2f mul %d div %.2f add} def\n", (double) DRAWING_WIDTH,
265 drawcnt, (double) DRAWING_LEFT);
266 printf ("/loc {yloc exch xloc exch} def\n");
267 printf ("/n {pop loc 1 0 360 arc fill} def\n");
268 printf ("/e {newpath 0.75 0.75 0.75 setrgbcolor loc moveto loc lineto stroke} def\n");
269 printf ("/dn {0 1 0 setrgbcolor n} def\n");
270 printf ("/cn {1 0 0 setrgbcolor n} def\n");
271 printf ("/bn {1 0 1 setrgbcolor n} def\n");
272 printf ("/un {1 1 0 setrgbcolor n} def\n");
273 printf ("/tbn {un} def\n");
274 printf ("/tcn {un} def\n");
275 printf ("/dw {gsave newpath 0 0 moveto true charpath pathbbox\n");
276 printf (" exch 4 3 roll sub 3 1 roll sub grestore} def\n");
277 printf ("/lbl {gsave loc translate newpath 0 0 moveto %.2f 0 lineto stroke\n",
278 (double) -DRAWING_TIC);
279 printf (" dup dw %.2f 0 moveto 2 div exch neg exch rmoveto show grestore} def\n",
280 (double) -(DRAWING_TIC + DRAWING_TICGAP));
281 printf ("gsave\n");
282 printf ("/Helvetica findfont 24 scalefont setfont\n");
283 printf ("0 0 0 setrgbcolor\n");
284 printf ("newpath\n");
285 printf ("%.2f 2 div %.2f add %.2f %.2f add moveto\n",
286 (double) DRAWING_WIDTH, (double) DRAWING_LEFT,
287 (double) DRAWING_HEIGHT, (double) DRAWING_BOTTOM);
288 printf ("(%s Branching Tree) dup stringwidth pop 2 div neg %.2f rmoveto show\n",
289 probname, (double) DRAWING_TITLEGAP);
290 printf ("grestore\n");
291
292 printf ("gsave\n");
293 printf ("0 setlinewidth\n");
294 printf ("0 0 0 setrgbcolor\n");
295 printf ("/Helvetica findfont 10 scalefont setfont\n");
296 printf ("%.2f 0 translate\n", (double) -DRAWING_TICMARGIN);
297
298 m = fmod (lobound, labelstep);
299 if (m == 0.0) labello = lobound;
300 else labello = lobound + labelstep - m;
301
302 printf ("newpath 0 %.2f loc moveto 0 %.2f loc lineto stroke\n",
303 lobound, upbound);
304
305 for (m = labello; m <= upbound; m += labelstep) {
306 printf ("(%.0f) 0 %.2f lbl\n", m, m);
307 }
308
309 printf ("grestore\n");
310
311 printf ("gsave\n");
312 printf ("0.5 setlinewidth\n");
313 printf ("0 0 0 setrgbcolor\n");
314 printf ("\n");
315 }
316
draw_postlude(void)317 static void draw_postlude (void)
318 {
319 printf ("grestore\n");
320 printf ("showpage\n");
321 printf ("%%EOF\n");
322 }
323
draw_node(tsp_bbnode * bbnode,int depth)324 static void draw_node (tsp_bbnode *bbnode, int depth)
325 {
326 printf ("%d %.2f %d ", bbnode->number, bbnode->lowerbound, depth);
327 if (bbnode->status == BB_NEEDS_CUTTING) {
328 printf ("cn\n");
329 } else if (bbnode->status == BB_NEEDS_BRANCHING) {
330 printf ("bn\n");
331 } else if (bbnode->status == BB_NEEDS_TENTATIVE_CUTTING) {
332 printf ("tcn\n");
333 } else if (bbnode->status == BB_NEEDS_TENTATIVE_BRANCHING) {
334 printf ("tbn\n");
335 } else if (bbnode->status == BB_DONE) {
336 printf ("dn\n");
337 } else {
338 printf ("un\n");
339 }
340 }
341
draw_edge(tsp_bbnode * bfrom,tsp_bbnode * bto)342 static void draw_edge (tsp_bbnode *bfrom, tsp_bbnode *bto)
343 {
344 printf ("%d %.2f %d %.2f e\n", bfrom->number, bfrom->lowerbound,
345 bto->number, bto->lowerbound);
346 }
347
draw_subtree_edges(tsp_bbnode * bbnode,int depth,int maxdepth,double upbound)348 static void draw_subtree_edges (tsp_bbnode *bbnode, int depth, int maxdepth,
349 double upbound)
350 {
351 if (bbnode->child0 != (tsp_bbnode *) NULL &&
352 (maxdepth <= 0 || depth < maxdepth) &&
353 bbnode->child0->lowerbound <= upbound - 1.0) {
354 draw_edge (bbnode, bbnode->child0);
355 draw_subtree_edges (bbnode->child0, depth+1, maxdepth, upbound);
356 }
357 if (bbnode->child1 != (tsp_bbnode *) NULL &&
358 (maxdepth <= 0 || depth < maxdepth) &&
359 bbnode->child1->lowerbound <= upbound - 1.0) {
360 draw_edge (bbnode, bbnode->child1);
361 draw_subtree_edges (bbnode->child1, depth+1, maxdepth, upbound);
362 }
363 }
364
draw_subtree_nodes(tsp_bbnode * bbnode,int depth,int maxdepth,double upbound)365 static void draw_subtree_nodes (tsp_bbnode *bbnode, int depth, int maxdepth,
366 double upbound)
367 {
368 draw_node (bbnode, depth);
369 if (bbnode->child0 != (tsp_bbnode *) NULL &&
370 (maxdepth <= 0 || depth < maxdepth) &&
371 bbnode->child0->lowerbound <= upbound - 1.0) {
372 draw_subtree_nodes (bbnode->child0, depth+1, maxdepth, upbound);
373 }
374 if (bbnode->child1 != (tsp_bbnode *) NULL &&
375 (maxdepth <= 0 || depth < maxdepth) &&
376 bbnode->child1->lowerbound <= upbound - 1.0) {
377 draw_subtree_nodes (bbnode->child1, depth+1, maxdepth, upbound);
378 }
379 }
380
report_leaves(char * probname,double restart_upbound,int bbcount,double branchzeit,double mod,char * format,tsp_bbnode * rootbbnode,int shownodes)381 static int report_leaves (char *probname, double restart_upbound,
382 int bbcount, double branchzeit, double mod, char *format,
383 tsp_bbnode *rootbbnode, int shownodes)
384 {
385 double lower = 0.0;
386 int leafcount = 0;
387 double *leafvals = (double *) NULL;
388 tsp_bbnode **leafbbs = (tsp_bbnode **) NULL;
389 int *leafperm = (int *) NULL;
390 int i;
391 int rval = 0;
392 char buf[80];
393 size_t outcnt;
394 double v;
395
396 leafvals = CC_SAFE_MALLOC (bbcount, double);
397 if (leafvals == (double *) NULL) {
398 fprintf (stderr, "Out of memory in report_leaves\n");
399 rval = 1; goto CLEANUP;
400 }
401
402 if (shownodes) {
403 leafbbs = CC_SAFE_MALLOC (bbcount, tsp_bbnode *);
404 if (leafbbs == (tsp_bbnode **) NULL) {
405 fprintf (stderr, "Out of memory in report_leaves\n");
406 rval = 1; goto CLEANUP;
407 }
408 }
409
410 lower = restart_upbound;
411 collect_leaves (rootbbnode, &lower, &leafcount, leafvals, leafbbs);
412
413 printf ("%s: >= %.2f <= %.2f bb %d active %d time %.2f\n", probname, lower,
414 restart_upbound, bbcount, leafcount, branchzeit);
415
416 if (leafcount == 0) {
417 rval = 0;
418 goto CLEANUP;
419 }
420
421 leafperm = CC_SAFE_MALLOC (leafcount, int);
422 if (leafperm == (int *) NULL) {
423 fprintf (stderr, "Out of memory in report_leaves\n");
424 rval = 1; goto CLEANUP;
425 }
426
427 for (i=0; i<leafcount; i++) leafperm[i] = i;
428
429 CCutil_double_perm_quicksort (leafperm, leafvals, leafcount);
430
431 outcnt = 0;
432 for (i=0; i<leafcount; i++) {
433 if (shownodes) {
434 show_node (leafbbs[leafperm[i]], mod, format);
435 } else {
436 v = leafvals[leafperm[i]];
437 if (mod > 0.0) v = fmod(v, mod);
438 sprintf (buf, format, v);
439 outcnt += strlen(buf) + 1;
440 if (outcnt >= 75) {
441 printf ("\n");
442 outcnt = strlen(buf) + 1;
443 }
444 printf ("%s ",buf);
445 }
446 }
447 if (!shownodes) {
448 printf ("\n");
449 }
450 rval = 0;
451
452 CLEANUP:
453 CC_IFFREE (leafvals, double);
454 CC_IFFREE (leafbbs, tsp_bbnode *);
455 CC_IFFREE (leafperm, int);
456 return rval;
457 }
458
print_node(tsp_bbnode * bbnode,double mod,char * format)459 static void print_node (tsp_bbnode *bbnode, double mod, char *format)
460 {
461 double v = bbnode->lowerbound;
462 char buf[80];
463
464 switch (bbnode->status) {
465 case BB_NEEDS_CUTTING:
466 printf ("C"); break;
467 case BB_NEEDS_BRANCHING:
468 printf ("B"); break;
469 case BB_NEEDS_TENTATIVE_CUTTING:
470 printf ("T"); break;
471 case BB_NEEDS_TENTATIVE_BRANCHING:
472 printf ("t"); break;
473 default:
474 printf ("?%d", bbnode->status); break;
475 }
476 printf (" %5d ", bbnode->id);
477 if (mod > 0.0) v = fmod (v, mod);
478 printf (format, v);
479
480 (void) prob_name (buf, sizeof (buf), "", bbnode->id);
481 printf (" %s\n", buf);
482 }
483
show_node(tsp_bbnode * bbnode,double mod,char * format)484 static void show_node (tsp_bbnode *bbnode, double mod, char *format)
485 {
486 tsp_bbnode *b;
487 int j;
488
489 print_node (bbnode, mod, format);
490
491 if (bbnode->status == BB_NEEDS_BRANCHING &&
492 bbnode->numtentative > 0) {
493 for (j=0; j<bbnode->numtentative; j++) {
494 b = bbnode->tentative_nodes[j].child0;
495 if (b && b->status != BB_DONE) {
496 printf (" ");
497 print_node (b, mod, format);
498 }
499 b = bbnode->tentative_nodes[j].child1;
500 if (b && b->status != BB_DONE) {
501 printf (" ");
502 print_node (b, mod, format);
503 }
504 }
505 }
506 }
507
report_tree(char * probname,double restart_upbound,int bbcount,double branchzeit,int maxdepth,double mod,char * format,tsp_bbnode * rootbbnode)508 static int report_tree (char *probname, double restart_upbound,
509 int bbcount, double branchzeit, int maxdepth, double mod, char *format,
510 tsp_bbnode *rootbbnode)
511 {
512 double lower = 0.0;
513 int leafcount = 0;
514 char buf[16384];
515
516 lower = restart_upbound;
517 collect_leaves (rootbbnode, &lower, &leafcount, (double *) NULL, (tsp_bbnode **) NULL);
518
519 printf ("%s: >= %.2f <= %.2f bb %d active %d time %.2f\n", probname, lower,
520 restart_upbound, bbcount, leafcount, branchzeit);
521
522 output_tree (rootbbnode, buf, 0, 0, maxdepth, mod, format);
523
524 return 0;
525 }
526
output_tree(tsp_bbnode * bbnode,char * buf,int buflen,int depth,int maxdepth,double mod,char * format)527 static void output_tree (tsp_bbnode *bbnode, char *buf, int buflen,
528 int depth, int maxdepth, double mod, char *format)
529 {
530 char mybuf[1024];
531 double v = bbnode->lowerbound;
532 size_t outcnt;
533 size_t i;
534
535 if (mod > 0.0) v = fmod(v, mod);
536 sprintf (mybuf, "%d ", bbnode->id);
537 sprintf (mybuf + strlen(mybuf), format, v);
538 printf ("%s", mybuf);
539 if (bbnode->child0 == (tsp_bbnode *) NULL &&
540 bbnode->child1 == (tsp_bbnode *) NULL) {
541 if (bbnode->status == BB_DONE) printf ("X");
542 printf ("\n");
543 } else if (maxdepth > 0 && depth >= maxdepth) {
544 if (bbnode->status == BB_DONE) printf ("+");
545 printf ("\n");
546 } else {
547 printf (" ");
548 outcnt = strlen(mybuf) + 1;
549 if (bbnode->parent == (tsp_bbnode *) NULL ||
550 bbnode->parent->child1 == bbnode) {
551 buf[buflen] = ' ';
552 } else {
553 buf[buflen] = '|';
554 }
555 for (i=1; i<outcnt; i++) buf[buflen+i] = ' ';
556 buflen += outcnt;
557 output_tree (bbnode->child0, buf, buflen, depth+1, maxdepth,
558 mod, format);
559 buf[buflen] = '\0';
560 printf ("%s", buf);
561 output_tree (bbnode->child1, buf, buflen, depth+1, maxdepth,
562 mod, format);
563 }
564 }
565
read_restart(char * restart_name,char ** p_probname,tsp_bbnode ** p_rootbbnode,double * p_upbound,int * p_ncount,int * p_bbcount,double * p_branchzeit,CCptrworld * bbnode_world)566 static int read_restart (char *restart_name, char **p_probname,
567 tsp_bbnode **p_rootbbnode, double *p_upbound, int *p_ncount,
568 int *p_bbcount, double *p_branchzeit, CCptrworld *bbnode_world)
569 {
570 FILE *f = (FILE *) NULL;
571 char *probname = (char *) NULL;
572 int rval = 0;
573
574 f = fopen (restart_name, "r");
575 if (f == (FILE*) NULL) {
576 perror (restart_name);
577 fprintf (stderr, "Unable to open %s for input in read_restart\n",
578 restart_name);
579 rval = 1; goto CLEANUP;
580 }
581
582 probname = CC_SAFE_MALLOC (CCtsp_PROB_FILE_NAME_LEN, char);
583 if (probname == (char *) NULL) {
584 fprintf (stderr, "Out of memory in read_restart\n");
585 rval = 1; goto CLEANUP;
586 }
587
588 CCutil_readstr (f, probname, CCtsp_PROB_FILE_NAME_LEN);
589
590 rval = fscanf (f, "%d%lf%d%lf\n", p_ncount, p_upbound, p_bbcount,
591 p_branchzeit);
592 if (rval <= 0) {
593 perror (restart_name);
594 fprintf (stderr, "fscanf from %s failed\n", restart_name);
595 rval = 1; goto CLEANUP;
596 }
597 rval = read_bbtree (f, p_rootbbnode, bbnode_world);
598 if (rval) {
599 fprintf (stderr, "read_bbtree failed\n"); goto CLEANUP;
600 }
601
602 rval = fclose (f);
603 if (rval) {
604 perror (restart_name);
605 fprintf (stderr, "fclose %s failed\n", restart_name);
606 rval = 1; goto CLEANUP;
607 }
608 f = (FILE *) NULL;
609
610 *p_probname = probname;
611
612 rval = 0;
613
614 CLEANUP:
615 if (f != (FILE *) NULL) {
616 fclose (f);
617 }
618 if (rval) {
619 CC_IFFREE (probname, char);
620 free_tree (p_rootbbnode, bbnode_world);
621 }
622 return rval;
623 }
624
read_bbtree(FILE * f,tsp_bbnode ** p_b,CCptrworld * bbnode_world)625 static int read_bbtree (FILE *f, tsp_bbnode **p_b, CCptrworld *bbnode_world)
626 {
627 int rval = 0;
628 int child0, child1;
629 tsp_bbnode *b = (tsp_bbnode *) NULL;
630
631 b = tsp_bbnode_alloc (bbnode_world);
632 if (b == (tsp_bbnode *) NULL) {
633 fprintf (stderr, "tsp_bbnode_alloc failed\n");
634 rval = 1; goto CLEANUP;
635 }
636 init_bbnode (b);
637
638 rval = fscanf (f, "%d%d%d%d%d%lf%lf\n", &b->status, &b->id,
639 &child0, &child1, &b->numtentative, &b->lowerbound,
640 &b->cputime);
641 if (rval <= 0) {
642 perror ("restart_file");
643 fprintf (stderr, "fscanf failed reading restart file\n");
644 rval = 1; goto CLEANUP;
645 }
646 b->workstatus = BB_IDLE;
647
648 if (b->numtentative > 0) {
649 rval = read_tentative_nodes (f, b->numtentative, &b->tentative_nodes,
650 b, bbnode_world);
651 if (rval) {
652 fprintf (stderr, "read_tentative_nodes failed\n");
653 goto CLEANUP;
654 }
655 }
656
657 if (child0 != -1) {
658 rval = read_bbtree (f, &(b->child0), bbnode_world);
659 if (rval) goto CLEANUP;
660 if (b->child0->id != child0) {
661 fprintf (stderr, "syntax error in restart file\n");
662 rval = 1; goto CLEANUP;
663 }
664 b->child0->parent = b;
665 }
666 if (child1 != -1) {
667 rval = read_bbtree (f, &(b->child1), bbnode_world);
668 if (rval) goto CLEANUP;
669 if (b->child1->id != child1) {
670 fprintf (stderr, "syntax error in restart file\n");
671 rval = 1; goto CLEANUP;
672 }
673 b->child1->parent = b;
674 }
675
676 *p_b = b;
677 rval = 0;
678
679 CLEANUP:
680 if (rval) {
681 tsp_bbnode_free (bbnode_world, b);
682 }
683 return rval;
684 }
685
read_tentative_nodes(FILE * f,int count,tsp_tnode ** list,tsp_bbnode * parent,CCptrworld * bbnode_world)686 static int read_tentative_nodes (FILE *f, int count, tsp_tnode **list,
687 tsp_bbnode *parent, CCptrworld *bbnode_world)
688 {
689 int rval = 0;
690 int i;
691 int obtained = 0;
692 tsp_tnode *s;
693 tsp_bbnode *child0 = (tsp_bbnode *) NULL;
694 tsp_bbnode *child1 = (tsp_bbnode *) NULL;
695
696 *list = CC_SAFE_MALLOC (count, tsp_tnode);
697 if (*list == (tsp_tnode *) NULL) {
698 fprintf (stderr, "out of memory in read_tentative_nodes\n");
699 rval = 1; goto CLEANUP;
700 }
701
702 for (obtained = 0; obtained < count; obtained++) {
703 s = &((*list)[obtained]);
704 child0 = tsp_bbnode_alloc (bbnode_world);
705 if (child0 == (tsp_bbnode *) NULL) {
706 fprintf (stderr, "tsp_bbnode_alloc failed\n");
707 rval = 1; goto CLEANUP;
708 }
709 init_bbnode (child0);
710 child1 = tsp_bbnode_alloc (bbnode_world);
711 if (child1 == (tsp_bbnode *) NULL) {
712 fprintf (stderr, "tsp_bbnode_alloc failed\n");
713 tsp_bbnode_free (bbnode_world, child0);
714 rval = 1; goto CLEANUP;
715 }
716 init_bbnode (child1);
717
718 rval = fscanf (f, "%d%d%lf%lf %d%d%lf%lf\n",
719 &child0->status, &child0->id,
720 &child0->lowerbound, &child0->cputime,
721 &child1->status, &child1->id,
722 &child1->lowerbound, &child1->cputime);
723 if (rval <= 0) {
724 perror ("restart_file");
725 fprintf (stderr, "fscanf failed reading tentative line\n");
726 rval = 1; goto CLEANUP;
727 }
728 child0->tparent = s;
729 child1->tparent = s;
730 s->child0 = child0;
731 s->child1 = child1;
732 s->parent = parent;
733 }
734 rval = 0;
735
736 CLEANUP:
737
738 if (rval) {
739 for (i = 0; i < obtained; i++) {
740 tsp_bbnode_free (bbnode_world, (*list)[i].child0);
741 tsp_bbnode_free (bbnode_world, (*list)[i].child1);
742 }
743 CC_IFFREE (*list, tsp_tnode);
744 }
745 return rval;
746 }
747
collect_leaves(tsp_bbnode * bbnode,double * lower,int * leafcount,double * leafvals,tsp_bbnode ** leafbbs)748 static void collect_leaves (tsp_bbnode *bbnode, double *lower, int *leafcount,
749 double *leafvals, tsp_bbnode **leafbbs)
750 {
751 if ((bbnode->child0 == (tsp_bbnode *) NULL ||
752 bbnode->child1 == (tsp_bbnode *) NULL) &&
753 bbnode->lowerbound < *lower) {
754 *lower = bbnode->lowerbound;
755 }
756 if (bbnode->status != BB_DONE) {
757 if (leafvals != (double *) NULL) {
758 leafvals[*leafcount] = bbnode->lowerbound;
759 }
760 if (leafbbs != (tsp_bbnode **) NULL) {
761 leafbbs[*leafcount] = bbnode;
762 }
763 (*leafcount)++;
764 }
765 if (bbnode->child0) {
766 collect_leaves (bbnode->child0, lower, leafcount, leafvals, leafbbs);
767 }
768 if (bbnode->child1) {
769 collect_leaves (bbnode->child1, lower, leafcount, leafvals, leafbbs);
770 }
771 }
772
prob_name(char * buf,size_t buflen,const char * f,int n)773 static int prob_name (char *buf, size_t buflen, const char *f, int n)
774 {
775 int l = (int) strlen(f);
776 int lastslash;
777 int i;
778 int d;
779
780 if (l + 5 > (int) buflen || n < 0) {
781 fprintf (stderr, "Cannot generate filename for %s node %d\n",
782 f, n);
783 return -1;
784 }
785
786 for (i = 0, lastslash = -1; i < l; i++) {
787 if (f[i] == '/') lastslash = i;
788 buf[i] = f[i];
789 }
790 if (l > lastslash + 9) l = lastslash + 9;
791 for (i = lastslash+1; i < l; i++) {
792 if (buf[i] == '.') buf[i] = '_';
793 }
794 if (n < 1000) {
795 buf[l++] = '.';
796 d = n/100;
797 buf[l++] = '0' + ((unsigned int) d);
798 n -= d*100;
799 d = n/10;
800 buf[l++] = '0' + d;
801 n -= d*10;
802 d = n;
803 buf[l++] = '0' + ((unsigned int) d);
804 } else if (n < 1000 + (26*36*36 - 5)) {
805 buf[l++] = '.';
806 #define NAMESTRNUM(xa,xb,xc) (((xa)-'a') * 1296 + ((xb)-'a'+10) * 36 + \
807 ((xc)-'a'+10))
808 n -= 1000;
809 if (n >= NAMESTRNUM('m','a','s')) n++;
810 if (n >= NAMESTRNUM('p','u','l')) n++;
811 if (n >= NAMESTRNUM('r','e','s')) n++;
812 if (n >= NAMESTRNUM('s','a','v')) n++;
813 if (n >= NAMESTRNUM('s','o','l')) n++;
814 d = n/1296;
815 buf[l++] = 'a' + ((unsigned int) d);
816 n -= d*1296;
817 d = n/36;
818 buf[l++] = (d < 10) ? '0' + ((unsigned int) d)
819 : 'a' + ((unsigned int) (d-10));
820 n -= d*36;
821 d = n;
822 buf[l++] = (d < 10) ? '0' + ((unsigned int) d)
823 : 'a' + ((unsigned int) (d-10));
824 } else if (n < 1000 + (26*36*36 - 5) + 36*36*36*36) {
825 n -= 1000;
826 n -= 26*36*36 - 5;
827 d = n/(36*36*36);
828 buf[l++] = (d < 10) ? '0' + ((unsigned int) d)
829 : 'a' + ((unsigned int) (d-10));
830 n -= d*36*36*36;
831 d = n/(36*36);
832 buf[l++] = (d < 10) ? '0' + ((unsigned int) d)
833 : 'a' + ((unsigned int) (d-10));
834 n -= d*(36*36);
835 d = n/36;
836 buf[l++] = (d < 10) ? '0' + ((unsigned int) d)
837 : 'a' + ((unsigned int) (d-10));
838 n -= d*36;
839 d = n;
840 buf[l++] = (d < 10) ? '0' + ((unsigned int) d)
841 : 'a' + ((unsigned int) (d-10));
842 } else {
843 fprintf (stderr, "Node number %d too large\n", n);
844 return -1;
845 }
846
847 buf[l] = '\0';
848 return 0;
849 }
850
init_bbnode(tsp_bbnode * bbnode)851 static void init_bbnode (tsp_bbnode *bbnode)
852 {
853 bbnode->id = 0;
854 bbnode->lowerbound = 0.0;
855 bbnode->status = BB_NEEDS_CUTTING;
856 bbnode->workstatus = BB_IDLE;
857 bbnode->prev = (tsp_bbnode *) NULL;
858 bbnode->next = (tsp_bbnode *) NULL;
859 bbnode->parent = (tsp_bbnode *) NULL;
860 bbnode->child0 = (tsp_bbnode *) NULL;
861 bbnode->child1 = (tsp_bbnode *) NULL;
862 bbnode->cputime = 0.0;
863 }
864
free_tree(tsp_bbnode ** bbnode,CCptrworld * bbnode_world)865 static void free_tree (tsp_bbnode **bbnode, CCptrworld *bbnode_world)
866 {
867 if (!(*bbnode)) return;
868 free_tree (&((*bbnode)->child0), bbnode_world);
869 free_tree (&((*bbnode)->child1), bbnode_world);
870 tsp_bbnode_free (bbnode_world, *bbnode);
871 *bbnode = (tsp_bbnode *) NULL;
872 }
873
parseargs(int ac,char ** av)874 static int parseargs (int ac, char **av)
875 {
876 int c;
877 int boptind = 1;
878 char *boptarg = (char *) NULL;
879
880 while ((c = CCutil_bix_getopt (ac, av, "d:glnp:P:?", &boptind, &boptarg)) != EOF) {
881 switch (c) {
882 case 'd':
883 arg_maxdepth = atoi(boptarg);
884 break;
885 case 'l':
886 leafsummary = 1;
887 break;
888 case 'n':
889 nodelist = 1;
890 break;
891 case 'p':
892 dig_before = atoi (boptarg);
893 break;
894 case 'P':
895 dig_after = atoi (boptarg);
896 break;
897 case 'g':
898 use_graphics = 1;
899 break;
900 default:
901 usage (av[0]);
902 return 1;
903 }
904 }
905
906 if (boptind >= ac) {
907 usage (av[0]);
908 return 1;
909 }
910
911 resfname = av[boptind++];
912
913 if (boptind < ac) {
914 usage (av[0]);
915 return 1;
916 }
917
918 return 0;
919 }
920
usage(char * fname)921 static void usage (char *fname)
922 {
923 fprintf (stderr, "Usage: %s [-flags below] restart_fname\n", fname);
924 fprintf (stderr, " -d n dump only to depth n\n");
925 fprintf (stderr, " -l output leaf summary\n");
926 fprintf (stderr, " -n output leaf node summary\n");
927 fprintf (stderr, " -p n only show last n digits before decimal\n");
928 fprintf (stderr, " -P N only show first n digits after decimal\n");
929 fprintf (stderr, " -g create graphical (postscript) picture\n");
930 }
931
932