Scippy

SCIP

Solving Constraint Integer Programs

reduce_sdutil.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reduce_sdutil.c
17  * @brief utility methods for Steiner tree reductions
18  * @author Daniel Rehfeldt
19  *
20  * This file implements utility methods for Steiner tree problem special distance reduction techniques.
21  *
22  * A list of all interface methods can be found in reduce.h.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 //#define SCIP_DEBUG
29 #include "reduce.h"
30 #include "portab.h"
31 
32 #define STP_SDN_NCLOSETERMS 4
33 #define STP_SDN_MAXDEGREE 4
34 #define STP_SDN_MAXNVISITS 4
35 
36 
37 /** see reduce.h */
39 {
40  SCIP_Real* closeterms_distN; /**< paths to N closest terms */
41  int* closetermsN; /**< close terminals */
42  SCIP_Bool* nodes_isBlocked; /**< node is blocked */
43  /** temporary arrays start: */
47  int* hitlist;
48  /** temporary arrays end */
49  int nnodesHit;
50  int N; /**< the number of closest terms per node */
51 };
52 
53 
54 /*
55  * local methods
56  */
57 
58 
59 
60 /** inserts new edge */
61 static inline
63  SCIP* scip, /**< SCIP data structure */
64  int term1, /**< end node 1 */
65  int term2, /**< end node 2 */
66  SCIP_Real edgecost, /**< cost */
67  SDGRAPH* sdgraph /**< the SD graph */
68 )
69 {
70  SCIP_Bool success;
71  const int* nodesid = reduce_sdgraphGetOrgnodesToSdMap(sdgraph);
72  const int sdnode1 = nodesid[term1];
73  const int sdnode2 = nodesid[term2];
74 
75  reduce_sdgraphInsertEdge(scip, sdnode1, sdnode2, edgecost, -1, NULL, sdgraph, &success);
76 }
77 
78 
79 /** allocates memory */
80 static
82  SCIP* scip, /**< SCIP */
83  const GRAPH* g, /**< graph to initialize from */
84  SCIP_Bool useSecond, /**< use second profit? */
85  SDPROFIT** sdprofit /**< SD profit */
86 )
87 {
88  const int nnodes = graph_get_nNodes(g);
89  SDPROFIT* sdp;
90 
91  SCIP_CALL( SCIPallocMemory(scip, sdprofit) );
92  sdp = *sdprofit;
93 
94  SCIP_CALL( SCIPallocMemoryArray(scip, &(sdp->nodes_bias), nnodes) );
95  SCIP_CALL( SCIPallocMemoryArray(scip, &(sdp->nodes_biassource), nnodes) );
96 
97  if( useSecond )
98  {
99  SCIP_CALL( SCIPallocMemoryArray(scip, &(sdp->nodes_bias2), nnodes) );
100  SCIP_CALL( SCIPallocMemoryArray(scip, &(sdp->nodes_biassource2), nnodes) );
101  }
102  else
103  {
104  sdp->nodes_bias2 = NULL;
105  sdp->nodes_biassource2 = NULL;
106  }
107 
108  return SCIP_OKAY;
109 }
110 
111 
112 /** gets SD node bias */
113 static
115  const GRAPH* g, /**< the graph */
116  SDPROFIT* sdprofit /**< SD profit */
117 )
118 {
119  const int nnodes = graph_get_nNodes(g);
120  const int pseudoroot = (graph_pc_isUnrootedPcMw(g)) ? g->source : -1;
121  const SCIP_Real* const costs = g->cost;
122  SCIP_Real* RESTRICT node_bias = sdprofit->nodes_bias;
123  int* RESTRICT node_biassource = sdprofit->nodes_biassource;
124  SCIP_Real* RESTRICT node_bias2 = sdprofit->nodes_bias2;
125  int* RESTRICT node_biassource2 = sdprofit->nodes_biassource2;
126  const SCIP_Bool isPcMw = graph_pc_isPcMw(g);
127 
128  assert(graph_pc_isPcMw(g) || !g->extended);
129  assert(node_bias2 && node_biassource2);
130 
131  for( int k = 0; k < nnodes; k++ )
132  {
133  node_bias[k] = 0.0;
134  node_biassource[k] = k;
135  node_bias2[k] = 0.0;
136  node_biassource2[k] = k;
137  }
138 
139  /* compute profits for non-terminals */
140  for( int k = 0; k < nnodes; k++ )
141  {
142  if( Is_term(g->term[k]) && k != pseudoroot )
143  {
144  int minneighbor = -1;
145  SCIP_Real mincost = isPcMw ? g->prize[k] : FARAWAY;
146  SCIP_Real mincost2 = mincost;
147 
148  for( int e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
149  {
150  const int neighbor = g->tail[e];
151 
152  if( neighbor == pseudoroot )
153  continue;
154 
155  if( costs[e] < mincost )
156  {
157  assert(!graph_pc_isPcMw(g) || !graph_pc_knotIsDummyTerm(g, neighbor));
158 
159  minneighbor = neighbor;
160  mincost2 = mincost;
161  mincost = costs[e];
162  }
163  else if( costs[e] < mincost2 )
164  {
165  mincost2 = costs[e];
166  }
167  }
168 
169  assert(minneighbor >= 0 || isPcMw || g->terms == 1);
170 
171  if( minneighbor >= 0 )
172  {
173  const SCIP_Real bias = mincost2 - mincost;
174 
175  assert(GE(bias, 0.0));
176 
177  if( bias > node_bias[minneighbor] )
178  {
179  node_bias[minneighbor] = bias;
180  node_biassource[minneighbor] = k;
181  }
182  else if( GT(bias, node_bias2[minneighbor]) )
183  {
184  node_bias2[minneighbor] = bias;
185  node_biassource2[minneighbor] = k;
186 
187  assert(node_biassource[minneighbor] != node_biassource2[minneighbor]);
188  }
189  }
190  }
191  }
192 
193  /* correct profits for terminals */
194  for( int k = 0; k < nnodes; k++ )
195  {
196  if( !Is_term(g->term[k]) )
197  {
198  continue;
199  }
200 
201  if( isPcMw )
202  {
203  if( g->prize[k] >= node_bias[k] )
204  {
205  node_bias[k] = g->prize[k];
206  node_biassource[k] = k;
207  }
208  else if( g->prize[k] >= node_bias2[k] )
209  {
210  node_bias2[k] = g->prize[k];
211  node_biassource2[k] = k;
212  }
213 
214  continue;
215  }
216 
217  node_bias[k] = FARAWAY;
218  node_biassource[k] = k;
219  node_bias2[k] = FARAWAY;
220  node_biassource2[k] = k;
221  }
222 
223 #ifndef NDEBUG
224  for( int k = 0; k < nnodes; k++ )
225  {
226  if( !Is_term(g->term[k]) )
227  {
228  assert(GE(node_bias[k], node_bias2[k]));
229  assert(node_biassource[k] != node_biassource2[k] || node_biassource[k] == k);
230  }
231  }
232 #endif
233 }
234 
235 
236 /** gets SD node bias */
237 static
239  const GRAPH* g, /**< the graph */
240  const SCIP_Real* edgecosts, /**< edge costs (w.r.t graph 'g') */
241  SDPROFIT* sdprofit /**< SD profit */
242 )
243 {
244  const int nnodes = graph_get_nNodes(g);
245  const int pseudoroot = (graph_pc_isUnrootedPcMw(g)) ? g->source : -1;
246  SCIP_Real* RESTRICT node_bias = sdprofit->nodes_bias;
247  int* RESTRICT node_biassource = sdprofit->nodes_biassource;
248  const SCIP_Bool isPcMw = graph_pc_isPcMw(g);
249 
250  assert(graph_pc_isPcMw(g) || !g->extended);
251  assert(edgecosts);
252 
253  for( int k = 0; k < nnodes; k++ )
254  {
255  node_bias[k] = 0.0;
256  node_biassource[k] = k;
257  }
258 
259  /* compute profits for non-terminals */
260  for( int k = 0; k < nnodes; k++ )
261  {
262  if( Is_term(g->term[k]) && k != pseudoroot )
263  {
264  int minneighbor = -1;
265  SCIP_Real mincost = isPcMw ? g->prize[k] : FARAWAY;
266  SCIP_Real mincost2 = mincost;
267 
268  for( int e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
269  {
270  const int neighbor = g->tail[e];
271 
272  if( neighbor == pseudoroot )
273  continue;
274 
275  if( edgecosts[e] < mincost )
276  {
277  assert(!graph_pc_isPcMw(g) || !graph_pc_knotIsDummyTerm(g, neighbor));
278 
279  minneighbor = neighbor;
280  mincost2 = mincost;
281  mincost = edgecosts[e];
282  }
283  else if( edgecosts[e] < mincost2 )
284  {
285  mincost2 = edgecosts[e];
286  }
287  }
288 
289  assert(minneighbor >= 0 || isPcMw || g->terms == 1);
290 
291  if( minneighbor >= 0 )
292  {
293  const SCIP_Real bias = mincost2 - mincost;
294 
295  assert(GE(bias, 0.0));
296 
297  if( GT(bias, node_bias[minneighbor]) )
298  {
299  node_bias[minneighbor] = bias;
300  node_biassource[minneighbor] = k;
301  }
302  }
303  }
304  }
305 
306  /* correct profits for terminals */
307  for( int k = 0; k < nnodes; k++ )
308  {
309  if( !Is_term(g->term[k]) )
310  {
311  continue;
312  }
313 
314  if( isPcMw )
315  {
316  if( g->prize[k] >= node_bias[k] )
317  {
318  node_bias[k] = g->prize[k];
319  node_biassource[k] = k;
320  }
321 
322  continue;
323  }
324 
325  node_bias[k] = FARAWAY;
326  node_biassource[k] = k;
327  }
328 }
329 
330 
331 /** updates implied profits by using exact bottleneck distances */
332 static inline
334  const GRAPH* g, /**< graph */
335  int node, /**< the node to update */
336  int sourceterm, /**< the source terminal */
337  SCIP_Real edgecost, /**< edge cost */
338  SCIP_Real bdist, /**< bottleneck distance */
339  SCIP_Bool blctree_isUpdated, /**< BLC tree fresh? */
340  SDPROFIT* sdprofit /**< the SD profit */
341 )
342 {
343  const SCIP_Real profit = bdist - edgecost;
344 
345  assert(GT(profit, 0.0));
346  assert(GE(edgecost, 0.0) && LE(edgecost, FARAWAY));
347  assert(GE(bdist, 0.0) && LE(bdist, FARAWAY));
348  assert(Is_term(g->term[sourceterm]));
349 
350 #ifndef NDEBUG
351  if( blctree_isUpdated && sourceterm == sdprofit->nodes_biassource[node] )
352  {
353  assert(GE(profit, sdprofit->nodes_bias[node]));
354  }
355  else if( blctree_isUpdated && sourceterm == sdprofit->nodes_biassource2[node] )
356  {
357  assert(GE(profit, sdprofit->nodes_bias2[node]));
358  }
359 #endif
360 
361  if( GT(profit, sdprofit->nodes_bias[node]) )
362  {
363  sdprofit->nodes_bias[node] = profit;
364  sdprofit->nodes_biassource[node] = sourceterm;
365  }
366  else if( GT(profit, sdprofit->nodes_bias2[node]) )
367  {
368  sdprofit->nodes_bias2[node] = profit;
369  sdprofit->nodes_biassource2[node] = sourceterm;
370  }
371  else if( sdprofit->nodes_biassource[node] == sdprofit->nodes_biassource2[node] )
372  {
373  sdprofit->nodes_bias2[node] = profit;
374  sdprofit->nodes_biassource2[node] = sourceterm;
375  }
376 }
377 
378 #if 0
379 /** marks terminals that can be reached from given source node */
380 static inline
381 void sdneighborMarkCloseTerms(
382  const GRAPH* g, /**< graph to initialize from */
383  int sourcenode,
384  int* RESTRICT nodes_nhits,
385  SCIP_Real* RESTRICT nodes_maxdist,
386  SD* sddata /**< SD */
387 )
388 {
389  int nnterms1;
390  SCIP_Real termdist1[4];
391  int neighbterms1[4];
392 
393  graph_tpathsGet4CloseTerms(g, sddata->terminalpaths, sourcenode, FARAWAY, neighbterms1, NULL, termdist1, &nnterms1);
394 
395  /* go over all close terminals of the source node */
396  for( int k = 0; k < nnterms1; k++ )
397  {
398  const int neighborterm = neighbterms1[k];
399  // const SCIP_Real dist = MAX(ecost, termdist1[k]); // todo also try without!
400  const SCIP_Real dist = termdist1[k];
401  assert(Is_term(g->term[neighborterm]));
402 
403  if( nodes_nhits[neighborterm] == 0 )
404  {
405  // todo save neighborterm in list
406  }
407 
408  nodes_nhits[neighborterm]++;
409 
410  if( dist > nodes_maxdist[neighborterm] )
411  nodes_maxdist[neighborterm] = dist;
412  }
413 }
414 #endif
415 
416 
417 /** marks nodes that can be reached from given source node */
418 static inline
420  SCIP* scip, /**< SCIP data structure */
421  const GRAPH* g, /**< graph to initialize from */
422  int sourcenode, /**< (neighbor) node to mark from */
423  SD* sddata /**< SD */
424 )
425 {
426  const SDPROFIT* sdprofit = sddata->sdprofit;
427  SDN* const sdneighbors = sddata->sdneighbors;
428  DIJK* RESTRICT dijkdata = sdneighbors->dijkdata;
429  int* RESTRICT nodes_nhits = sdneighbors->nodes_nhits;
430  SCIP_Real* RESTRICT nodes_maxdist = sdneighbors->nodes_maxdist;
431  const int* const visitlist = dijkdata->visitlist;
432  SCIP_Real* RESTRICT distance = dijkdata->node_distance;
433  int* RESTRICT hitlist = sdneighbors->hitlist;
434  int nvisits;
435 
436  assert(dijkdata && nodes_nhits && nodes_maxdist && hitlist);
437 
438  SCIP_CALL( graph_sdCloseNodesBiased(scip, g, sdprofit, sourcenode, dijkdata) );
439 
440  nvisits = dijkdata->nvisits;
441  assert(nvisits >= 0);
442  assert(sdneighbors->nnodesHit >= 0);
443 
444  for( int k = 0; k < nvisits; k++ )
445  {
446  const int node = visitlist[k];
447  const SCIP_Real dist = distance[node];
448 
449  if( node == sourcenode )
450  continue;
451 
452  assert(GT(dist, 0.0));
453 
454  if( nodes_nhits[node] == 0 )
455  {
456  hitlist[sdneighbors->nnodesHit++] = node;
457  assert(EQ(nodes_maxdist[node], 0.0));
458  }
459 
460  nodes_nhits[node]++;
461 
462  if( dist > nodes_maxdist[node] )
463  nodes_maxdist[node] = dist;
464  }
465 
466  graph_dijkLimited_reset(g, dijkdata);
467 
468  return SCIP_OKAY;
469 }
470 
471 
472 /** helper */
473 static
475  SCIP* scip, /**< SCIP */
476  GRAPH* g, /**< graph */
477  SDN* sdn /**< SD neighbors */
478 )
479 {
480  const int N = sdn->N;
481  SCIP_Real* const RESTRICT closeterms_distN = sdn->closeterms_distN;
482  int* const RESTRICT closetermsN = sdn->closetermsN;
483  const int nnodes = graph_get_nNodes(g);
484  int* RESTRICT nodes_nhits;
485  SCIP_Real* RESTRICT nodes_maxdist;
486 
487  assert(N >= 1);
488  assert(!sdn->nodes_nhits);
489  assert(!sdn->nodes_maxdist);
490  assert(!sdn->hitlist);
491  assert(!sdn->dijkdata);
492 
493  SCIP_CALL( SCIPallocBufferArray(scip, &(sdn->nodes_nhits), nnodes) );
494  SCIP_CALL( SCIPallocBufferArray(scip, &(sdn->nodes_maxdist), nnodes) );
495  SCIP_CALL( SCIPallocBufferArray(scip, &(sdn->hitlist), nnodes) );
496  nodes_nhits = sdn->nodes_nhits;
497  nodes_maxdist = sdn->nodes_maxdist;
498 
499  SCIP_CALL( graph_dijkLimited_init(scip, g, &(sdn->dijkdata)) );
501 
502  graph_init_dcsr(scip, g);
503 
504  for( int i = 0; i < nnodes; ++i )
505  {
506  nodes_nhits[i] = 0;
507  nodes_maxdist[i] = 0.0;
508  sdn->nodes_isBlocked[i] = FALSE;
509  }
510 
511  for( int i = 0; i < N * nnodes; ++i )
512  {
513  closeterms_distN[i] = FARAWAY;
514  closetermsN[i] = UNKNOWN;
515  }
516 
517  return SCIP_OKAY;
518 }
519 
520 
521 /** helper */
522 static
524  SCIP* scip, /**< SCIP */
525  GRAPH* g, /**< graph */
526  SDN* sdn /**< SD neighbors */
527 )
528 {
529  graph_free_dcsr(scip, g);
530  graph_dijkLimited_free(scip, &(sdn->dijkdata));
531 
532  SCIPfreeBufferArray(scip, &(sdn->hitlist));
533  SCIPfreeBufferArray(scip, &(sdn->nodes_maxdist));
534  SCIPfreeBufferArray(scip, &(sdn->nodes_nhits));
535 }
536 
537 
538 /** updates single node */
539 static inline
541  SCIP* scip, /**< SCIP */
542  const GRAPH* g, /**< graph to initialize from */
543  int node, /**< node to update */
544  int term, /**< terminal */
545  SDN* sdn, /**< SD neighbors */
546  SDGRAPH* sdgraph, /**< SD graph */
547  int* nupdates /**< number of distance updates */
548 )
549 {
550  SCIP_Real* RESTRICT nodes_maxdist = sdn->nodes_maxdist;
551  const SCIP_Real sd_new = nodes_maxdist[node];
552 
553  assert(node != term);
554  assert(GT(sd_new, 0.0) && LT(sd_new, FARAWAY));
555 
556  if( Is_term(g->term[node]) )
557  {
558  /* update the SD MST */
559  const SCIP_Real sd_org = reduce_sdgraphGetSd(term, node, sdgraph);
560  if( LT(sd_new, sd_org) )
561  {
562  (*nupdates)++;
563  sdn->nodes_isBlocked[term] = TRUE;
564  sdgraphInsertEdge(scip, term, node, sd_new, sdgraph);
565  //graph_knot_printInfo(g, term); graph_knot_printInfo(g, i); printf("term %d->%d: new=%f vs org=%f \n", term, i, nodes_maxdist[i], sdorg);
566  }
567  }
568  else
569  {
571  int* RESTRICT closetermsN = sdn->closetermsN;
572  SCIP_Real sd_max = 0.0;
573  int node_max = -1;
574  const int N = sdn->N;
575  const int nnodes = g->knots;
576 
577  assert(N >= 1);
578 
579  /* get maximum old SD */
580  for( int i = 0; i < N; i++ )
581  {
582  const int node_i = node + i * nnodes;
583  if( GT(closeterms_distN[node_i], sd_max) )
584  {
585  sd_max = closeterms_distN[node_i];
586  node_max = node_i;
587  }
588  }
589 
590  assert(GT(sd_max, 0.0));
591 
592  if( LT(sd_new, sd_max) )
593  {
594  (*nupdates)++;
595  closeterms_distN[node_max] = sd_new;
596  closetermsN[node_max] = term;
597  }
598  }
599 }
600 
601 
602 /** updates SDs by using neighbor argument */
603 static
605  SCIP* scip, /**< SCIP */
606  GRAPH* g, /**< graph to initialize from */
607  SD* sddata, /**< SD */
608  int* nupdates /**< number of distance updates */
609 )
610 {
611  SDN* const sdneighbors = sddata->sdneighbors;
612  SDGRAPH* const sdgraph = sddata->sdgraph;
613  int* RESTRICT nodes_nhits = sdneighbors->nodes_nhits;
614  SCIP_Real* RESTRICT nodes_maxdist = sdneighbors->nodes_maxdist;
615  int* RESTRICT hitlist = sdneighbors->hitlist;
616  const int nnodes = graph_get_nNodes(g);
617  const int maxdegree = STP_SDN_MAXDEGREE;
618 
619  *nupdates = 0;
620 
621  for( int term = 0; term < nnodes; ++term )
622  {
623  if( Is_term(g->term[term]) )
624  {
625  const int degree = g->grad[term];
626 
627  if( degree > maxdegree )
628  continue;
629 
630 #ifndef NDEBUG
631  for( int i = 0; i < nnodes; ++i )
632  {
633  assert(nodes_nhits[i] == 0);
634  assert(EQ(nodes_maxdist[i], 0.0));
635  }
636 #endif
637  sdneighbors->nnodesHit = 0;
638 
639  /* loop over all neighbors */
640  for( int e = g->outbeg[term]; e != EAT_LAST; e = g->oeat[e] )
641  {
642  const int neighbor = g->head[e];
643  SCIP_CALL( sdneighborMarkCloseNodes(scip, g, neighbor, sddata) );
644  }
645 
646  for( int i = 0; i < sdneighbors->nnodesHit; i++ )
647  {
648  const int hitnode = hitlist[i];
649 
650  assert(graph_knot_isInRange(g, hitnode));
651  assert(0 < nodes_nhits[hitnode] && nodes_nhits[hitnode] <= degree);
652 
653  if( nodes_nhits[hitnode] == degree && hitnode != term )
654  {
655  sdneighborUpdateNode(scip, g, hitnode, term, sdneighbors, sdgraph, nupdates);
656  }
657 
658  nodes_nhits[hitnode] = 0;
659  nodes_maxdist[hitnode] = 0.0;
660  }
661  }
662  }
663 
664  return SCIP_OKAY;
665 }
666 
667 
668 /** updates SDs by using neighbor argument */
669 static
671  SCIP* scip, /**< SCIP */
672  GRAPH* g, /**< graph to initialize from */
673  SD* sddata, /**< SD */
674  int* nupdates /**< number of distance updates */
675 )
676 {
677  SDN* sdn = sddata->sdneighbors;
678  SDGRAPH* sdgraph = sddata->sdgraph;
679  assert(sdgraph);
680 
681 //#define STP_SDN_PRINT
682 
683 #ifdef STP_SDN_PRINT
684  printf("start SDN update \n");
685 #endif
686 
687  sdneighborUpdateInit(scip, g, sdn);
688  SCIP_CALL( sdneighborUpdateExec(scip, g, sddata, nupdates) );
689 
690 #ifdef STP_SDN_PRINT
691  printf("\n before \n");
692 
693  for( int i = 0; i < MIN(10, g->terms - 1); i++ )
694  printf("%f ", sdgraph->mstcosts[i]);
695 
696  printf("\n after \n");
697 #endif
698 
699  SCIP_CALL( reduce_sdgraphMstBuild(scip, g, sdgraph) );
701 
702 #ifdef STP_SDN_PRINT
703  for( int i = 0; i < MIN(10, g->terms - 1); i++ )
704  printf("%f ", sdgraph->mstcosts[i]);
705 
706  printf("\n");
707  printf("g->terms=%d nupdates=%d \n", g->terms, *nupdates);
708  //exit(1);
709 #endif
710 
711  sdneighborUpdateFree(scip, g, sdn);
712 
713  return SCIP_OKAY;
714 
715 }
716 
717 
718 /*
719  * Interface methods
720  */
721 
722 
723 /** initializes SD structure */
725  SCIP* scip, /**< SCIP */
726  GRAPH* g, /**< graph NOTE: will mark the graph, thus not const :(
727  terrible design */
728  SD** sd /**< to initialize */
729 )
730 {
731  SD* s;
732  assert(scip);
733 
734  SCIP_CALL( SCIPallocMemory(scip, sd) );
735  s = *sd;
736 
737  s->hasNeigborUpdate = FALSE;
738  s->isBiased = FALSE;
739  s->sdprofit = NULL;
740  s->blctree = NULL;
741  s->sdneighbors = NULL;
742  SCIP_CALL( graph_tpathsInit(scip, g, &(s->terminalpaths)) );
743  SCIP_CALL( reduce_sdgraphInit(scip, g, &(s->sdgraph)) );
745 
746  return SCIP_OKAY;
747 }
748 
749 
750 /** initializes biased SD structure */
752  SCIP* scip, /**< SCIP */
753  GRAPH* g, /**< graph NOTE: will mark the graph, thus not const :(
754  terrible design */
755  SD** sd /**< to initialize */
756 )
757 {
758  SD* s;
759  assert(scip);
760 
761  SCIP_CALL( SCIPallocMemory(scip, sd) );
762  s = *sd;
763 
764  s->hasNeigborUpdate = FALSE;
765  s->isBiased = TRUE;
766  s->sdneighbors = NULL;
767  s->blctree = NULL;
768  SCIP_CALL( reduce_sdprofitInit(scip, g, &(s->sdprofit)) );
770  SCIP_CALL( reduce_sdgraphInitBiased(scip, g, s->sdprofit, &(s->sdgraph)) );
772 
773  return SCIP_OKAY;
774 }
775 
776 
777 
778 /** initializes fully biased SD structure */
780  SCIP* scip, /**< SCIP */
781  GRAPH* g, /**< graph NOTE: will mark the graph, thus not const :(
782  terrible design */
783  SD** sd /**< to initialize */
784 )
785 {
786  SD* s;
787  assert(scip);
788 
789  SCIP_CALL( SCIPallocMemory(scip, sd) );
790  s = *sd;
791 
792  s->hasNeigborUpdate = FALSE;
793  s->isBiased = TRUE;
794  s->sdneighbors = NULL;
795  SCIP_CALL( reduce_sdprofitInit(scip, g, &(s->sdprofit)) );
796  SCIP_CALL( reduce_blctreeInit(scip, g, &(s->blctree)) );
798 
801 
802 // SCIP_CALL( reduce_sdgraphInitBiased(scip, g, s->sdprofit, &(s->sdgraph)) );
803 
805 
806  return SCIP_OKAY;
807 }
808 
809 
810 /** repairs SD structure for imminent edge elimination */
812  SCIP* scip, /**< SCIP */
813  int edge, /**< edge to be deleted soon */
814  SCIP_Bool withEdgeReplacement,/**< with edge replacement? */
815  GRAPH* g, /**< graph NOTE: will mark the graph, thus not const :(
816  terrible design */
817  SD* sd /**< to be repaired */
818 )
819 {
820  assert(scip && g && sd);
821  assert(graph_edge_isInRange(g, edge));
822  assert(sd->terminalpaths);
823  assert(!sd->hasNeigborUpdate);
824  assert(!sd->isBiased);
825  assert(!sd->sdprofit);
826  assert(!sd->sdneighbors);
827 
828  SCIP_CALL( graph_tpathsRepair(scip, edge, withEdgeReplacement, g, (sd->terminalpaths)) );
829 
830  if( reduce_sdgraphEdgeIsInMst(sd->sdgraph, edge) )
831  {
832  const SCIP_Real edgecost = g->cost[edge];
833 
834  assert(EQ(g->cost[edge], g->cost[flipedge(edge)]));
835 
836  g->cost[edge] = FARAWAY;
837  g->cost[flipedge(edge)] = FARAWAY;
838 
839  reduce_sdgraphFree(scip, &(sd->sdgraph));
840 
841  SCIP_CALL( reduce_sdgraphInit(scip, g, &(sd->sdgraph)) );
843 
844  g->cost[edge] = edgecost;
845  g->cost[flipedge(edge)] = edgecost;
846  }
847 
848  return SCIP_OKAY;
849 }
850 
851 
852 /** sets up SD repairing mechanism */
854  SCIP* scip, /**< SCIP */
855  const GRAPH* g, /**< graph */
856  SD* sd /**< to be repaired */
857 )
858 {
859  assert(scip && g && sd);
860 
862 
863  return SCIP_OKAY;
864 }
865 
866 
867 /** adds biased neighbor SD structure */
869  SCIP* scip, /**< SCIP */
870  const GRAPH* g, /**< graph */
871  SD* sd /**< to add to */
872 )
873 {
874  assert(scip && g && sd);
875  assert(!sd->sdneighbors);
876  assert(!sd->hasNeigborUpdate);
877 
878  SCIP_CALL( reduce_sdneighborInit(scip, g, &(sd->sdneighbors)) );
879 
880  sd->hasNeigborUpdate = TRUE;
881 
882  return SCIP_OKAY;
883 }
884 
885 /** frees SD structure */
887  SCIP* scip, /**< SCIP */
888  SD** sd /**< to free */
889 )
890 {
891  SD* s;
892  assert(scip && sd);
893 
894  s = *sd;
895  assert(s);
896 
897  reduce_sdgraphFree(scip, &(s->sdgraph));
898  graph_tpathsFree(scip, &(s->terminalpaths));
899 
900  if( s->sdprofit )
901  reduce_sdprofitFree(scip, &(s->sdprofit));
902 
903  if( s->blctree )
904  reduce_blctreeFree(scip, &(s->blctree));
905 
906  if( s->sdneighbors )
907  reduce_sdneighborFree(scip, &(s->sdneighbors));
908 
909  SCIPfreeMemory(scip, sd);
910 }
911 
912 
913 
914 /** get blocked nodes */
915 const SCIP_Bool* reduce_sdneighborGetBlocked(const SDN* sdneighbors)
916 {
917  assert(sdneighbors);
918 
919 
920  return sdneighbors->nodes_isBlocked;
921 }
922 
923 
924 /** gets (up to) four close terminals to given node i;
925  * with strict upper bound on allowed distances */
927  const GRAPH* g, /**< graph data structure */
928  const SDN* sdneighbor, /**< SD neighbor data structure */
929  int node, /**< node */
930  SCIP_Real maxdist_strict, /**< maximum valid distance (strict) */
931  int* RESTRICT closeterms, /**< four close terminals */
932  SCIP_Real* RESTRICT closeterms_dist, /**< four close terminal distance */
933  int* RESTRICT ncloseterms /**< number of close terminals found */
934 )
935 {
936  const int nnodes = graph_get_nNodes(g);
937  const int N = sdneighbor->N;
938  const int* const terms = sdneighbor->closetermsN;
939  const SCIP_Real* const dists = sdneighbor->closeterms_distN;
940  int nterms = 0;
941 
942  assert(graph_knot_isInRange(g, node));
943  assert(N >= 1);
944 
945  for( int i = 0; i < N; i++ )
946  {
947  const int node_i = node + i * nnodes;
948 
949  if( terms[node_i] < 0 )
950  break;
951 
952  if( LT(dists[node_i], maxdist_strict) )
953  {
954  *ncloseterms = 1;
955  closeterms_dist[nterms] = dists[node_i];
956  closeterms[nterms] = terms[node_i];
957 
958  assert(graph_knot_isInRange(g, closeterms[nterms]));
959  assert(GE(closeterms_dist[nterms], 0.0));
960 
961  nterms++;
962  }
963  }
964 
965  *ncloseterms = nterms;
966 }
967 
968 
969 /** initializes SDN */
971  SCIP* scip, /**< SCIP */
972  const GRAPH* g, /**< graph to initialize from */
973  SDN** sdn /**< SD neighbors */
974 )
975 {
976  SDN* sdneighbors;
977  const int nnodes = graph_get_nNodes(g);
978  const int N = STP_SDN_NCLOSETERMS;
979 
980  assert(N >= 1);
981 
982  SCIP_CALL( SCIPallocMemory(scip, sdn) );
983 
984  sdneighbors = *sdn;
985  sdneighbors->nnodesHit = -1;
986  sdneighbors->N = N;
987  SCIP_CALL( SCIPallocMemoryArray(scip, &(sdneighbors->nodes_isBlocked), nnodes) );
988  SCIP_CALL( SCIPallocMemoryArray(scip, &(sdneighbors->closeterms_distN), N * nnodes) );
989  SCIP_CALL( SCIPallocMemoryArray(scip, &(sdneighbors->closetermsN), N * nnodes) );
990  sdneighbors->hitlist = NULL;
991  sdneighbors->nodes_maxdist = NULL;
992  sdneighbors->nodes_nhits = NULL;
993  sdneighbors->dijkdata = NULL;
994 
995  return SCIP_OKAY;
996 }
997 
998 
999 /** frees SDN */
1001  SCIP* scip, /**< SCIP */
1002  SDN** sdn /**< SD neighbors */
1003 )
1004 {
1005  SCIPfreeMemoryArray(scip, &((*sdn)->closetermsN));
1006  SCIPfreeMemoryArray(scip, &((*sdn)->closeterms_distN));
1007  SCIPfreeMemoryArray(scip, &((*sdn)->nodes_isBlocked));
1008 
1009  SCIPfreeMemory(scip, sdn);
1010 }
1011 
1012 
1013 /** updates SDs by using neighbor argument
1014  * NOTE: invalidates certain SD routines! */
1016  SCIP* scip, /**< SCIP */
1017  GRAPH* g, /**< graph to initialize from */
1018  SD* sddata, /**< SD */
1019  int* nupdates /**< number of distance updates */
1020 )
1021 {
1022  assert(scip && g && sddata && nupdates);
1023  assert(sddata->sdneighbors);
1024 
1025  sdneighborUpdate(scip, g, sddata, nupdates);
1026 
1027  return SCIP_OKAY;
1028 }
1029 
1030 
1031 /** initializes SD profit */
1033  SCIP* scip, /**< SCIP */
1034  const GRAPH* g, /**< graph to initialize from */
1035  SDPROFIT** sdprofit /**< the SD profit */
1036 )
1037 {
1038  assert(scip && g);
1039 
1040  SCIP_CALL( sdprofitAlloc(scip, g, TRUE, sdprofit) );
1041  sdprofitBuild(g, *sdprofit);
1042 
1043  return SCIP_OKAY;
1044 }
1045 
1046 
1047 /** initializes SD profit */
1049  SCIP* scip, /**< SCIP */
1050  const GRAPH* g, /**< graph to initialize from */
1051  const SCIP_Real* edgecosts, /**< edge costs (w.r.t graph 'g') */
1052  SDPROFIT** sdprofit /**< the SD profit */
1053 )
1054 {
1055  assert(scip && g);
1056 
1057  SCIP_CALL( sdprofitAlloc(scip, g, FALSE, sdprofit) );
1058  sdprofitBuild1stOnly(g, edgecosts, *sdprofit);
1059 
1060  return SCIP_OKAY;
1061 }
1062 
1063 
1064 /** prints SD profit statistics */
1066  const GRAPH* g, /**< graph to initialize from */
1067  const SDPROFIT* sdprofit /**< the SD profit */
1068 )
1069 {
1070  const int nnodes = graph_get_nNodes(g);
1071  int nnodes_profit = 0;
1072  int nnodes_nonprofit = 0;
1073  SCIP_Real avg = 0.0;
1074  const SCIP_Real* node_bias;
1075 
1076  assert(sdprofit);
1077 
1078  node_bias = sdprofit->nodes_bias;
1079 
1080  for( int k = 0; k < nnodes; k++ )
1081  {
1082  if( !Is_term(g->term[k]) )
1083  {
1084  if( GT(node_bias[k], 0.0) )
1085  {
1086  avg += node_bias[k];
1087  nnodes_profit++;
1088  }
1089  else
1090  nnodes_nonprofit++;
1091 
1092  continue;
1093  }
1094  }
1095 
1096  printf("Steiner nodes: profitable=%d non-profitable=%d .... Profit: sum=%f avg=%f\n", nnodes_profit, nnodes_nonprofit,
1097  avg, avg / (SCIP_Real) nnodes_profit);
1098 }
1099 
1100 
1101 /** frees SD profit */
1103  SCIP* scip, /**< SCIP */
1104  SDPROFIT** sdprofit /**< the SD profit */
1105 )
1106 {
1107  SDPROFIT* sdp;
1108  assert(scip && sdprofit);
1109 
1110  sdp = *sdprofit;
1111  assert(sdp);
1112 
1114  SCIPfreeMemoryArrayNull(scip, &(sdp->nodes_bias2));
1115  SCIPfreeMemoryArray(scip, &(sdp->nodes_biassource));
1116  SCIPfreeMemoryArray(scip, &(sdp->nodes_bias));
1117 
1118  SCIPfreeMemory(scip, sdprofit);
1119 }
1120 
1121 
1122 /** updates implied profits by using exact bottleneck distances */
1124  SCIP* scip, /**< SCIP */
1125  const GRAPH* g, /**< graph */
1126  const BLCTREE* blctree, /**< BLC tree */
1127  SCIP_Bool blctree_isUpdated, /**< BLC tree fresh? */
1128  SDPROFIT* sdprofit /**< the SD profit */
1129 )
1130 {
1131  SCIP_Real* RESTRICT candidate_bottlenecks;
1132  int* RESTRICT candidate_edges;
1133  int ncandidates;
1134 
1135  assert(scip && g && blctree && sdprofit);
1136 
1137  ncandidates = reduce_blctreeGetMstNedges(blctree);
1138  assert(ncandidates > 0);
1139 
1140  SCIP_CALL( SCIPallocBufferArray(scip, &candidate_bottlenecks, ncandidates) );
1141  SCIP_CALL( SCIPallocBufferArray(scip, &candidate_edges, ncandidates) );
1142  reduce_blctreeGetMstEdges(g, blctree, candidate_edges);
1143  reduce_blctreeGetMstBottlenecks(g, blctree, candidate_bottlenecks);
1144 
1145  for( int i = 0; i < ncandidates; ++i )
1146  {
1147  const int edge = candidate_edges[i];
1148  const SCIP_Real bdist = candidate_bottlenecks[i];
1149  const SCIP_Real edgecost = g->cost[edge];
1150 
1151  assert(graph_edge_isInRange(g, edge));
1152  assert(LE(edgecost, bdist));
1153 
1154  if( LT(edgecost, bdist) )
1155  {
1156  const int tail = g->tail[edge];
1157  const int head = g->head[edge];
1158 
1159  if( Is_term(g->term[tail]) )
1160  {
1161  sdprofitUpdateNode(g, head, tail, edgecost, bdist, blctree_isUpdated, sdprofit);
1162  }
1163 
1164  if( Is_term(g->term[head]) )
1165  {
1166  sdprofitUpdateNode(g, tail, head, edgecost, bdist, blctree_isUpdated, sdprofit);
1167  }
1168  }
1169  }
1170 
1171  SCIPfreeBufferArray(scip, &candidate_edges);
1172  SCIPfreeBufferArray(scip, &candidate_bottlenecks);
1173 
1174  return SCIP_OKAY;
1175 }
1176 
1177 
1178 /** builds implied profits by using exact bottleneck distances */
1180  SCIP* scip, /**< SCIP */
1181  const GRAPH* g, /**< graph */
1182  const BLCTREE* blctree, /**< BLC tree */
1183  SCIP_Bool blctree_isUpdated, /**< BLC tree fresh? */
1184  SDPROFIT* sdprofit /**< the SD profit */
1185 )
1186 {
1187  assert(scip && g && blctree && sdprofit);
1188 
1189  sdprofitBuild(g, sdprofit);
1190  SCIP_CALL( reduce_sdprofitUpdateFromBLC(scip, g, blctree, blctree_isUpdated, sdprofit) );
1191 
1192  return SCIP_OKAY;
1193 }
void reduce_sdprofitPrintStats(const GRAPH *g, const SDPROFIT *sdprofit)
SCIP_RETCODE reduce_sdgraphMstBuild(SCIP *, const GRAPH *, SDGRAPH *)
SCIP_RETCODE reduce_sdgraphInit(SCIP *, const GRAPH *, SDGRAPH **)
static volatile int nterms
Definition: interrupt.c:38
SCIP_RETCODE reduce_sdRepair(SCIP *scip, int edge, SCIP_Bool withEdgeReplacement, GRAPH *g, SD *sd)
static SCIP_RETCODE sdneighborUpdateInit(SCIP *scip, GRAPH *g, SDN *sdn)
SCIP_RETCODE reduce_sdInit(SCIP *scip, GRAPH *g, SD **sd)
int *RESTRICT head
Definition: graphdefs.h:224
int source
Definition: graphdefs.h:195
void reduce_blctreeGetMstEdges(const GRAPH *, const BLCTREE *, int *)
Definition: reduce_util.c:1230
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_RETCODE reduce_sdInitBiasedBottleneck(SCIP *scip, GRAPH *g, SD **sd)
#define STP_SDN_NCLOSETERMS
Definition: reduce_sdutil.c:32
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
static void sdneighborUpdateFree(SCIP *scip, GRAPH *g, SDN *sdn)
int terms
Definition: graphdefs.h:192
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
static void sdgraphInsertEdge(SCIP *scip, int term1, int term2, SCIP_Real edgecost, SDGRAPH *sdgraph)
Definition: reduce_sdutil.c:62
void reduce_sdneighborGetCloseTerms(const GRAPH *g, const SDN *sdneighbor, int node, SCIP_Real maxdist_strict, int *RESTRICT closeterms, SCIP_Real *RESTRICT closeterms_dist, int *RESTRICT ncloseterms)
void graph_free_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1807
static void sdprofitBuild(const GRAPH *g, SDPROFIT *sdprofit)
SCIP_Real reduce_sdgraphGetSd(int, int, SDGRAPH *)
SCIP_RETCODE reduce_sdprofitBuildFromBLC(SCIP *scip, const GRAPH *g, const BLCTREE *blctree, SCIP_Bool blctree_isUpdated, SDPROFIT *sdprofit)
#define FALSE
Definition: def.h:87
void reduce_sdgraphInitOrderedMstCosts(SDGRAPH *)
int *RESTRICT inpbeg
Definition: graphdefs.h:202
#define TRUE
Definition: def.h:86
void reduce_sdneighborFree(SCIP *scip, SDN **sdn)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void reduce_sdgraphFree(SCIP *, SDGRAPH **)
SCIP_RETCODE reduce_sdgraphInitBiased(SCIP *, const GRAPH *, const SDPROFIT *, SDGRAPH **)
#define EAT_LAST
Definition: graphdefs.h:58
#define FARAWAY
Definition: graphdefs.h:89
static SCIP_RETCODE sdneighborMarkCloseNodes(SCIP *scip, const GRAPH *g, int sourcenode, SD *sddata)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
const SCIP_Bool * reduce_sdneighborGetBlocked(const SDN *sdneighbors)
SCIP_RETCODE reduce_blctreeInit(SCIP *, GRAPH *, BLCTREE **)
Definition: reduce_util.c:1168
SCIP_RETCODE graph_init_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1721
SCIP_RETCODE reduce_sdprofitUpdateFromBLC(SCIP *scip, const GRAPH *g, const BLCTREE *blctree, SCIP_Bool blctree_isUpdated, SDPROFIT *sdprofit)
void graph_dijkLimited_reset(const GRAPH *, DIJK *)
Definition: graph_util.c:2105
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE graph_tpathsInitBiased(SCIP *, const SDPROFIT *, GRAPH *, TPATHS **)
Definition: graph_tpath.c:1700
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
SCIP_RETCODE reduce_sdUpdateWithSdNeighbors(SCIP *scip, GRAPH *g, SD *sddata, int *nupdates)
SCIP_Bool extended
Definition: graphdefs.h:267
#define STP_SDN_MAXNVISITS
Definition: reduce_sdutil.c:34
static void sdprofitUpdateNode(const GRAPH *g, int node, int sourceterm, SCIP_Real edgecost, SCIP_Real bdist, SCIP_Bool blctree_isUpdated, SDPROFIT *sdprofit)
SCIP_Real * prize
Definition: graphdefs.h:210
int *RESTRICT grad
Definition: graphdefs.h:201
void reduce_sdgraphMstSortCosts(SDGRAPH *)
SCIP_RETCODE graph_tpathsRepair(SCIP *, int, SCIP_Bool, const GRAPH *, TPATHS *)
Definition: graph_tpath.c:1744
static SCIP_RETCODE sdneighborUpdate(SCIP *scip, GRAPH *g, SD *sddata, int *nupdates)
#define NULL
Definition: lpi_spx1.cpp:155
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
void reduce_sdprofitFree(SCIP *scip, SDPROFIT **sdprofit)
void reduce_sdgraphInsertEdge(SCIP *, int, int, SCIP_Real, int, int *RESTRICT, SDGRAPH *, SCIP_Bool *)
#define LT(a, b)
Definition: portab.h:81
SCIP_RETCODE graph_tpathsRepairSetUp(const GRAPH *, TPATHS *)
Definition: graph_tpath.c:1719
void reduce_sdFree(SCIP *scip, SD **sd)
SCIP_RETCODE reduce_sdInitBiased(SCIP *scip, GRAPH *g, SD **sd)
SCIP_RETCODE graph_dijkLimited_init(SCIP *, const GRAPH *, DIJK **)
Definition: graph_util.c:1989
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE reduce_sdprofitInit(SCIP *scip, const GRAPH *g, SDPROFIT **sdprofit)
#define GT(a, b)
Definition: portab.h:84
void graph_dijkLimited_free(SCIP *, DIJK **)
Definition: graph_util.c:2143
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
SCIP_RETCODE reduce_sdRepairSetUp(SCIP *scip, const GRAPH *g, SD *sd)
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
SCIP_RETCODE reduce_sdAddNeighborSd(SCIP *scip, const GRAPH *g, SD *sd)
int *RESTRICT term
Definition: graphdefs.h:196
SCIP_Real *RESTRICT nodes_bias2
Definition: reducedefs.h:138
void graph_tpathsGet4CloseTerms(const GRAPH *, const TPATHS *, int, SCIP_Real, int *RESTRICT, int *RESTRICT, SCIP_Real *RESTRICT, int *RESTRICT)
SCIP_Bool reduce_sdgraphEdgeIsInMst(const SDGRAPH *, int)
SCIP_RETCODE reduce_sdgraphInitBiasedFromTpaths(SCIP *, GRAPH *, const SDPROFIT *, const TPATHS *, SDGRAPH **)
Portable definitions.
SCIP_RETCODE graph_sdCloseNodesBiased(SCIP *, const GRAPH *, const SDPROFIT *, int, DIJK *)
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_RETCODE reduce_sdneighborInit(SCIP *scip, const GRAPH *g, SDN **sdn)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Real *RESTRICT nodes_bias
Definition: reducedefs.h:137
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
const int * reduce_sdgraphGetOrgnodesToSdMap(const SDGRAPH *)
int reduce_blctreeGetMstNedges(const BLCTREE *)
Definition: reduce_util.c:1218
SCIP_Bool graph_pc_isUnrootedPcMw(const GRAPH *)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_RETCODE graph_tpathsInit(SCIP *, GRAPH *, TPATHS **)
Definition: graph_tpath.c:1682
#define SCIP_Real
Definition: def.h:177
#define STP_SDN_MAXDEGREE
Definition: reduce_sdutil.c:33
static SCIP_RETCODE sdprofitAlloc(SCIP *scip, const GRAPH *g, SCIP_Bool useSecond, SDPROFIT **sdprofit)
Definition: reduce_sdutil.c:81
static void sdneighborUpdateNode(SCIP *scip, const GRAPH *g, int node, int term, SDN *sdn, SDGRAPH *sdgraph, int *nupdates)
SCIP_RETCODE reduce_sdprofitInit1stOnly(SCIP *scip, const GRAPH *g, const SCIP_Real *edgecosts, SDPROFIT **sdprofit)
int *RESTRICT outbeg
Definition: graphdefs.h:204
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
static void sdprofitBuild1stOnly(const GRAPH *g, const SCIP_Real *edgecosts, SDPROFIT *sdprofit)
void reduce_blctreeFree(SCIP *, BLCTREE **)
Definition: reduce_util.c:1201
static SCIP_RETCODE sdneighborUpdateExec(SCIP *scip, GRAPH *g, SD *sddata, int *nupdates)
includes various reduction methods for Steiner tree problems
void graph_tpathsFree(SCIP *, TPATHS **)
Definition: graph_tpath.c:2300
void reduce_blctreeGetMstBottlenecks(const GRAPH *, const BLCTREE *, SCIP_Real *)
Definition: reduce_util.c:1349