Scippy

SCIP

Solving Constraint Integer Programs

extreduce_data.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 extreduce_data.c
17  * @brief plain data storages for extended reduction techniques for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements several (relatively) plain data storages needed for extended reduction techniques.
21  * Basically data transfer objects with additional setup, free, and cleaning methods.
22  *
23  * A list of all interface methods can be found in extreduce.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 // #define SCIP_DEBUG
29 // #define STP_DEBUG_EXT
30 
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <assert.h>
34 #include "graph.h"
35 #include "portab.h"
36 #include "extreduce.h"
37 
38 
39 
40 
41 
42 /** helper function */
43 static inline
45  MLDISTS* sds /**< distance structure */
46 )
47 {
48  const int nlevels = extreduce_mldistsNlevels(sds);
49 
50  assert(nlevels == 2 || nlevels == 1);
51 
53 
54  if( nlevels == 2 )
56 }
57 
58 
59 /** helper function */
60 static inline
62  CSRDEPO* msts /**< CSR depository containing MSTs */
63 )
64 {
65 #ifndef NDEBUG
66  const int nmsts = graph_csrdepo_getNcsrs(msts);
67 
68  assert(nmsts == 1 || nmsts == 2);
69 #endif
70 
71  graph_csrdepo_clean(msts);
72 }
73 
74 
75 /** cleans-up after trying to rule out a component */
77  SCIP* scip, /**< SCIP */
78  const GRAPH* graph, /**< graph data structure */
79  const EXTCOMP* extcomp, /**< component to be cleaned for */
80  SCIP_Bool unhash, /**< unhash component? */
81  EXTDATA* extdata /**< extension data */
82 )
83 {
84  REDDATA* const reddata = extdata->reddata;
85  MLDISTS* const sds_vertical = reddata->sds_vertical;
86  MLDISTS* const sds_horizontal = reddata->sds_horizontal;
87  CSRDEPO* const msts_comp = reddata->msts_comp;
88  CSRDEPO* const msts_levelbase = reddata->msts_levelbase;
89  const int* const compedges = extcomp->compedges;
90  const int ncompedges = extcomp->ncompedges;
91  int* const tree_deg = extdata->tree_deg;
92  int* const pseudoancestor_mark = extdata->reddata->pseudoancestor_mark;
93  SCIP_Bool* const sdeq_edgesIsForbidden = extdata->sdeq_edgesIsForbidden;
94  const STP_Vectype(int) sdeq_resetStack = extdata->sdeq_resetStack;
95  const int sdeq_size = StpVecGetSize(sdeq_resetStack);
96 
97  assert(ncompedges >= 1);
98  assert(sdeq_size >= 0);
99 
100  for( int i = 0; i < ncompedges; ++i )
101  {
102  const int edge = compedges[i];
103  const int head = graph->head[edge];
104  const int tail = graph->tail[edge];
105 
106  assert(graph_edge_isInRange(graph, edge));
107 
108  tree_deg[head] = 0;
109  tree_deg[tail] = 0;
110 
111  if( unhash )
112  {
113  graph_pseudoAncestors_unhashEdge(graph->pseudoancestors, edge, pseudoancestor_mark);
114  }
115  }
116 
117  if( unhash && extInitialCompIsGenStar(extdata) )
118  {
119  const int centeredge = extcomp->genstar_centeredge;
120  assert(graph_edge_isInRange(graph, centeredge));
121 
122  graph_pseudoAncestors_unhashEdge(graph->pseudoancestors, centeredge, pseudoancestor_mark);
123  }
124 
125  for( int i = 0; i < sdeq_size; i++ )
126  {
127  const int edge = sdeq_resetStack[i];
128 
129  assert(graph_edge_isInRange(graph, 2 * edge));
130  assert(sdeq_edgesIsForbidden[edge]);
131 
132  sdeq_edgesIsForbidden[edge] = FALSE;
133  }
134  extdata->sdeq_hasForbiddenEdges = FALSE;
135 
136  StpVecFree(scip, extdata->sdeq_resetStack);
137 
138  postCleanSDs(sds_vertical);
139  postCleanSDs(sds_horizontal);
140 
141  if( extReddataHasBiasedSds(reddata) )
142  {
143  postCleanSDs(reddata->sdsbias_vertical);
145  }
146 
147  postCleanMSTs(msts_comp);
148  postCleanMSTs(msts_levelbase);
149 
150  extreduce_extdataClean(extdata);
152  extreduce_pcdataClean(extdata->pcdata);
153 
154  assert(extreduce_extdataIsClean(graph, extdata));
155  assert(extreduce_reddataIsClean(graph, extdata->reddata));
156  assert(extreduce_pcdataIsClean(graph, extdata->pcdata));
157 }
158 
159 
160 /** initialize permanent extension data struct
161  * NOTE: Sets distdata and reddata entries to NULL, since non-owned */
163  SCIP* scip, /**< SCIP */
164  enum EXTRED_MODE mode, /**< mode */
165  const GRAPH* graph, /**< graph data structure */
166  STP_Bool* edgedeleted, /**< edge array to mark which directed edge can be removed */
167  EXTPERMA** extpermanent /**< (uninitialized) extension data */
168 )
169 {
170  EXTPERMA* extperm;
171  STP_Vectype(int)* nodes_implied = NULL;
172  SCIP_Bool* isterm = NULL;
173  SCIP_Real* bottleneckDistNode = NULL;
174  SCIP_Real* pcSdToNode = NULL;
175  int* tree_deg = NULL;
176  const int nnodes = graph_get_nNodes(graph);
177  const int msts_datasize = STP_EXT_MAXDFSDEPTH * STP_EXTTREE_MAXNLEAVES_GUARD * 2;
178  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
179  const int msts_maxn = STP_EXT_MAXDFSDEPTH_GUARD;
180 
181 #ifndef NDEBUG
182  const SCIP_Bool sds_vertical_useids = TRUE;
183 #else
184  const SCIP_Bool sds_vertical_useids = FALSE;
185 #endif
186 
187  assert(scip && extpermanent);
188  assert(mode == extred_fast || mode == extred_full);
189 
190  SCIP_CALL( SCIPallocMemory(scip, extpermanent) );
191  extperm = *extpermanent;
192 
193  SCIP_CALL( SCIPallocMemoryArray(scip, &nodes_implied, nnodes) );
194  SCIP_CALL( SCIPallocMemoryArray(scip, &isterm, nnodes) );
195  SCIP_CALL( SCIPallocMemoryArray(scip, &tree_deg, nnodes) );
196  SCIP_CALL( SCIPallocMemoryArray(scip, &bottleneckDistNode, nnodes) );
197 
198  if( pcmw )
199  {
200  SCIP_CALL( SCIPallocMemoryArray(scip, &pcSdToNode, nnodes) );
201  }
202 
203  reduce_impliedNodesGet(scip, graph, nodes_implied);
204  SCIP_CALL( reduce_dcmstInit(scip, STP_EXTTREE_MAXNLEAVES_GUARD, &(extperm->dcmst)) );
205  SCIP_CALL( graph_csrdepo_init(scip, msts_maxn, msts_datasize, &(extperm->msts_comp)) );
206  SCIP_CALL( graph_csrdepo_init(scip, msts_maxn, msts_datasize, &(extperm->msts_levelbase)) );
207 
209  STP_EXTTREE_MAXNLEAVES_GUARD, 1, sds_vertical_useids, &(extperm->sds_vertical)) );
210 
212  STP_EXT_MAXGRAD, 1, TRUE, &(extperm->sds_horizontal)) );
213 
215  STP_EXTTREE_MAXNLEAVES_GUARD, &(extperm->contration)) );
216 
217  extperm->randnumgen = NULL;
218  extperm->sdsbias_horizontal = NULL;
219  extperm->sdsbias_vertical = NULL;
220  extperm->distdata_default = NULL;
221  extperm->distdata_biased = NULL;
222  extperm->redcostdata = NULL;
223  extperm->solIsValid = FALSE;
224 
225  extperm->result = NULL;
226  extperm->nodes_implications = nodes_implied;
227  extperm->edgedeleted = edgedeleted;
228  extperm->isterm = isterm;
229  extperm->bottleneckDistNode = bottleneckDistNode;
230  extperm->pcSdToNode = pcSdToNode;
231  extperm->tree_deg = tree_deg;
232  extperm->nnodes = nnodes;
233  extperm->redcostEqualAllow = FALSE;
234  extperm->useSdBias = FALSE;
235  extperm->mode = mode;
236  extperm->tree_maxdepth = extreduce_getMaxTreeDepth(graph, extperm);
239 
240  if( pcmw )
241  {
242  assert(pcSdToNode);
243 
244  for( int k = 0; k < nnodes; k++ )
245  pcSdToNode[k] = -1.0;
246  }
247 
248  graph_getIsTermArray(graph, isterm);
249 
250  for( int k = 0; k < nnodes; k++ )
251  {
252  bottleneckDistNode[k] = -1.0;
253 
254  if( graph->mark[k] )
255  tree_deg[k] = 0;
256  else
257  tree_deg[k] = -1;
258  }
259 
260  assert(extreduce_extPermaIsClean(graph, extperm));
261 
262  return SCIP_OKAY;
263 }
264 
265 
266 /** adds random number generator */
268  SCIP_RANDNUMGEN* randnumgen, /**< random number generator to add (NON-OWNED!) */
269  EXTPERMA* extpermanent /**< (initialized) extension data */
270 )
271 {
272  assert(extpermanent && randnumgen);
273 
274  extpermanent->randnumgen = randnumgen;
275 }
276 
277 
278 /** adds biased ML distances containers */
280  SCIP* scip, /**< SCIP */
281  EXTPERMA* extpermanent /**< (initialized) extension data */
282 )
283 {
284  const int msts_maxn = STP_EXT_MAXDFSDEPTH_GUARD;
285 #ifndef NDEBUG
286  const SCIP_Bool sds_vertical_useids = TRUE;
287 #else
288  const SCIP_Bool sds_vertical_useids = FALSE;
289 #endif
290 
291  assert(scip && extpermanent);
292  assert(!extpermanent->sdsbias_vertical && !extpermanent->sdsbias_horizontal);
293 
295  STP_EXTTREE_MAXNLEAVES_GUARD, 1, sds_vertical_useids, &(extpermanent->sdsbias_vertical)) );
296 
298  STP_EXT_MAXGRAD, 1, TRUE, &(extpermanent->sdsbias_horizontal)) );
299 
300  return SCIP_OKAY;
301 }
302 
303 
304 /** initialize permanent extension data struct */
306  const GRAPH* graph, /**< graph data structure */
307  const EXTPERMA* extperm /**< extension data */
308 )
309 {
310  const SCIP_Real* bottleneckDistNode = NULL;
311  const SCIP_Real* pcSdToNode = NULL;
312  const int* tree_deg = NULL;
313  const int nnodes = graph_get_nNodes(graph);
314 
315  assert(extperm);
316 
317  if( extperm->edgedeleted )
318  {
319  SCIPdebugMessage("use of edge-deleted array is deprecated! \n");
320  return FALSE;
321  }
322 
323  bottleneckDistNode = extperm->bottleneckDistNode;
324  pcSdToNode = extperm->pcSdToNode;
325  tree_deg = extperm->tree_deg;
326 
327  if( nnodes != extperm->nnodes )
328  {
329  SCIPdebugMessage("inconsistent number of nodes \n");
330  return FALSE;
331  }
332 
333  if( !graph_csrdepo_isEmpty(extperm->msts_comp) )
334  {
335  SCIPdebugMessage("msts_comp not empty! \n");
336  return FALSE;
337  }
338 
339  if( !graph_csrdepo_isEmpty(extperm->msts_levelbase) )
340  {
341  SCIPdebugMessage("msts_reduced not empty! \n");
342  return FALSE;
343  }
344 
345  if( !extreduce_mldistsIsEmpty(extperm->sds_vertical) )
346  {
347  SCIPdebugMessage("sds_vertical not empty! size=%d \n", extreduce_mldistsNlevels(extperm->sds_vertical));
348  return FALSE;
349  }
350 
352  {
353  SCIPdebugMessage("sds_horizontal not empty! \n");
354  return FALSE;
355  }
356 
357  if( extperm->sdsbias_vertical && !extreduce_mldistsIsEmpty(extperm->sdsbias_vertical) )
358  {
359  SCIPdebugMessage("sdsbias_vertical not empty! size=%d \n", extreduce_mldistsNlevels(extperm->sds_vertical));
360  return FALSE;
361  }
362 
364  {
365  SCIPdebugMessage("sdsbias_horizontal not empty! \n");
366  return FALSE;
367  }
368 
369  for( int i = 0; i < nnodes; i++ )
370  {
371  if( !(tree_deg[i] == 0 || tree_deg[i] == -1) )
372  return FALSE;
373 
374  if( bottleneckDistNode[i] > -0.5 )
375  return FALSE;
376 
377  if( pcSdToNode && !EQ(pcSdToNode[i], -1.0) )
378  return FALSE;
379  }
380 
381  return TRUE;
382 }
383 
384 
385 /** frees extension data */
387  SCIP* scip, /**< SCIP */
388  EXTPERMA** extpermanent /**< extension data */
389 )
390 {
391  EXTPERMA* extperm;
392 
393  assert(scip && extpermanent);
394 
395  extperm = *extpermanent;
396 
397  if( extperm->sdsbias_vertical )
398  extreduce_mldistsFree(scip, &(extperm->sdsbias_vertical));
399 
400  if( extperm->sdsbias_horizontal )
401  extreduce_mldistsFree(scip, &(extperm->sdsbias_horizontal));
402 
403  extreduce_contractionFree(scip, &(extperm->contration));
404  extreduce_mldistsFree(scip, &(extperm->sds_horizontal));
405  extreduce_mldistsFree(scip, &(extperm->sds_vertical));
406  graph_csrdepo_free(scip, &(extperm->msts_comp));
407  graph_csrdepo_free(scip, &(extperm->msts_levelbase));
408  reduce_dcmstFree(scip, &(extperm->dcmst));
409 
410  SCIPfreeMemoryArrayNull(scip, &(extperm->pcSdToNode));
411  SCIPfreeMemoryArray(scip, &(extperm->bottleneckDistNode));
412  SCIPfreeMemoryArray(scip, &(extperm->tree_deg));
413  SCIPfreeMemoryArray(scip, &(extperm->isterm));
414 
415  for( int i = extperm->nnodes - 1; i >= 0; i-- )
416  {
417  StpVecFree(scip, extperm->nodes_implications[i]);
418  }
419  SCIPfreeMemoryArray(scip, &(extperm->nodes_implications));
420 
421  SCIPfreeMemory(scip, extpermanent);
422 }
423 
424 
425 /** cleans extension data */
427  EXTDATA* extdata /**< extension data */
428 )
429 {
430  assert(extdata);
431 
432  extdata->extstack_ncomponents = 0;
433  extdata->tree_nDelUpArcs = 0;
434  extdata->tree_nleaves = 0;
435  extdata->tree_ninnerNodes = 0;
436  extdata->tree_nedges = 0;
437  extdata->tree_depth = 0;
438  extdata->tree_root = -1;
439  extdata->tree_starcenter = -1;
440  extdata->tree_cost = 0.0;
441  extdata->ncostupdatestalls = 0;
442 }
443 
444 
445 /** cleans reduction data */
447  REDDATA* reddata /**< reduction data */
448 )
449 {
450  const int redcost_nlevels = reddata->redcost_nlevels;
451  SCIP_Real* const redcost_treecosts = reddata->redcost_treecosts;
452 
453  assert(redcost_nlevels >= 1);
454  assert(reddata->contration);
455 
456  for( int i = 0; i < redcost_nlevels; i++ )
457  {
458  redcost_treecosts[i] = 0.0;
459  }
460 }
461 
462 
463 /** cleans PC data */
465  PCDATA* pcdata /**< PC data */
466 )
467 {
468  assert(pcdata);
469 
470  pcdata->tree_innerPrize = 0.0;
471 }
472 
473 
474 /** is the extension data clean? */
476  const GRAPH* graph, /**< graph data structure */
477  const EXTDATA* extdata /**< extension data */
478 )
479 {
480  const int nnodes = graph_get_nNodes(graph);
481  const int nedges = graph_get_nEdges(graph);
482 
483  if( extdata->extstack_ncomponents != 0 )
484  {
485  printf("extdata->extstack_ncomponents %d \n", extdata->extstack_ncomponents);
486  return FALSE;
487  }
488 
489  if( extdata->tree_nDelUpArcs != 0 )
490  {
491  printf("extdata->tree_nDelUpArcs %d \n", extdata->tree_nDelUpArcs);
492  return FALSE;
493  }
494 
495  if( !EQ(extdata->tree_cost, 0.0) )
496  {
497  printf("extdata->tree_cost %f \n", extdata->tree_cost);
498  return FALSE;
499  }
500 
501  if( extdata->ncostupdatestalls != 0 )
502  {
503  printf("extdata->ncostupdatestalls %d \n", extdata->ncostupdatestalls);
504  return FALSE;
505  }
506 
507  if( extdata->tree_nleaves != 0 )
508  {
509  printf("extdata->tree_nleaves %d \n", extdata->tree_nleaves);
510  return FALSE;
511  }
512 
513  if( extdata->tree_ninnerNodes != 0 )
514  {
515  printf("extdata->tree_ninnerNodes %d \n", extdata->tree_ninnerNodes);
516  return FALSE;
517  }
518 
519  if( extdata->tree_root != -1 )
520  {
521  printf("extdata->tree_root %d \n", extdata->tree_root);
522  return FALSE;
523  }
524 
525  if( extdata->tree_nedges != 0 )
526  {
527  printf("extdata->tree_nedges %d \n", extdata->tree_nedges);
528  return FALSE;
529  }
530 
531  if( extdata->tree_starcenter != -1 )
532  {
533  printf("extdata->tree_starcenter %d \n", extdata->tree_starcenter);
534  return FALSE;
535  }
536 
537  if( extdata->tree_depth != 0 )
538  {
539  printf("extdata->tree_depth %d \n", extdata->tree_depth);
540  return FALSE;
541  }
542 
543  for( int i = 0; i < nnodes; i++ )
544  {
545  if( !(extdata->tree_deg[i] == 0 || extdata->tree_deg[i] == -1) )
546  {
547  printf("extdata->tree_deg[i] %d \n", extdata->tree_deg[i]);
548  return FALSE;
549  }
550 
551  if( !EQ(extdata->tree_bottleneckDistNode[i], -1.0) )
552  {
553  printf("extdata->bottleneckDistNode[i] %f \n", extdata->tree_bottleneckDistNode[i]);
554  return FALSE;
555  }
556  }
557 
558  for( int i = 0; i < nedges / 2; ++i )
559  {
560  if( extdata->sdeq_edgesIsForbidden[i] )
561  {
562  printf("extdata->sdeq_edgesIsForbidden[%d] not reset \n", i);
563  return FALSE;
564  }
565  }
566 
567  return TRUE;
568 }
569 
570 
571 /** is the reduction data clean? */
573  const GRAPH* graph, /**< graph data structure */
574  const REDDATA* reddata /**< reduction data */
575 )
576 {
577  const int nancestors = graph_pseudoAncestorsGetHashArraySize(graph->pseudoancestors);
578  const int redcost_nlevels = reddata->redcost_nlevels;
579  const SCIP_Real* const redcost_treecosts = reddata->redcost_treecosts;
580 
581  assert(redcost_nlevels >= 1);
582 
583  for( int i = 0; i < nancestors; i++ )
584  {
585  if( reddata->pseudoancestor_mark[i] != 0 )
586  {
587  printf("%d pseudoancestor_mark %d \n", i, reddata->pseudoancestor_mark[i]);
588  return FALSE;
589  }
590  }
591 
592  for( int i = 0; i < redcost_nlevels; i++ )
593  {
594  if( !EQ(redcost_treecosts[i], 0.0) )
595  {
596  printf("FAIL: tree redcost %f for level %d \n", redcost_treecosts[i], i);
597  return FALSE;
598  }
599  }
600 
601  return TRUE;
602 }
603 
604 /** is the reduction data clean? */
606  const GRAPH* graph, /**< graph data structure */
607  const PCDATA* pcdata /**< PC data */
608 )
609 {
610  const int nnodes = graph_get_nNodes(graph);
611 
612  assert(pcdata);
613 
614  if( !graph_pc_isPc(graph) )
615  {
616  return TRUE;
617  }
618 
619  if( pcdata->nPcSdCands != -1 )
620  {
621  return FALSE;
622  }
623 
624  if( pcdata->pcSdStart != -1 )
625  {
626  return FALSE;
627  }
628 
629  if( !EQ(pcdata->tree_innerPrize, 0.0) )
630  {
631  return FALSE;
632  }
633 
634  for( int i = 0; i < nnodes; i++ )
635  {
636  if( !EQ(pcdata->pcSdToNode[i], -1.0) )
637  {
638  printf("pcSdToNode[%d]=%f \n", i, pcdata->pcSdToNode[i]);
639  return FALSE;
640  }
641  }
642 
643 
644  return TRUE;
645 }
void extreduce_extPermaFree(SCIP *scip, EXTPERMA **extpermanent)
#define STP_Vectype(type)
Definition: stpvector.h:44
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
void graph_pseudoAncestors_unhashEdge(const PSEUDOANS *, int, int *)
void graph_csrdepo_clean(CSRDEPO *)
Definition: graph_util.c:781
#define StpVecGetSize(vec)
Definition: stpvector.h:139
static SCIP_Bool extInitialCompIsGenStar(const EXTDATA *extdata)
int *RESTRICT head
Definition: graphdefs.h:224
enum EXTRED_MODE mode
#define STP_EXTTREE_MAXNEDGES
Definition: extreducedefs.h:46
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
void graph_getIsTermArray(const GRAPH *, SCIP_Bool *)
Definition: graph_base.c:540
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void extreduce_contractionFree(SCIP *, CONTRACT **)
SCIP_RETCODE extreduce_extPermaInit(SCIP *scip, enum EXTRED_MODE mode, const GRAPH *graph, STP_Bool *edgedeleted, EXTPERMA **extpermanent)
SCIP_Real tree_innerPrize
SCIP_Real *const redcost_treecosts
int graph_pseudoAncestorsGetHashArraySize(const PSEUDOANS *)
void reduce_impliedNodesGet(SCIP *, const GRAPH *, STP_Vectype(int) *)
Definition: reduce_util.c:937
SCIP_Bool extreduce_pcdataIsClean(const GRAPH *graph, const PCDATA *pcdata)
void extreduce_extCompClean(SCIP *scip, const GRAPH *graph, const EXTCOMP *extcomp, SCIP_Bool unhash, EXTDATA *extdata)
#define FALSE
Definition: def.h:87
int *const pseudoancestor_mark
static void postCleanMSTs(CSRDEPO *msts)
#define TRUE
Definition: def.h:86
int extreduce_mldistsNlevels(const MLDISTS *)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
#define STP_EXT_MAXDFSDEPTH
Definition: extreducedefs.h:38
SCIP_RETCODE reduce_dcmstInit(SCIP *, int, DCMST **)
Definition: reduce_util.c:1385
void extreduce_extPermaAddRandnumgen(SCIP_RANDNUMGEN *randnumgen, EXTPERMA *extpermanent)
#define SCIPdebugMessage
Definition: pub_message.h:87
void extreduce_reddataClean(REDDATA *reddata)
SCIP_Bool extreduce_extdataIsClean(const GRAPH *graph, const EXTDATA *extdata)
REDDATA *const reddata
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_RETCODE extreduce_contractionInit(SCIP *, int, int, CONTRACT **)
SCIP_Bool graph_csrdepo_isEmpty(const CSRDEPO *)
Definition: graph_util.c:851
This file implements extended reduction techniques for several Steiner problems.
static void postCleanSDs(MLDISTS *sds)
SCIP_Real *const pcSdToNode
SCIP_Bool extreduce_mldistsIsEmpty(const MLDISTS *)
SCIP_Bool extreduce_extPermaIsClean(const GRAPH *graph, const EXTPERMA *extperm)
PSEUDOANS * pseudoancestors
Definition: graphdefs.h:236
SCIP_Real * bottleneckDistNode
static SCIP_Bool extReddataHasBiasedSds(const REDDATA *reddata)
void graph_csrdepo_free(SCIP *, CSRDEPO **)
Definition: graph_util.c:637
#define NULL
Definition: lpi_spx1.cpp:155
void extreduce_mldistsLevelRemoveTop(MLDISTS *)
#define EQ(a, b)
Definition: portab.h:79
CONTRACT * contration
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RANDNUMGEN * randnumgen
unsigned char STP_Bool
Definition: portab.h:34
#define STP_EXT_MAXDFSDEPTH_GUARD
Definition: extreducedefs.h:39
CSRDEPO *const msts_comp
#define STP_EXTTREE_MAXNLEAVES_GUARD
Definition: extreducedefs.h:48
#define SCIP_Bool
Definition: def.h:84
SCIP_Bool *const sdeq_edgesIsForbidden
int *RESTRICT tail
Definition: graphdefs.h:223
SCIP_RETCODE graph_csrdepo_init(SCIP *, int, int, CSRDEPO **)
Definition: graph_util.c:590
CSRDEPO *const msts_levelbase
SCIP_RETCODE extreduce_extPermaAddMLdistsbiased(SCIP *scip, EXTPERMA *extpermanent)
int extreduce_getMaxTreeDepth(const GRAPH *, const EXTPERMA *)
SCIP_RETCODE extreduce_mldistsInit(SCIP *, int, int, int, int, SCIP_Bool, MLDISTS **)
SCIP_Real *const tree_bottleneckDistNode
PCDATA *const pcdata
SCIP_Bool graph_pc_isPc(const GRAPH *)
Portable definitions.
SCIP_Bool sdeq_hasForbiddenEdges
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
#define STP_EXTTREE_MAXNLEAVES
Definition: extreducedefs.h:47
SCIP_Bool extreduce_reddataIsClean(const GRAPH *graph, const REDDATA *reddata)
void reduce_dcmstFree(SCIP *, DCMST **)
Definition: reduce_util.c:1634
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
const int redcost_nlevels
#define STP_EXT_MAXGRAD
Definition: extreducedefs.h:42
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
EXTRED_MODE
Definition: reducedefs.h:71
void extreduce_mldistsFree(SCIP *, MLDISTS **)
#define SCIP_Real
Definition: def.h:177
void extreduce_pcdataClean(PCDATA *pcdata)
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
MLDISTS *const sds_vertical
MLDISTS *const sdsbias_vertical
void extreduce_extdataClean(EXTDATA *extdata)
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
MLDISTS *const sds_horizontal
int *const tree_deg
#define nnodes
Definition: gastrans.c:65
MLDISTS *const sdsbias_horizontal
SCIP_Real tree_cost
int graph_csrdepo_getNcsrs(const CSRDEPO *)
Definition: graph_util.c:741