1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file reduce_simple.c
17 * @brief several basic reductions for Steiner tree problems
18 * @author Daniel Rehfeldt
19 *
20 * This file implements basic reduction techniques for several Steiner problems.
21 * All tests are described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.
22 *
23 * A list of all interface methods can be found in grph.h.
24 *
25 */
26
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <assert.h>
32 #include "grph.h"
33 #include "portab.h"
34 #include "scip/scip.h"
35
36 #ifndef NDEBUG
37 /** check whether problem has adjacent terminals */
38 static
adjterms(const GRAPH * g)39 SCIP_Bool adjterms(
40 const GRAPH* g /**< graph data structure */
41 )
42 {
43 for( int e = 0; e < g->edges; e++ )
44 {
45 if( g->oeat[e] != EAT_FREE )
46 {
47 const int tail = g->tail[e];
48 const int head = g->head[e];
49 if( Is_term(g->term[tail]) && Is_term(g->term[head]) && g->mark[head] && g->mark[tail] )
50 return TRUE;
51 }
52 }
53
54 return FALSE;
55 }
56 #endif
57
58 /** count numbers of chains */
59 static
nchains(const GRAPH * g)60 unsigned nchains(
61 const GRAPH* g /**< graph data structure */
62 )
63 {
64 unsigned ccount = 0;
65 for( int e = 0; e < g->edges; e++ )
66 {
67 if( g->oeat[e] != EAT_FREE )
68 {
69 const int tail = g->tail[e];
70 const int head = g->head[e];
71 if( !Is_term(g->term[tail]) && !Is_term(g->term[head]) && g->grad[head] == 2 && g->grad[tail] == 2 )
72 ccount++;
73 }
74 }
75 return ccount;
76 }
77
78 /** is there no vertex of higher prize? */
79 static
is_maxprize(SCIP * scip,const GRAPH * g,int i,SCIP_Real * maxprize)80 SCIP_Bool is_maxprize(
81 SCIP* scip, /**< SCIP data structure */
82 const GRAPH* g, /**< graph data structure */
83 int i, /**< the terminal to be checked */
84 SCIP_Real* maxprize /**< stores incumbent prize (can be updated) */
85 )
86 {
87 int t = -1;
88 SCIP_Real max;
89
90 assert(i >= 0 && Is_term(g->term[i]) && g->prize[i] > 0.0);
91
92 if( g->stp_type == STP_RPCSPG && i != g->source )
93 return FALSE;
94 else if( g->stp_type == STP_RPCSPG && i == g->source )
95 return TRUE;
96
97 max = *maxprize;
98
99 if( max > g->prize[i] )
100 return FALSE;
101
102 max = -1.0;
103
104 for( int k = 0; k < g->knots; k++ )
105 {
106 if( Is_term(g->term[k]) && g->mark[k] && g->grad[k] > 0 )
107 {
108 assert(k != g->source);
109 if( g->prize[k] > max )
110 {
111 max = g->prize[k];
112 t = k;
113 }
114 else if( t == i && g->prize[k] >= max )
115 {
116 t = k;
117 }
118 }
119 }
120
121 *maxprize = max;
122
123 SCIPdebugMessage("maxprize: %f (from %d) \n", g->prize[t], t );
124 return (t == i);
125 }
126
127 /** try to eliminate a terminal of degree one */
128 static
trydg1edgepc(SCIP * scip,GRAPH * g,SCIP_Real * offset,int * solnode,int * count,int i,int iout,SCIP_Bool * rerun,SCIP_Real * maxprize)129 SCIP_RETCODE trydg1edgepc(
130 SCIP* scip, /**< SCIP data structure */
131 GRAPH* g, /**< graph data structure */
132 SCIP_Real* offset, /**< pointer to store the offset */
133 int* solnode, /**< solution nodes or NULL */
134 int* count, /**< pointer storing number of eliminated edges */
135 int i, /**< the terminal to be checked */
136 int iout, /**< outgoing arc */
137 SCIP_Bool* rerun, /**< further eliminations possible? */
138 SCIP_Real* maxprize /**< stores incumbent prize (can be updated) */
139 )
140 {
141 int i1;
142 int degsum;
143
144 assert(scip != NULL);
145 assert(g != NULL);
146 assert(count != NULL);
147 assert(Is_term(g->term[i]));
148
149 if( is_maxprize(scip, g, i, maxprize) )
150 return SCIP_OKAY;
151
152 i1 = g->head[iout];
153
154 if( SCIPisLE(scip, g->prize[i], g->cost[iout]) && g->stp_type != STP_MWCSP )
155 {
156 /* delete terminal */
157
158 if( (i1 < i) && (Is_term(g->term[i1]) || g->grad[i1] == 2 || g->grad[i1] == 3) )
159 (*rerun) = TRUE;
160 SCIPdebugMessage("Delete (degree 1) terminal %d \n", i);
161 (*offset) += g->prize[i];
162 (*count) += graph_pc_deleteTerm(scip, g, i);
163 }
164 else
165 {
166 /* contract terminal */
167
168 (*rerun) = TRUE;
169 assert(SCIPisGT(scip, g->prize[i], 0.0 ));
170
171 if( g->stp_type == STP_MWCSP )
172 {
173 if( SCIPisLE(scip, g->prize[i], -g->prize[i1]) )
174 *offset += g->prize[i];
175 else
176 *offset -= g->prize[i1];
177 }
178 else
179 {
180 *offset += g->cost[iout];
181 }
182
183 if( g->source == i1 )
184 {
185 assert(g->stp_type == STP_RPCSPG );
186
187 if( g->pcancestors[i] != NULL )
188 {
189 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->pcancestors[i], NULL) );
190 SCIPintListNodeFree(scip, &(g->pcancestors[i]));
191 }
192 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[iout], NULL) );
193 (*count) += graph_pc_deleteTerm(scip, g, i);
194 return SCIP_OKAY;
195 }
196
197 degsum = g->grad[i] + g->grad[i1];
198
199 SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i, i1, i) );
200
201 degsum -= g->grad[i];
202
203 assert(degsum >= 1);
204
205 if( g->stp_type == STP_MWCSP )
206 {
207 int e;
208 int t = UNKNOWN;
209 int e2 = UNKNOWN;
210 if( SCIPisLE(scip, g->prize[i], 0.0) )
211 {
212 for (e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e])
213 {
214 i1 = g->head[e];
215 if( Is_pterm(g->term[i1]) && g->source != i1 )
216 t = i1;
217 else if( g->source == i1 )
218 e2 = e;
219 }
220
221 assert(t != UNKNOWN);
222 assert(e2 != UNKNOWN);
223
224 /* delete artificial terminal */
225 graph_pc_knot2nonTerm(g, t);
226 while (g->outbeg[t] != EAT_LAST)
227 {
228 e = g->outbeg[t];
229 g->cost[e] = 0.0;
230 g->cost[flipedge(e)] = 0.0;
231 graph_edge_del(scip, g, e, TRUE);
232 (*count)++;
233 }
234
235 assert(g->grad[t] == 0);
236
237 /* i is not a terminal anymore */
238 graph_pc_knot2nonTerm(g, i);
239 graph_edge_del(scip, g, e2, TRUE);
240
241 for (e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e])
242 if( g->mark[g->tail[e]] )
243 g->cost[e] = -g->prize[i];
244
245 for (e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e])
246 {
247 i1 = g->head[e];
248 if( g->mark[i1] )
249 {
250 if( !Is_term(g->term[i1]) )
251 {
252 g->cost[e] = -g->prize[i1];
253 }
254 else
255 {
256 g->cost[e] = 0.0;
257 }
258 }
259 }
260 }
261 else
262 {
263 for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
264 if( g->mark[g->tail[e]] )
265 g->cost[e] = 0.0;
266
267 for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
268 {
269 i1 = g->head[e];
270 if( g->mark[i1] )
271 {
272 if( !Is_term(g->term[i1]) )
273 {
274 assert(SCIPisLE(scip, g->prize[i1], 0.0));
275 g->cost[e] = -g->prize[i1];
276 }
277 else
278 {
279 assert(SCIPisGE(scip, g->prize[i1], 0.0));
280 g->cost[e] = 0.0;
281 }
282 }
283 else if( Is_pterm(g->term[i1]) && g->source != i1 )
284 {
285 t = i1;
286 }
287
288 }
289 assert(t != UNKNOWN);
290
291 for (e = g->inpbeg[t]; e != EAT_LAST; e = g->ieat[e])
292 if( g->tail[e] == g->source )
293 break;
294 assert(e != EAT_LAST);
295 g->cost[e] = g->prize[i];
296 }
297 }
298 (*count) += degsum;
299 }
300 return SCIP_OKAY;
301 }
302
303
304 /** traverse one side of a chain (MWCSP) */
305 static
traverseChain(SCIP * scip,GRAPH * g,int * length,int * final,int i,int i1,int i2,int e1)306 SCIP_RETCODE traverseChain(
307 SCIP* scip, /**< SCIP data structure */
308 GRAPH* g, /**< graph data structure */
309 int* length, /**< pointer to store length of chain */
310 int* final, /**< pointer to store final vertex */
311 int i, /**< start vertex */
312 int i1, /**< first vertex */
313 int i2, /**< last vertex */
314 int e1 /**< first edge */
315 )
316 {
317 IDX* ancestors = NULL;
318 IDX* revancestors = NULL;
319 SCIP_Real sum;
320 int k;
321 int e;
322
323 assert(g != NULL);
324 assert(scip != NULL);
325 assert(length != NULL);
326
327 k = i1;
328 e = e1;
329 sum = 0.0;
330
331 while( g->grad[k] == 2 && !Is_term(g->term[k]) && k != i2 )
332 {
333 assert(g->mark[k]);
334
335 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e], NULL) );
336 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[flipedge(e)], NULL) );
337
338 if( e != e1 )
339 graph_edge_del(scip, g, e, TRUE);
340
341 e = g->outbeg[k];
342 sum += g->prize[k];
343 (*length)++;
344
345 if( e == flipedge(e1) )
346 e = g->oeat[e];
347
348 assert(e != EAT_LAST);
349 assert(SCIPisLE(scip, g->prize[k], 0.0));
350
351 k = g->head[e];
352 }
353 if( k != i1 )
354 {
355 int ne;
356
357 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e], NULL) );
358 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[flipedge(e)], NULL) );
359
360 graph_edge_del(scip, g, e, TRUE);
361
362 g->prize[i] += sum;
363 ne = graph_edge_redirect(scip, g, e1, i, k, 1.0, TRUE);
364
365 if( ne != -1 )
366 {
367 e1 = ne;
368
369 SCIPintListNodeFree(scip, &(g->ancestors[e1]));
370 SCIPintListNodeFree(scip, &(g->ancestors[flipedge(e1)]));
371
372 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), ancestors, NULL) );
373 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(e1)]), revancestors, NULL) );
374
375 }
376 else
377 {
378 for( e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
379 if( g->head[e1] == k )
380 break;
381 assert(e1 != EAT_LAST);
382 }
383
384 SCIPintListNodeFree(scip, &(ancestors));
385 SCIPintListNodeFree(scip, &(revancestors));
386
387 if( SCIPisGE(scip, g->prize[k], 0.0) )
388 g->cost[e1] = 0.0;
389 else
390 g->cost[e1] = -g->prize[k];
391 assert(SCIPisLE(scip, g->prize[i], 0.0) );
392 }
393
394 *final = k;
395
396 return SCIP_OKAY;
397 }
398
399
400 /** adjust for a (rooted) PC or MW problem */
401 static
adjust0term(SCIP * scip,GRAPH * g,int i)402 void adjust0term(
403 SCIP* scip, /**< SCIP data structure */
404 GRAPH* g, /**< graph data structure */
405 int i /**< index of the terminal */
406 )
407 {
408 int t;
409 int e2;
410
411 assert(Is_term(g->term[i]));
412 assert(g->source != i);
413 assert(SCIPisZero(scip, g->prize[i]));
414
415 t = UNKNOWN;
416 e2 = UNKNOWN;
417
418 if( !Is_term(g->term[i]) || SCIPisGT(scip, g->prize[i], 0.0) )
419 return;
420
421 for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
422 {
423 const int i1 = g->head[e];
424 if( Is_pterm(g->term[i1]) && g->source != i1 )
425 t = i1;
426 else if( g->source == i1 )
427 e2 = e;
428 }
429
430 assert(t != UNKNOWN);
431 assert(g->head[g->term2edge[i]] == t);
432
433 /* i is not a terminal anymore */
434 graph_pc_knot2nonTerm(g, i);
435
436 if( g->stp_type != STP_RPCSPG )
437 {
438 assert(e2 != UNKNOWN);
439 graph_edge_del(scip, g, e2, TRUE);
440 }
441
442 /* delete artificial terminal */
443 graph_pc_knot2nonTerm(g, t);
444
445 while( g->outbeg[t] != EAT_LAST )
446 graph_edge_del(scip, g, g->outbeg[t], TRUE);
447
448 assert(g->grad[t] == 0);
449 }
450
451
452 /** contract edges of weight zero */
reduce_contractZeroEdges(SCIP * scip,GRAPH * g,SCIP_Bool savehistory)453 SCIP_RETCODE reduce_contractZeroEdges(
454 SCIP* scip, /**< SCIP data structure */
455 GRAPH* g, /**< graph data structure */
456 SCIP_Bool savehistory /**< save the history? */
457 )
458 {
459 int count;
460 int nedges;
461
462 assert(g != NULL);
463 assert(scip != NULL);
464
465 nedges = g->edges;
466
467 do
468 {
469 count = 0;
470 for( int e = 0; e < nedges; e += 2 )
471 {
472 if( g->oeat[e] != EAT_FREE && SCIPisZero(scip, g->cost[e]) && SCIPisZero(scip, g->cost[flipedge(e)]) )
473 {
474 if( savehistory )
475 {
476 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e], NULL) );
477 }
478 SCIP_CALL( graph_knot_contract(scip, g, NULL, g->tail[e], g->head[e]) );
479 count++;
480 }
481 }
482 } while( count > 0 );
483
484 return SCIP_OKAY;
485 }
486
487
488 /** basic reduction tests for the STP */
reduce_simple(SCIP * scip,GRAPH * g,SCIP_Real * fixed,int * solnode,int * nelims,int * edgestate)489 SCIP_RETCODE reduce_simple(
490 SCIP* scip, /**< SCIP data structure */
491 GRAPH* g, /**< graph data structure */
492 SCIP_Real* fixed, /**< pointer to offset value */
493 int* solnode, /**< node array to mark whether an node is part of a given solution (CONNECT),
494 or NULL */
495 int* nelims, /**< pointer to number of reductions */
496 int* edgestate /**< array to store status of (directed) edge (for propagation, can otherwise be set to NULL) */
497 )
498 {
499 int i;
500 int i1;
501 int i2;
502 int e1;
503 int e2;
504 int nnodes;
505 int rerun = TRUE;
506 int done = TRUE;
507 int count = 0;
508 SCIP_Bool checkstate = (edgestate != NULL);
509
510 assert(g != NULL);
511 assert(fixed != NULL);
512 assert(nelims != NULL);
513
514 nnodes = g->knots;
515
516 SCIPdebugMessage("Degree Test: ");
517
518 /* main loop */
519 while( rerun )
520 {
521 rerun = FALSE;
522
523 for( i = 0; i < nnodes; i++ )
524 {
525 assert(g->grad[i] >= 0);
526
527 if( g->grad[i] == 1 )
528 {
529 e1 = g->outbeg[i];
530 i1 = g->head[e1];
531
532 assert(e1 >= 0);
533 assert(e1 == Edge_anti(g->inpbeg[i]));
534 assert(g->oeat[e1] == EAT_LAST);
535 assert(g->ieat[g->inpbeg[i]] == EAT_LAST);
536
537 if( checkstate )
538 {
539 if( edgestate[e1] == EDGE_BLOCKED || Is_term(g->term[i]) )
540 continue;
541 else
542 graph_edge_del(scip, g, e1, TRUE);
543 }
544 else
545 {
546 if( Is_term(g->term[i]) )
547 {
548 *fixed += g->cost[e1];
549 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL) );
550 }
551
552 SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
553 }
554 count++;
555
556 assert(g->grad[i] == 0);
557
558 /* the last node in the graph? */
559 if( g->grad[i1] == 0 )
560 {
561 rerun = FALSE;
562 break;
563 }
564 if( (i1 < i) && (g->grad[i1] < 3) )
565 rerun = TRUE;
566
567 continue;
568 }
569 if( g->grad[i] == 2 && !checkstate )
570 {
571 e1 = g->outbeg[i];
572 e2 = g->oeat[e1];
573 i1 = g->head[e1];
574 i2 = g->head[e2];
575
576 assert(e1 >= 0);
577 assert(e2 >= 0);
578
579 do
580 {
581 done = TRUE;
582
583 if( !Is_term(g->term[i]) )
584 {
585 assert(EQ(g->cost[e2], g->cost[Edge_anti(e2)]));
586
587 g->cost[e1] += g->cost[e2];
588 g->cost[Edge_anti(e1)] += g->cost[e2];
589
590 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[flipedge(e2)], NULL) );
591 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(e1)]), g->ancestors[e2], NULL) );
592
593 SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
594 count++;
595
596 break;
597 }
598 assert(Is_term(g->term[i]));
599
600 if( Is_term(g->term[i1]) && Is_term(g->term[i2]) )
601 {
602
603 if( SCIPisLT(scip, g->cost[e1], g->cost[e2]) )
604 {
605 *fixed += g->cost[e1];
606 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL) );
607 SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
608 }
609 else
610 {
611 *fixed += g->cost[e2];
612 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e2], NULL) );
613 SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
614 }
615 count++;
616
617 break;
618 }
619 if( Is_term(g->term[i1]) && !Is_term(g->term[i2]) && SCIPisLE(scip, g->cost[e1], g->cost[e2]) )
620 {
621 *fixed += g->cost[e1];
622 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL) );
623 SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
624 count++;
625 break;
626 }
627 if( Is_term(g->term[i2]) && !Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e2], g->cost[e1]) )
628 {
629 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e2], NULL) );
630 *fixed += g->cost[e2];
631 SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
632 count++;
633 break;
634 }
635 done = FALSE;
636 }
637 while( FALSE );
638
639 if (done
640 && (((i1 < i) && (g->grad[i1] < 3))
641 || ((i2 < i) && (g->grad[i2] < 3))))
642 rerun = TRUE;
643 }
644 if( Is_term(g->term[i]) && g->grad[i] > 2 && !checkstate )
645 {
646 SCIP_Real mincost = FARAWAY;
647 int ett = UNKNOWN;
648 for( e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
649 {
650 i1 = g->head[e1];
651
652 if( SCIPisLT(scip, g->cost[e1], mincost) )
653 {
654 mincost = g->cost[e1];
655 if( Is_term(g->term[i1]) )
656 ett = e1;
657 }
658 else if( Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e1], mincost) )
659 {
660 ett = e1;
661 }
662 }
663 if( ett != UNKNOWN && SCIPisLE(scip, g->cost[ett], mincost) )
664 {
665 *fixed += g->cost[ett];
666 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[ett], NULL) );
667 SCIP_CALL( graph_knot_contractLowdeg2High(scip, g, solnode, i, g->head[ett]) );
668
669 rerun = TRUE;
670 }
671 }
672 }
673 }
674 SCIPdebugMessage(" %d Knots deleted\n", count);
675 assert(graph_valid(g));
676
677 *nelims += count;
678 return SCIP_OKAY;
679 }
680
681
682
683 /** basic reduction tests for the SAP */
reduce_simple_sap(SCIP * scip,GRAPH * g,SCIP_Real * fixed,int * count)684 SCIP_RETCODE reduce_simple_sap(
685 SCIP* scip, /**< SCIP data structure */
686 GRAPH* g, /**< graph data structure */
687 SCIP_Real* fixed, /**< pointer to offfset value */
688 int* count /**< pointer to number of reductions */
689 )
690 {
691 SCIP_QUEUE* queue;
692 int i;
693 int e;
694 int i1;
695 int i2;
696 int e1;
697 int e2;
698 int nnodes;
699 int* pnode;
700 char rerun;
701
702 assert(g != NULL);
703 assert(fixed != NULL);
704 assert(count != NULL);
705
706 rerun = TRUE;
707 nnodes = g->knots;
708
709 *count = 0;
710 SCIPdebugMessage("Degree Test: ");
711
712 /* main loop */
713 while( rerun )
714 {
715 rerun = FALSE;
716
717 for( i = 0; i < nnodes; i++ )
718 {
719 assert(g->grad[i] >= 0);
720
721 if( g->grad[i] == 1 )
722 {
723 e1 = g->inpbeg[i];
724 i1 = g->tail[e1];
725
726 assert(e1 >= 0);
727 assert(e1 == Edge_anti(g->outbeg[i]));
728 assert(g->ieat[e1] == EAT_LAST);
729 assert(g->oeat[g->outbeg[i]] == EAT_LAST);
730
731 if( Is_term(g->term[i]) )
732 {
733 if( i == g->source )
734 {
735 e2 = flipedge(e1);
736 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e2], NULL) );
737 *fixed += g->cost[e2];
738 SCIP_CALL( graph_knot_contract(scip, g, NULL, i1, i) );
739 }
740 else
741 {
742 SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL));
743 *fixed += g->cost[e1];
744 SCIP_CALL(graph_knot_contract(scip, g, NULL, i1, i));
745 }
746 }
747 else
748 {
749 graph_edge_del(scip, g, e1, TRUE);
750 }
751
752 assert(g->grad[i] == 0);
753
754 if ((i1 < i) && (g->grad[i1] < 3))
755 rerun = TRUE;
756
757 (*count)++;
758
759 continue;
760 }
761
762 if( g->grad[i] == 2 )
763 {
764 e1 = g->outbeg[i];
765 e2 = g->oeat[e1];
766 i1 = g->head[e1];
767 i2 = g->head[e2];
768
769 assert(e1 >= 0);
770 assert(e2 >= 0);
771
772 if( !Is_term(g->term[i]) )
773 {
774 if( (!Is_term(g->term[i2]) && !Is_term(g->term[i1])) )
775 {
776 g->cost[e1] += g->cost[Edge_anti(e2)];
777 g->cost[Edge_anti(e1)] += g->cost[e2];
778
779 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[Edge_anti(e2)], NULL) );
780 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(e1)]), g->ancestors[e2], NULL) );
781
782 if( SCIPisGT(scip, g->cost[e1], FARAWAY) )
783 g->cost[e1] = FARAWAY;
784 if( SCIPisGT(scip, g->cost[Edge_anti(e1)], FARAWAY) )
785 g->cost[Edge_anti(e1)] = FARAWAY;
786
787 SCIP_CALL( graph_knot_contract(scip, g, NULL, i2, i) );
788
789 (*count)++;
790 if( ((i1 < i) && (g->grad[i1] < 3))
791 || ((i2 < i) && (g->grad[i2] < 3)) )
792 rerun = TRUE;
793 }
794 }
795 /* CONSTCOND */
796 /*lint -save -e717 */
797 /*lint -restore */
798 }
799 }
800 }
801
802 /* delete all arcs in \delta^-(root) */
803 for( e = g->inpbeg[g->source]; e != EAT_LAST; e = g->ieat[e] )
804 g->cost[e] = FARAWAY;
805
806 /* delete all nodes not reachable from the root by forward arcs */
807
808 /* BFS */
809 SCIP_CALL(SCIPqueueCreate(&queue, nnodes, 1.1));
810
811 for (i = 0; i < nnodes; i++)
812 g->mark[i] = FALSE;
813
814 g->mark[g->source] = TRUE;
815 SCIP_CALL(SCIPqueueInsert(queue, &(g->source)));
816
817 while (!SCIPqueueIsEmpty(queue))
818 {
819 pnode = (SCIPqueueRemove(queue));
820 for (e = g->outbeg[*pnode]; e != EAT_LAST; e = g->oeat[e])
821 {
822 if( !g->mark[g->head[e]] && SCIPisLT(scip, g->cost[e], FARAWAY) )
823 {
824 g->mark[g->head[e]] = TRUE;
825 SCIP_CALL(SCIPqueueInsert(queue, &(g->head[e])));
826 }
827 }
828 }
829
830 for (i = 0; i < nnodes; i++)
831 if( !g->mark[i] )
832 while (g->inpbeg[i] != EAT_LAST)
833 graph_edge_del(scip, g, g->inpbeg[i], TRUE);
834
835 /* delete all nodes that cannot reach a terminal other than the root by forward arcs (not using the root) */
836
837 /* BFS */
838
839 assert(SCIPqueueIsEmpty(queue));
840
841 for( i = 0; i < nnodes; i++ )
842 {
843 if( Is_term(g->term[i]) && i != g->source )
844 {
845 g->mark[i] = TRUE;
846 SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[g->outbeg[i]])) );
847 }
848 else
849 {
850 g->mark[i] = FALSE;
851 }
852 }
853
854 g->mark[g->source] = TRUE;
855
856 while( !SCIPqueueIsEmpty(queue) )
857 {
858 pnode = (SCIPqueueRemove(queue));
859 for( e = g->inpbeg[*pnode]; e != EAT_LAST; e = g->ieat[e] )
860 {
861 if( !g->mark[g->tail[e]] && SCIPisLT(scip, g->cost[e], FARAWAY) )
862 {
863 g->mark[g->tail[e]] = TRUE;
864 SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[e])) );
865 }
866 }
867 }
868
869 SCIPqueueFree(&queue);
870
871 for( i = 0; i < nnodes; i++ )
872 if( !g->mark[i] )
873 while( g->inpbeg[i] != EAT_LAST )
874 graph_edge_del(scip, g, g->inpbeg[i], TRUE);
875
876 SCIPdebugMessage("dirdeg %d Knots deleted\n", *count);
877 assert(graph_valid(g));
878
879 return SCIP_OKAY;
880 }
881
882
883 /** root proximity terminal test (SAP) */
reduce_rpt(SCIP * scip,GRAPH * g,SCIP_Real * fixed,int * count)884 SCIP_RETCODE reduce_rpt(
885 SCIP* scip, /**< SCIP data structure */
886 GRAPH* g, /**< graph data structure */
887 SCIP_Real* fixed, /**< pointer to offset value */
888 int* count /**< pointer to number of reductions */
889 )
890 {
891 SCIP_Real pathcost;
892 SCIP_Real* dijkdist;
893 int i;
894 int e;
895 int i1;
896 int e1;
897 int old;
898 int nnodes;
899 int* dijkedge;
900
901 assert(scip != NULL);
902 assert(g != NULL);
903 assert(fixed != NULL);
904 assert(count != NULL);
905
906 nnodes = g->knots;
907 *count = 0;
908
909 SCIP_CALL( SCIPallocBufferArray(scip, &dijkdist, nnodes) );
910 SCIP_CALL( SCIPallocBufferArray(scip, &dijkedge, nnodes) );
911
912 graph_path_execX(scip, g, g->source, g->cost, dijkdist, dijkedge);
913
914 for( i = 0; i < nnodes; i++ )
915 {
916 if( Is_term(g->term[i]) && i != g->source && g->grad[i] > 0 )
917 {
918 e1 = dijkedge[i];
919 pathcost = dijkdist[i];
920
921 for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
922 {
923 if( e == e1 )
924 continue;
925
926 if( SCIPisGT(scip, pathcost, g->cost[e]) )
927 break;
928 }
929 if( e == EAT_LAST )
930 {
931 i1 = g->tail[e1];
932 old = g->grad[i] + g->grad[i1] - 1;
933
934 SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL));
935 *fixed += g->cost[e1];
936 SCIP_CALL(graph_knot_contract(scip, g, NULL, i1, i));
937
938 assert(old - g->grad[i1] > 0);
939 *count += old - g->grad[i1];
940 SCIPdebugMessage("contract %d\n", old - g->grad[i] - g->grad[i1]);
941 }
942
943 }
944 }
945
946 SCIPfreeBufferArray(scip, &dijkedge);
947 SCIPfreeBufferArray(scip, &dijkdist);
948
949 return SCIP_OKAY;
950 }
951
952 /** basic reduction tests for the MWCS problem */
reduce_simple_mw(SCIP * scip,GRAPH * g,int * solnode,SCIP_Real * fixed,int * count)953 SCIP_RETCODE reduce_simple_mw(
954 SCIP* scip, /**< SCIP data structure */
955 GRAPH* g, /**< graph data structure */
956 int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
957 SCIP_Real* fixed, /**< pointer to offset value */
958 int* count /**< pointer to number of reductions */
959 )
960 {
961 SCIP_Real maxprize = -1.0;
962 const int nnodes = g->knots;
963 int localcount = 0;
964
965 SCIP_Bool rerun;
966 SCIP_Bool contracted;
967
968 assert(g != NULL);
969 assert(fixed != NULL);
970 assert(count != NULL);
971 assert(g->stp_type == STP_MWCSP);
972
973 SCIPdebugMessage("MW degree test: \n");
974
975 contracted = TRUE;
976 while( contracted )
977 {
978 contracted = FALSE;
979
980 /* contract adjacent positive vertices */
981 for( int i = 0; i < nnodes; i++ )
982 {
983 int i1 = -1;
984 int grad;
985 SCIP_Bool hit;
986
987 if( !Is_term(g->term[i]) || !(g->mark[i]) )
988 continue;
989
990 grad = g->grad[i];
991 hit = FALSE;
992
993 for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
994 {
995 const int head = g->head[e];
996
997 if( Is_term(g->term[head]) && head != g->source )
998 {
999 assert(g->mark[head]);
1000
1001 if( (g->grad[head] <= grad) )
1002 {
1003 grad = g->grad[head];
1004 i1 = head;
1005 }
1006 else if( head < i )
1007 {
1008 hit = TRUE;
1009 }
1010 }
1011 }
1012
1013 while( i1 >= 0 )
1014 {
1015 int i2 = -1;
1016
1017 assert(g->mark[i1]);
1018 assert(g->grad[i1] > 0);
1019 assert(Is_term(g->term[i1]));
1020
1021 grad = g->grad[i];
1022 hit = FALSE;
1023 for( int e = g->outbeg[i1]; e != EAT_LAST; e = g->oeat[e] )
1024 {
1025 const int head = g->head[e];
1026 if( Is_term(g->term[head]) && head != i && head != g->source )
1027 {
1028 assert(g->mark[head]);
1029
1030 if( (g->grad[head] <= grad) )
1031 {
1032 i2 = head;
1033 grad = g->grad[head];
1034 }
1035 else if( head < i )
1036 {
1037 hit = TRUE;
1038 }
1039 }
1040 }
1041
1042 SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i, i1, i));
1043
1044 localcount++;
1045
1046 i1 = i2;
1047 }
1048 if( hit )
1049 contracted = TRUE;
1050 }
1051 }
1052
1053 /* contract adjacent 0 vertices */
1054 for( int i = 0; i < nnodes; i++ )
1055 {
1056 if( !(g->mark[i]) || !SCIPisZero(scip, g->prize[i]) )
1057 continue;
1058
1059 for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1060 {
1061 const int i2 = g->head[e];
1062
1063 if( g->mark[i2] && SCIPisGE(scip, g->prize[i2], 0.0) )
1064 {
1065 if( Is_term(g->term[i2]) )
1066 {
1067 SCIP_CALL(graph_pc_contractEdge(scip, g, solnode, i2, i, i2));
1068 }
1069 else
1070 {
1071 SCIP_CALL( graph_pc_contractEdgeAncestors(scip, g, i2, i, flipedge_Uint(e)) );
1072 SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
1073 }
1074
1075 localcount++;
1076 break;
1077 }
1078 }
1079 }
1080
1081 SCIPdebugMessage("chains before: %d \n", nchains(g));
1082
1083 rerun = TRUE;
1084
1085 /* main loop */
1086 while( rerun )
1087 {
1088 rerun = FALSE;
1089
1090 /* main loop for remaining tests */
1091 for( int i = 0; i < nnodes; i++ )
1092 {
1093 assert(g->grad[i] >= 0);
1094 if( !g->mark[i] || g->grad[i] == 0 )
1095 continue;
1096
1097 assert(!Is_pterm(g->term[i]));
1098
1099 /* non-positive vertex? */
1100 if( !Is_term(g->term[i]) )
1101 {
1102 if( g->grad[i] == 1 )
1103 {
1104 const int e1 = g->inpbeg[i];
1105 const int i1 = g->tail[e1];
1106
1107 assert(e1 >= 0);
1108 assert(e1 == Edge_anti(g->outbeg[i]));
1109 assert(g->ieat[e1] == EAT_LAST);
1110 assert(g->oeat[g->outbeg[i]] == EAT_LAST);
1111 assert(SCIPisLE(scip, g->prize[i], 0.0));
1112
1113 graph_edge_del(scip, g, e1, TRUE);
1114 SCIPdebugMessage("delete negative vertex of degree 1 (%d)\n ", i);
1115 assert(g->grad[i] == 0);
1116
1117 if( (i1 < i) && (g->grad[i1] < 3 || (g->grad[i1] == 3 && Is_term(g->term[i1]))) )
1118 rerun = TRUE;
1119
1120 localcount++;
1121 continue;
1122 }
1123
1124 /* contract non-positive chains */
1125 if( g->grad[i] == 2 )
1126 {
1127 int f1 = -1;
1128 int f2 = -1;
1129 int length = 0;
1130
1131 const int e1 = g->outbeg[i];
1132 const int e2 = g->oeat[e1];
1133 const int i1 = g->head[e1];
1134 const int i2 = g->head[e2];
1135
1136 assert(e1 >= 0);
1137 assert(e2 >= 0);
1138 assert(i1 != i2);
1139 assert(g->mark[i1]);
1140 assert(g->mark[i2]);
1141
1142 SCIP_CALL( traverseChain(scip, g, &length, &f1, i, i1, i2, e1) );
1143 SCIP_CALL( traverseChain(scip, g, &length, &f2, i, i2, i1, e2) );
1144
1145 if( f1 == f2 )
1146 {
1147 while( g->outbeg[i] != EAT_LAST )
1148 graph_edge_del(scip, g, g->outbeg[i], TRUE);
1149 }
1150 else if( length > 0 )
1151 {
1152 assert(g->grad[i] <= 2);
1153
1154 for( int e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
1155 g->cost[e] = -g->prize[i];
1156
1157 localcount += length;
1158 }
1159 }
1160 continue;
1161 }
1162
1163 /* node i is of positive weight (terminal): */
1164
1165 /* terminal of 0-prize? */
1166 if( SCIPisLE(scip, g->prize[i], 0.0) )
1167 {
1168 adjust0term(scip, g, i);
1169 localcount += 2;
1170 continue;
1171 }
1172
1173 /* terminal of (real) degree 0? */
1174 if( g->grad[i] == 2 )
1175 {
1176 /* if terminal node i is not the one with the highest prize, delete */
1177 if( !is_maxprize(scip, g, i, &maxprize) )
1178 {
1179 SCIPdebugMessage("delete degree 0 term %d prize: %f count:%d\n ", i, g->prize[i], localcount);
1180 (*fixed) += g->prize[i];
1181 localcount += graph_pc_deleteTerm(scip, g, i);
1182 }
1183 }
1184 /* terminal of (real) degree 1? */
1185 else if( g->grad[i] == 3 )
1186 {
1187 int e;
1188 for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1189 if( g->mark[g->head[e]] )
1190 break;
1191
1192 assert(e != EAT_LAST);
1193 assert(g->head[e] != g->source);
1194
1195 if( !Is_term(g->term[g->head[e]]) )
1196 {
1197 SCIP_CALL( trydg1edgepc(scip, g, fixed, NULL, count, i, e, &rerun, &maxprize) );
1198 continue;
1199 }
1200 }
1201 }
1202 }
1203
1204 /* contract adjacent positive vertices */
1205 for( int i = 0; i < nnodes; i++ )
1206 {
1207 int i1;
1208
1209 if( !(g->mark[i]) || !Is_term(g->term[i]) )
1210 continue;
1211
1212 i1 = i;
1213
1214 do
1215 {
1216 assert(g->mark[i1]);
1217 assert(g->grad[i1] > 0);
1218 assert(Is_term(g->term[i1]));
1219
1220 contracted = FALSE;
1221
1222 for( int e = g->outbeg[i1]; e != EAT_LAST; e = g->oeat[e] )
1223 {
1224 const int i2 = g->head[e];
1225 if( g->mark[i2] && Is_term(g->term[i2]) )
1226 {
1227 SCIPdebugMessage("contract tt after (local) main loop %d->%d\n ", i1, i2);
1228 SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i1, i2, i1) );
1229 localcount++;
1230 contracted = TRUE;
1231 break;
1232 }
1233 }
1234 }
1235 while( contracted );
1236 }
1237
1238 (*count) += localcount;
1239 SCIPdebugMessage("MW basic reduction package has deleted %d edges\n", *count);
1240
1241 SCIPdebugMessage("chains after: %d \n", nchains(g));
1242 assert(!adjterms(g));
1243
1244 assert(graph_valid(g));
1245
1246 SCIP_CALL( level0save(scip, g) );
1247
1248 return SCIP_OKAY;
1249 }
1250
1251 /** basic reduction tests for the HCDSTP */
reduce_simple_hc(SCIP * scip,GRAPH * g,SCIP_Real * fixed,int * count)1252 SCIP_RETCODE reduce_simple_hc(
1253 SCIP* scip, /**< SCIP data structure */
1254 GRAPH* g, /**< graph data structure */
1255 SCIP_Real* fixed, /**< pointer to offfset value */
1256 int* count /**< pointer to number of reductions */
1257 )
1258 {
1259 int i;
1260 int e;
1261 int e2;
1262 int nnodes;
1263 SCIP_Bool rerun = TRUE;
1264
1265 assert(g != NULL);
1266 assert(fixed != NULL);
1267 assert(count != NULL);
1268 assert(g->stp_type == STP_DHCSTP);
1269
1270 nnodes = g->knots;
1271
1272 SCIPdebugMessage("basic HC test: \n");
1273
1274 /* main loop */
1275 while( rerun )
1276 {
1277 rerun = FALSE;
1278
1279 /* delete incoming arcs of the root */
1280 e = g->inpbeg[g->source];
1281 while( e != EAT_LAST )
1282 {
1283 e2 = g->ieat[e];
1284
1285 if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
1286 {
1287 SCIPdebugMessage("delete incoming root arc \n");
1288 (*count)++;
1289 graph_edge_del(scip, g, e, TRUE);
1290 }
1291 else if( SCIPisLT(scip, g->cost[e], FARAWAY) )
1292 {
1293 SCIPdebugMessage("delete anti-parallel root arcs \n");
1294 g->cost[e] = FARAWAY;
1295 }
1296
1297 e = e2;
1298 }
1299
1300 /* delete outgoing arcs of the terminals (other than the root) */
1301 for( i = 0; i < nnodes; i++ )
1302 {
1303 if( Is_term(g->term[i]) && i != g->source )
1304 {
1305 e = g->outbeg[i];
1306 while( e != EAT_LAST )
1307 {
1308 e2 = g->oeat[e];
1309
1310 if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
1311 {
1312 SCIPdebugMessage("delete anti-parallel terminal arcs \n");
1313 (*count)++;
1314 graph_edge_del(scip, g, e, TRUE);
1315 }
1316
1317 e = e2;
1318 }
1319 }
1320 }
1321 }
1322
1323 SCIPdebugMessage("HC basic reduction package has deleted %d edges\n", *count);
1324
1325 return SCIP_OKAY;
1326 }
1327
1328
1329 /** basic reductions for RPCSTP and PCSPG */
reduce_simple_pc(SCIP * scip,GRAPH * g,SCIP_Real * fixed,int * count,int * solnode,SCIP_Bool contractroot)1330 SCIP_RETCODE reduce_simple_pc(
1331 SCIP* scip, /**< SCIP data structure */
1332 GRAPH* g, /**< graph data structure */
1333 SCIP_Real* fixed, /**< pointer to offset value */
1334 int* count, /**< pointer to number of reductions */
1335 int* solnode, /**< solution nodes */
1336 SCIP_Bool contractroot /**< contract vertices into root (for rooted prize-collecting) */
1337 )
1338 {
1339 int edges2[2];
1340 int nodes2[2];
1341 SCIP_Real maxprize = -1.0;
1342 const int nnodes = g->knots;
1343 const SCIP_Bool pc = (g->stp_type == STP_PCSPG);
1344 SCIP_Bool rerun = TRUE;
1345
1346 assert(g != NULL);
1347 assert(fixed != NULL);
1348 assert(count != NULL);
1349 assert(g->stp_type == STP_PCSPG || g->stp_type == STP_RPCSPG);
1350 assert(!g->extended);
1351
1352 *count = 0;
1353
1354 SCIPdebugMessage("Degree Test: ");
1355
1356 if( !pc )
1357 g->mark[g->source] = FALSE;
1358
1359 /* main loop */
1360 while( rerun )
1361 {
1362 rerun = FALSE;
1363
1364 for( int i = 0; i < nnodes; i++ )
1365 {
1366 assert(g->grad[i] >= 0);
1367 assert(!(g->mark[i] && Is_pterm(g->term[i])));
1368
1369 /* last condition should never be true, but just in case ... */
1370 if( !g->mark[i] || g->grad[i] == 0 || Is_pterm(g->term[i]) )
1371 continue;
1372
1373 if( !Is_term(g->term[i]) )
1374 {
1375 assert(SCIPisZero(scip, g->prize[i]));
1376
1377 if( g->grad[i] == 1 )
1378 {
1379 const int e1 = g->inpbeg[i];
1380 const int i1 = g->tail[e1];
1381
1382 assert(e1 >= 0);
1383 assert(e1 == Edge_anti(g->outbeg[i]));
1384 assert(g->ieat[e1] == EAT_LAST);
1385 assert(g->oeat[g->outbeg[i]] == EAT_LAST);
1386
1387 graph_edge_del(scip, g, e1, TRUE);
1388 SCIPdebugMessage("delete non-terminal of degree 1 %d\n ", i);
1389 (*count)++;
1390
1391 assert(g->grad[i] == 0);
1392
1393 /* the last node? */
1394 if( g->grad[i1] == 0 )
1395 {
1396 rerun = FALSE;
1397 break;
1398 }
1399 if( (i1 < i) && (g->grad[i1] < 3 || Is_term(g->term[i1])) )
1400 rerun = TRUE;
1401
1402 continue;
1403 }
1404
1405 /* contract non terminals of degree 2 */
1406 if( g->grad[i] == 2 )
1407 {
1408 const int e1 = g->outbeg[i];
1409 const int e2 = g->oeat[e1];
1410 const int i1 = g->head[e1];
1411 const int i2 = g->head[e2];
1412
1413 assert(e1 >= 0);
1414 assert(e2 >= 0);
1415
1416 assert(g->mark[i1] || i1 == g->source);
1417 assert(g->mark[i2] || i2 == g->source);
1418 assert(SCIPisEQ(scip, g->cost[e2], g->cost[flipedge(e2)]));
1419
1420 g->cost[e1] += g->cost[e2];
1421 g->cost[flipedge(e1)] += g->cost[e2];
1422
1423 SCIPdebugMessage("contract non-terminals %d %d \n ", i2, i);
1424 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[flipedge(e2)], NULL) );
1425 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(e1)]), g->ancestors[e2], NULL) );
1426
1427 SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
1428 (*count)++;
1429
1430 if( (Is_term(g->term[i2]) && (i2 < i)) || (Is_term(g->term[i1]) && (i1 < i)) )
1431 rerun = TRUE;
1432 }
1433 continue;
1434 }
1435
1436 /*
1437 * node i is a terminal:
1438 */
1439
1440 /* terminal of 0-prize? */
1441 if( SCIPisLE(scip, g->prize[i], 0.0) && i != g->source )
1442 {
1443 adjust0term(scip, g, i);
1444 (*count) += 2;
1445 continue;
1446 }
1447
1448 assert(Is_term(g->term[i]));
1449
1450 /* terminal of (real) degree 0? */
1451 if( ( (g->grad[i] == 2 && pc) || (g->grad[i] == 1 && !pc) ) )
1452 {
1453 /* if terminal node i is node the one with the highest prize, delete */
1454 if( !is_maxprize(scip, g, i, &maxprize) )
1455 {
1456 SCIPdebugMessage("delete 0 term %d prize: %f count:%d\n ", i, g->prize[i], *count);
1457 (*fixed) += g->prize[i];
1458 (*count) += graph_pc_deleteTerm(scip, g, i);
1459 }
1460 }
1461 /* terminal of (real) degree 1? */
1462 else if( ( (g->grad[i] == 3 && pc) || (g->grad[i] == 2 && !pc) ) )
1463 {
1464 int e;
1465 for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1466 if( g->mark[g->head[e]] || (!pc && g->head[e] == g->source) )
1467 break;
1468
1469 assert(e != EAT_LAST);
1470 assert(g->head[e] != g->source || !pc);
1471
1472 SCIP_CALL( trydg1edgepc(scip, g, fixed, solnode, count, i, e, &rerun, &maxprize) );
1473 }
1474 /* terminal of (real) degree 2? */
1475 else if( ( (g->grad[i] == 4 && pc) || (g->grad[i] == 3 && !pc) ) )
1476 {
1477 if( !is_maxprize(scip, g, i, &maxprize) )
1478 {
1479 int i2 = 0;
1480 for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1481 {
1482 const int i1 = g->head[e];
1483 if( g->mark[i1] || (!pc && i1 == g->source) )
1484 {
1485 assert(i2 < 2);
1486
1487 edges2[i2] = e;
1488 nodes2[i2++] = i1;
1489 }
1490 }
1491
1492 assert(i2 >= 2);
1493 if( SCIPisLE(scip, g->prize[i], g->cost[edges2[0]]) && SCIPisLE(scip, g->prize[i], g->cost[edges2[1]]) )
1494 {
1495 IDX* ancestors = NULL;
1496 IDX* revancestors = NULL;
1497 int n1;
1498 const int e = edges2[0];
1499 const int e1 = edges2[1];
1500
1501 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e], NULL) );
1502 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[Edge_anti(e1)], NULL) );
1503 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[Edge_anti(e)], NULL) );
1504 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[e1], NULL) );
1505 SCIPdebugMessage("delete - term - %d\n ", i);
1506
1507 /* contract edge */
1508 n1 = graph_edge_redirect(scip, g, e, nodes2[1], nodes2[0], g->cost[e] + g->cost[e1] - g->prize[i], TRUE);
1509
1510 /* new edge inserted? */
1511 if( n1 >= 0)
1512 {
1513 /* add ancestors */
1514 SCIPintListNodeFree(scip, &(g->ancestors[n1]));
1515 SCIPintListNodeFree(scip, &(g->ancestors[Edge_anti(n1)]));
1516 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[n1]), ancestors, NULL) );
1517 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(n1)]), revancestors, NULL) );
1518 }
1519 (*count) += graph_pc_deleteTerm(scip, g, i);
1520 (*fixed) += g->prize[i];
1521 SCIPintListNodeFree(scip, &(ancestors));
1522 SCIPintListNodeFree(scip, &(revancestors));
1523 }
1524 }
1525 }
1526
1527 /* try to contract adjacent terminals */
1528 if( g->grad[i] > 0 )
1529 {
1530 SCIP_Real mincost = FARAWAY;
1531 int ett = UNKNOWN;
1532
1533 for( int e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
1534 {
1535 const int i1 = g->head[e1];
1536
1537 if( !g->mark[i1] && (pc || i1 != g->source || !contractroot) )
1538 continue;
1539
1540 if( SCIPisLT(scip, g->cost[e1], mincost) )
1541 {
1542 mincost = g->cost[e1];
1543 if( Is_term(g->term[i1]) )
1544 ett = e1;
1545 }
1546 else if( Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e1], mincost) )
1547 {
1548 assert(SCIPisLT(scip, g->cost[e1], FARAWAY));
1549 assert(SCIPisEQ(scip, g->cost[e1], mincost));
1550 ett = e1;
1551 }
1552 }
1553
1554 if( ett != UNKNOWN && SCIPisLE(scip, g->cost[ett], mincost) && SCIPisLE(scip, g->cost[ett], g->prize[i])
1555 && SCIPisLE(scip, g->cost[ett], g->prize[g->head[ett]]) )
1556 {
1557 const int i1 = g->head[ett];
1558 SCIPdebugMessage("contract tt %d->%d\n ", i, i1);
1559 assert(SCIPisLT(scip, mincost, FARAWAY));
1560 *fixed += g->cost[ett];
1561 (*count)++;
1562
1563 if( i1 == g->source )
1564 {
1565 int j;
1566 int e;
1567
1568 /* get edge from i to its artificial terminal */
1569 for (e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e])
1570 if( Is_pterm(g->term[g->head[e]]) && g->head[e] != g->source )
1571 break;
1572
1573 assert(e != EAT_LAST);
1574 SCIPdebugMessage("contract rt %d->%d \n", i, i1);
1575
1576 if( g->pcancestors[i] != NULL )
1577 {
1578 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->pcancestors[i], NULL));
1579 SCIPintListNodeFree(scip, &(g->pcancestors[i]));
1580 }
1581 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[ett], NULL));
1582
1583 /* artificial terminal to i */
1584 j = g->head[e];
1585 assert(!g->mark[j]);
1586
1587 /* delete edge and unmark artificial terminal */
1588 graph_pc_knot2nonTerm(g, j);
1589 graph_edge_del(scip, g, e, TRUE);
1590
1591 /* delete remaining incident edge of artificial terminal */
1592 e = g->inpbeg[j];
1593
1594 assert(e != EAT_LAST);
1595 assert(g->source == g->tail[e] || g->source == j);
1596 assert(SCIPisEQ(scip, g->prize[i], g->cost[e]));
1597
1598 graph_edge_del(scip, g, e, TRUE);
1599
1600 assert(g->inpbeg[j] == EAT_LAST);
1601
1602 SCIP_CALL(graph_knot_contract(scip, g, solnode, i1, i));
1603 graph_pc_knot2nonTerm(g, i);
1604 } /* i1 == root */
1605 else
1606 {
1607 if( g->grad[i] >= g->grad[i1] )
1608 SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i, i1, i) );
1609 else
1610 SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i1, i, i1) );
1611 }
1612
1613 rerun = TRUE;
1614 }
1615 } /* contract adjacent terminals */
1616 } /* for i = 1, ..., nnodes */
1617 } /* main loops */
1618
1619 if( !pc )
1620 g->mark[g->source] = TRUE;
1621 SCIPdebugMessage("degree test pc: %d nodes deleted\n", *count);
1622
1623 assert(graph_valid(g));
1624
1625 SCIP_CALL( level0save(scip, g) );
1626
1627 return SCIP_OKAY;
1628 }
1629