Scippy

SCIP

Solving Constraint Integer Programs

stptest_extreduce.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 stptest_extreduce.c
17  * @brief tests for Steiner tree extended reductions
18  * @author Daniel Rehfeldt
19  *
20  * This file implements tests for Steiner problem extended reductions.
21  *
22  * A list of all interface methods can be found in stptest.h.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 //#define SCIP_DEBUG
29 #include <stdio.h>
30 #include <assert.h>
31 #include "stptest.h"
32 #include "portab.h"
33 #include "graph.h"
34 #include "reduce.h"
35 #include "extreduce.h"
36 
37 
38 #define STPTEST_EXT_MAXNCLOSENODES 64
39 
40 /** base method for extended edge reduction tests */
41 static
42 SCIP_RETCODE extCheckArc(
43  SCIP* scip, /**< SCIP data structure */
44  GRAPH* graph, /**< the graph */
45  REDCOST* redcostdata, /**< reduced cost data */
46  STP_Bool* edgedeleted, /**< marks for each edge whether deleted */
47  int edge, /**< the edge/arc to check */
48  int edgedelete, /**< delete the edge if possible? */
49  int nclosenodes, /**< max. number of close nodes to each node */
50  SCIP_Bool* deletable, /**< is the edge deletable? */
51  SCIP_Bool equality /**< allow equality for checks */
52 )
53 {
54  DISTDATA* distdata;
55  EXTPERMA* extpermanent;
56 
57  SCIP_CALL( graph_init_dcsr(scip, graph) );
58  SCIP_CALL( extreduce_distDataInit(scip, graph, nclosenodes, FALSE, FALSE, &distdata) );
59  SCIP_CALL( extreduce_extPermaInit(scip, extred_full, graph, edgedeleted, &extpermanent) );
60 
61  if( edgedelete >= 0 )
62  {
63  extreduce_edgeRemove(scip, edgedelete, graph, distdata, extpermanent);
64  assert(graph_isMarked(graph));
65  }
66 
67  extpermanent->redcostEqualAllow = equality;
68  extpermanent->distdata_default = distdata;
69 
70  /* actual test */
71  SCIP_CALL( extreduce_checkArc(scip, graph, redcostdata, edge, extpermanent, deletable) );
72 
73  /* clean up */
74  extreduce_extPermaFree(scip, &extpermanent);
75  extreduce_distDataFree(scip, graph, &distdata);
76  graph_free_dcsr(scip, graph);
77 
78  return SCIP_OKAY;
79 }
80 
81 
82 /** base method for extended edge reduction tests */
83 static
84 SCIP_RETCODE extCheckEdge(
85  SCIP* scip, /**< SCIP data structure */
86  GRAPH* graph, /**< the graph */
87  REDCOST* redcostdata, /**< reduced cost data */
88  STP_Bool* edgedeleted, /**< array to mark */
89  int edge, /**< edge to check */
90  SCIP_Bool* deletable, /**< can edge be deleted? */
91  SCIP_Bool allowEquality /**< allow equality for rule-out */
92 )
93 {
94  DISTDATA* distdata;
95  EXTPERMA* extpermanent;
96 
97  SCIP_CALL( graph_init_dcsr(scip, graph) );
98  SCIP_CALL( extreduce_distDataInit(scip, graph, STPTEST_EXT_MAXNCLOSENODES, FALSE, FALSE, &distdata) );
99  SCIP_CALL( extreduce_extPermaInit(scip, extred_full, graph, edgedeleted, &extpermanent) );
100 
101  extpermanent->redcostEqualAllow = allowEquality;
102  extpermanent->distdata_default = distdata;
103 
104  /* actual test */
105  SCIP_CALL( extreduce_checkEdge(scip, graph, redcostdata, edge, extpermanent, deletable) );
106 
107  /* clean up */
108  extreduce_extPermaFree(scip, &extpermanent);
109  extreduce_distDataFree(scip, graph, &distdata);
110  graph_free_dcsr(scip, graph);
111 
112  return SCIP_OKAY;
113 }
114 
115 
116 /** base method for extended edge reduction tests */
117 static
118 SCIP_RETCODE extCheckNode(
119  SCIP* scip, /**< SCIP data structure */
120  GRAPH* graph, /**< the graph */
121  REDCOST* redcostdata, /**< reduced cost data */
122  STP_Bool* edgedeleted, /**< array */
123  int node, /**< node to check */
124  SCIP_Bool* deletable, /**< pointer to mark whether node can be deleted */
125  SCIP_Bool allowEquality /**< allow equality? */
126 )
127 {
128  STAR* star;
129  DISTDATA* distdata;
130  EXTPERMA* extpermanent;
131 
132  SCIP_CALL( graph_init_dcsr(scip, graph) );
133  SCIP_CALL( extreduce_distDataInit(scip, graph, STPTEST_EXT_MAXNCLOSENODES, FALSE, FALSE, &distdata) );
134  SCIP_CALL( extreduce_extPermaInit(scip, extred_full, graph, edgedeleted, &extpermanent) );
135  SCIP_CALL( reduce_starInit(scip, graph->grad[node], &star) );
136 
137  extpermanent->redcostEqualAllow = allowEquality;
138  extpermanent->distdata_default = distdata;
139 
140  /* actual test */
141  SCIP_CALL( extreduce_checkNode(scip, graph, redcostdata, node, star, extpermanent, deletable) );
142 
143  /* clean up */
144  reduce_starFree(scip, &star);
145  extreduce_extPermaFree(scip, &extpermanent);
146  extreduce_distDataFree(scip, graph, &distdata);
147  graph_free_dcsr(scip, graph);
148 
149  return SCIP_OKAY;
150 }
151 
152 
153 
154 /** base method for extended edge reduction tests (with biased SDs) */
155 static
156 SCIP_RETCODE extDeleteNodes(
157  SCIP* scip, /**< SCIP data structure */
158  GRAPH* graph, /**< the graph */
159  REDCOST* redcostdata, /**< reduced cost data */
160  SCIP_Bool allowEquality /**< allow equality? */
161 )
162 {
163  DISTDATA* distdata;
164  EXTPERMA* extpermanent;
165  int ndeleted;
166 
167  SCIP_CALL( graph_init_dcsr(scip, graph) );
168  SCIP_CALL( extreduce_distDataInit(scip, graph, STPTEST_EXT_MAXNCLOSENODES, FALSE, FALSE, &distdata) );
169  SCIP_CALL( extreduce_extPermaInit(scip, extred_full, graph, NULL, &extpermanent) );
170 
171  assert(!extpermanent->distdata_default);
172 
173  extpermanent->distdata_default = distdata;
174  extpermanent->redcostdata = redcostdata;
175  extpermanent->redcostEqualAllow = allowEquality;
176 
177  SCIP_CALL( extreduce_pseudoDeleteNodes(scip, NULL, extpermanent, graph, NULL, &ndeleted) );
178 
179  /* clean up */
180  extreduce_distDataFree(scip, graph, &distdata);
181 
182  if( extpermanent->distdata_biased )
183  extreduce_distDataFree(scip, graph, &(extpermanent->distdata_biased));
184 
185  extreduce_extPermaFree(scip, &extpermanent);
186 
187  graph_free_dcsr(scip, graph);
188 
189  return SCIP_OKAY;
190 }
191 
192 /** initializes to default */
193 static
194 void extInitRedCostArrays(
195  const GRAPH* graph, /**< the graph */
196  REDCOST* redcostdata /**< reduced costs data */
197 )
198 {
199  const int nnodes = graph->knots;
200  const int nedges = graph->edges;
201  SCIP_Real* const rootdist = redcosts_getRootToNodeDistTop(redcostdata);
202  SCIP_Real* const redcost = redcosts_getEdgeCostsTop(redcostdata);
203  PATH* const termpaths3 = redcosts_getNodeToTermsPathsTop(redcostdata);
204  int* const vbase3 = redcosts_getNodeToTermsBasesTop(redcostdata);
205 
206  assert(redcosts_getNnodes(redcostdata) == nnodes);
207  assert(redcosts_getNedges(redcostdata) == nedges);
208 
209  for( int i = 0; i < nnodes; i++ )
210  rootdist[i] = 0.0;
211 
212  for( int i = 0; i < 3 * nnodes; i++ )
213  {
214  vbase3[i] = graph->source;
215  termpaths3[i].dist = 0.0;
216  termpaths3[i].edge = -1;
217  }
218 
219  for( int i = 0; i < nedges; i++ )
220  redcost[i] = 0.0;
221 }
222 
223 
224 /** initializes to default for PC */
225 static
226 void extInitRedCostArraysPc(
227  const GRAPH* graph, /**< the graph */
228  REDCOST* redcostdata /**< reduced costs data */
229 )
230 {
231  const int nnodes = graph->knots;
232  int* const vbase3 = redcosts_getNodeToTermsBasesTop(redcostdata);
233 
234  assert(graph_pc_isPc(graph));
235 
236  extInitRedCostArrays(graph, redcostdata);
237 
238  for( int i = 0; i < 3 * nnodes; i++ )
239  {
240  vbase3[i] = 0;
241  }
242 }
243 
244 #ifdef SCIP_DISABLED
245 /** initializes to default for PC */
246 static
247 void extInitRedCostArraysPcWithBase(
248  const GRAPH* graph, /**< the graph */
249  int base, /**< the base */
250  REDCOST* redcostdata /**< reduced costs data */
251 )
252 {
253  const int nnodes = graph->knots;
254  int* const vbase3 = redcosts_getNodeToTermsBasesTop(redcostdata);
255 
256  assert(graph_pc_isPc(graph));
257 
258  extInitRedCostArrays(graph, redcostdata);
259 
260  for( int i = 0; i < 3 * nnodes; i++ )
261  {
262  vbase3[i] = base;
263  }
264 }
265 #endif
266 
267 
268 static
269 SCIP_RETCODE testEdgeDeletion5_deprecated(
270  SCIP* scip, /**< SCIP data structure */
271  int variant /**< 1,2 */
272 )
273 {
274  GRAPH* graph;
275  const int nnodes = 85;
276  const int nedges = 88;
277  const int root = 0;
278  STP_Bool* edgedeleted = NULL;
279  SCIP_Real cutoff = 100.0;
280  int testedge;
281  SCIP_Bool deletable;
282  REDCOST* redcostdata;
283 
284  assert(variant == 1 || variant == 2);
285 
286  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
287 
288  graph_knot_add(graph, STP_TERM);
289 
290  /* also add dummy nodes to avoid full stack */
291  for( int i = 1; i < nnodes; i++ )
292  graph_knot_add(graph, -1);
293 
294  graph_knot_chg(graph, 6, STP_TERM);
295  graph_knot_chg(graph, 7, STP_TERM);
296  graph_knot_chg(graph, 8, STP_TERM);
297  graph_knot_chg(graph, 9, STP_TERM);
298 
299  graph->source = 0;
300 
301  graph_edge_addBi(scip, graph, 0, 1, 1.0);
302  graph_edge_addBi(scip, graph, 1, 2, 1.0);
303  graph_edge_addBi(scip, graph, 1, 3, 1.0);
304  graph_edge_addBi(scip, graph, 1, 4, 1.0);
305  graph_edge_addBi(scip, graph, 1, 5, 1.0);
306 
307  graph_edge_addBi(scip, graph, 2, 6, 1.0);
308  graph_edge_addBi(scip, graph, 3, 7, 1.0);
309  graph_edge_addBi(scip, graph, 4, 8, 1.0);
310  graph_edge_addBi(scip, graph, 5, 9, 1.0);
311 
312  graph_edge_addBi(scip, graph, 6, 10, 1.0);
313  graph_edge_addBi(scip, graph, 7, 10, 1.0);
314  graph_edge_addBi(scip, graph, 8, 10, 1.0);
315  graph_edge_addBi(scip, graph, 9, 10, 1.0);
316 
317  graph_edge_addBi(scip, graph, 0, 10, 0.9);
318 
319  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
320  extInitRedCostArrays(graph, redcostdata);
321 
322  for( int i = 0; i < graph->edges; i++ )
323  redcosts_getEdgeCostsTop(redcostdata)[i] = 1.0;
324 
325  testedge = 0;
326 
327  SCIP_CALL( stptest_graphSetUp(scip, graph) );
328 
329  if( variant == 1 )
330  {
331  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, testedge, -1, nnodes, &deletable, TRUE));
332  assert(deletable);
333  }
334  else
335  {
336  int edgedelete = -1;
337 
338  assert(variant == 2);
339 
340  for( int e = graph->outbeg[0]; e != EAT_LAST; e = graph->oeat[e] )
341  {
342  if( graph->head[e] == 10 )
343  edgedelete = e;
344  }
345 
346  assert(edgedelete >= 0);
347 
348  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, testedge, edgedelete, nnodes, &deletable, TRUE));
349  assert(!deletable);
350  }
351 
352  stptest_extreduceTearDown(scip, graph, &redcostdata);
353 
354  return SCIP_OKAY;
355 }
356 
357 
358 static
359 SCIP_RETCODE testEdgeDeletion4_deprecated(
360  SCIP* scip, /**< SCIP data structure */
361  int variant /**< 1,2,3 */
362 )
363 {
364  GRAPH* graph;
365  const int nnodes = 55;
366  const int nedges = 28;
367  const int root = 0;
368  STP_Bool* edgedeleted = NULL;
369  SCIP_Real cutoff = 100.0;
370  int edge;
371  SCIP_Bool deletable;
372  REDCOST* redcostdata;
373 
374  assert(scip);
375  assert(variant == 1 || variant == 2 || variant == 3);
376 
377  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
378 
379  graph_knot_add(graph, 0);
380 
381  /* also add dummy nodes to avoid full stack */
382  for( int i = 1; i < nnodes; i++ )
383  graph_knot_add(graph, -1);
384 
385  graph->source = 0;
386 
387  graph_edge_addBi(scip, graph, 0, 1, 1.0);
388  graph_edge_addBi(scip, graph, 1, 2, 1.0);
389  graph_edge_addBi(scip, graph, 1, 3, 1.0);
390  graph_edge_addBi(scip, graph, 2, 4, 1.0);
391  graph_edge_addBi(scip, graph, 3, 5, 1.0);
392  graph_edge_addBi(scip, graph, 4, 6, 1.0);
393  graph_edge_addBi(scip, graph, 5, 7, 1.0);
394 
395  graph_edge_addBi(scip, graph, 0, 6, 0.9);
396  graph_edge_addBi(scip, graph, 0, 7, 0.9);
397 
398  if( variant == 3 )
399  graph_edge_addBi(scip, graph, 7, 8, 0.9);
400 
401  graph_mark(graph);
402 
403  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
404  extInitRedCostArrays(graph, redcostdata);
405 
406  for( int i = 0; i < graph->edges; i++ )
407  redcosts_getEdgeCostsTop(redcostdata)[i] = 1.0;
408 
409  edge = 0;
410 
411  graph_knot_chg(graph, 4, 0);
412  graph_knot_chg(graph, 5, 0);
413 
414  SCIP_CALL( graph_initHistory(scip, graph) );
415  SCIP_CALL( graph_path_init(scip, graph) );
416 
417  if( variant == 1 )
418  {
419  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, -1, nnodes, &deletable, TRUE));
420 
421  assert(deletable);
422  }
423  else if( variant == 2 )
424  {
425  int edgedelete = -1;
426 
427  for( int e = graph->outbeg[0]; e != EAT_LAST; e = graph->oeat[e] )
428  if( graph->head[e] == 7 )
429  edgedelete = e;
430 
431  assert(edgedelete >= 0);
432 
433  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, edgedelete, nnodes, &deletable, TRUE));
434  assert(!deletable);
435  }
436  else
437  {
438  int edgedelete = -1;
439 
440  assert(variant == 3);
441 
442  for( int e = graph->outbeg[7]; e != EAT_LAST; e = graph->oeat[e] )
443  if( graph->head[e] == 8 )
444  edgedelete = e;
445 
446  assert(edgedelete >= 0);
447 
448  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, edgedelete, nnodes, &deletable, TRUE));
449  assert(deletable);
450  }
451 
452  stptest_extreduceTearDown(scip, graph, &redcostdata);
453 
454  return SCIP_OKAY;
455 }
456 
457 
458 static
459 SCIP_RETCODE testEdgeDeletion3_deprecated(
460  SCIP* scip, /**< SCIP data structure */
461  int variant /**< 1,2,3,4 */
462 )
463 {
464  GRAPH* graph;
465  const int nnodes = 55;
466  const int nedges = 28;
467  const int root = 0;
468  STP_Bool* edgedeleted = NULL;
469  SCIP_Real cutoff = 7.0;
470  int edge;
471  SCIP_Bool deletable;
472  REDCOST* redcostdata;
473 
474  assert(scip);
475 
476  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
477 
478  /* build graph */
479  graph_knot_add(graph, 0);
480 
481  /* also add dummy nodes to avoid full stack */
482  for( int i = 1; i < nnodes; i++ )
483  graph_knot_add(graph, -1);
484 
485  graph->source = 0;
486 
487  graph_edge_addBi(scip, graph, 0, 1, 1.0);
488  graph_edge_addBi(scip, graph, 1, 2, 1.0);
489  graph_edge_addBi(scip, graph, 2, 3, 1.0);
490  graph_edge_addBi(scip, graph, 2, 4, 1.0);
491  graph_edge_addBi(scip, graph, 3, 5, 1.0);
492  graph_edge_addBi(scip, graph, 3, 6, 1.0);
493  graph_edge_addBi(scip, graph, 4, 7, 1.0);
494 
495  graph_edge_addBi(scip, graph, 7, 9, 0.9);
496  graph_edge_addBi(scip, graph, 8, 0, 1.0);
497  graph_edge_addBi(scip, graph, 9, 0, 1.0);
498  graph_edge_addBi(scip, graph, 0, nnodes - 1, 1.0);
499 
500  graph_knot_chg(graph, nnodes - 1, 0); /* dummy node */
501  graph_mark(graph);
502 
503  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
504  extInitRedCostArrays(graph, redcostdata);
505 
506  redcosts_getNodeToTermsBasesTop(redcostdata)[5] = nnodes - 1;
507  redcosts_getNodeToTermsBasesTop(redcostdata)[6] = nnodes - 1;
508  redcosts_getNodeToTermsPathsTop(redcostdata)[5].dist = 3.0;
509  redcosts_getNodeToTermsPathsTop(redcostdata)[6].dist = 3.0;
510  redcosts_getNodeToTermsPathsTop(redcostdata)[5 + nnodes].dist = 3.0;
511  redcosts_getNodeToTermsPathsTop(redcostdata)[6 + nnodes].dist = 3.0;
512 
513  for( int i = 0; i < graph->edges; i++ )
514  redcosts_getEdgeCostsTop(redcostdata)[i] = 1.0;
515 
516  edge = 0;
517 
518  graph_knot_chg(graph, 7, 0);
519 
520  if( variant == 1 )
521  {
522  SCIP_CALL( graph_initHistory(scip, graph) );
523  SCIP_CALL( graph_path_init(scip, graph) );
524 
525  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, -1, nnodes, &deletable, TRUE));
526  assert(deletable);
527  }
528  else if( variant == 2 )
529  {
530  SCIP_CALL( graph_initHistory(scip, graph) );
531  SCIP_CALL( graph_path_init(scip, graph) );
532 
533  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, -1, nnodes, &deletable, FALSE));
534  assert(deletable);
535  }
536  else if( variant == 3 )
537  {
538  const int edge2 = 14;
539  assert(graph->tail[edge2] == 7 && graph->head[edge2] == 9);
540 
541  SCIP_CALL( graph_initHistory(scip, graph) );
542  SCIP_CALL( graph_path_init(scip, graph) );
543 
544  graph->cost[edge2] = 0.99;
545  graph->cost[flipedge(edge2)] = 0.99;
546  graph_knot_chg(graph, 4, 0);
547 
548  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, -1, nnodes, &deletable, TRUE));
549  }
550  else if( variant == 4 )
551  {
552  const int edgedelete = 14;
553  assert(graph->tail[edgedelete] == 7 && graph->head[edgedelete] == 9);
554 
555  SCIP_CALL( graph_initHistory(scip, graph) );
556  SCIP_CALL( graph_path_init(scip, graph) );
557 
558  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, edgedelete, nnodes, &deletable, TRUE));
559  assert(!deletable);
560  }
561 
562  stptest_extreduceTearDown(scip, graph, &redcostdata);
563 
564  return SCIP_OKAY;
565 }
566 
567 
568 static
569 SCIP_RETCODE testEdgeDeletion2_deprecated(
570  SCIP* scip, /**< SCIP data structure */
571  int variant /**< 1,2,3,4,5 */
572 )
573 {
574  GRAPH* graph;
575  const int nnodes = 55;
576  const int nedges = 28;
577  const int root = 0;
578 
579  STP_Bool* edgedeleted = NULL;
580  SCIP_Real cutoff = 100.0;
581  int edge;
582  SCIP_Bool deletable;
583  REDCOST* redcostdata;
584 
585  assert(scip);
586 
587  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
588 
589  graph_knot_add(graph, 0);
590 
591  /* also add dummy nodes to avoid full stack */
592  for( int i = 1; i < nnodes; i++ )
593  graph_knot_add(graph, -1);
594 
595  graph->source = 0;
596 
597  graph_edge_addBi(scip, graph, 0, 1, 1.0);
598  graph_edge_addBi(scip, graph, 1, 2, 1.0);
599  graph_edge_addBi(scip, graph, 1, 3, 1.0);
600  graph_edge_addBi(scip, graph, 1, 4, 1.0);
601 
602  graph_edge_addBi(scip, graph, 2, 5, 1.0);
603  graph_edge_addBi(scip, graph, 3, 6, 1.0);
604  graph_edge_addBi(scip, graph, 3, 7, 1.0);
605  graph_edge_addBi(scip, graph, 4, 8, 1.0);
606  graph_edge_addBi(scip, graph, 4, 9, 1.0);
607 
608  graph_edge_addBi(scip, graph, 5, 10, 1.0);
609  graph_edge_addBi(scip, graph, 10, 11, 1.0);
610  graph_edge_addBi(scip, graph, 11, 12, 1.0);
611 
612  graph_mark(graph);
613 
614  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
615  extInitRedCostArrays(graph, redcostdata);
616 
617  edge = 0;
618 
619  if( variant == 1 )
620  {
621  int pseudoancestor;
622  SCIP_CALL( graph_initHistory(scip, graph) );
623  SCIP_CALL( graph_path_init(scip, graph) );
624 
625  graph_addPseudoAncestor(graph, &pseudoancestor);
626  graph_addPseudoAncestor(graph, &pseudoancestor);
627  SCIP_CALL( graph_pseudoAncestors_addToEdge(scip, 0, 1, graph) );
628 
629  for( int e = graph->outbeg[10]; e != EAT_LAST; e = graph->oeat[e] )
630  {
631  if( graph->head[e] == 11 )
632  {
633  SCIP_CALL( graph_pseudoAncestors_addToEdge(scip, e, 1, graph) );
634  break;
635  }
636  }
637 
638  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, -1, nnodes, &deletable, FALSE));
639 
640  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
641  }
642 
643  stptest_extreduceTearDown(scip, graph, &redcostdata);
644 
645 
646  return SCIP_OKAY;
647 }
648 
649 
650 static
651 SCIP_RETCODE testEdgeDeletion1_deprecated(
652  SCIP* scip /**< SCIP data structure */
653 )
654 {
655  GRAPH* graph;
656  const int nnodes = 55;
657  const int nedges = 18;
658  const int root = 0;
659  STP_Bool* edgedeleted = NULL;
660  SCIP_Real cutoff = 0.0;
661  int edge;
662  SCIP_Bool deletable;
663  REDCOST* redcostdata;
664 
665  assert(scip);
666 
667  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
668 
669  graph_knot_add(graph, 0);
670 
671  /* also add dummy nodes to avoid full stack */
672  for( int i = 1; i < nnodes; i++ )
673  graph_knot_add(graph, -1);
674 
675  graph->source = 0;
676 
677  graph_edge_addBi(scip, graph, 0, 1, 1.0);
678  graph_edge_addBi(scip, graph, 1, 2, 1.0);
679  graph_edge_addBi(scip, graph, 1, 3, 1.0);
680  graph_edge_addBi(scip, graph, 1, 4, 1.0);
681 
682  graph_edge_addBi(scip, graph, 2, 5, 1.0);
683  graph_edge_addBi(scip, graph, 3, 6, 1.0);
684  graph_edge_addBi(scip, graph, 3, 7, 1.0);
685  graph_edge_addBi(scip, graph, 4, 8, 1.0);
686  graph_edge_addBi(scip, graph, 4, 9, 1.0);
687 
688  SCIP_CALL( graph_initHistory(scip, graph) );
689  SCIP_CALL( graph_path_init(scip, graph) );
690 
691  graph_mark(graph);
692 
693  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
694  extInitRedCostArrays(graph, redcostdata);
695 
696  edge = 0;
697 
698  SCIP_CALL(extCheckArc(scip, graph, redcostdata, edgedeleted, edge, -1, nnodes, &deletable, FALSE));
699 
700  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
701 
702  stptest_extreduceTearDown(scip, graph, &redcostdata);
703 
704  return SCIP_OKAY;
705 }
706 
707 
708 
709 /** tests that edge can be deleted by exploiting that two vertices have the
710  * same reduced costs closest terminal */
711 static
712 SCIP_RETCODE testEdgeDeletedByCommonRedCostsTargets(
713  SCIP* scip /**< SCIP data structure */
714 )
715 {
716  REDCOST* redcostdata;
717  GRAPH* graph;
718  const int nnodes = 15;
719  const int nedges = 64; /* just some upper bound */
720  const int root = 0;
721  SCIP_Real cutoff = 100.0;
722  STP_Bool* edgedeleted = NULL;
723  int testedge = 0;
724  SCIP_Bool deletable;
725  const int firstdummynode = 6;
726 
727  assert(scip);
728 
729  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
730 
731  /* build tree */
732  graph_knot_add(graph, STP_TERM); /* node 0 */
733  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
734  graph_knot_add(graph, STP_TERM); /* node 2 */
735  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
736  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
737  graph_knot_add(graph, STP_TERM); /* node 5 */
738 
739  /* add dummy nodes 6-14 */
740  for( int i = firstdummynode; i < nnodes; i++ )
741  graph_knot_add(graph, STP_TERM_NONE);
742 
743  graph->source = 0;
744 
745  graph_edge_addBi(scip, graph, 0, 1, 1.0);
746  graph_edge_addBi(scip, graph, 1, 2, 1.0);
747  graph_edge_addBi(scip, graph, 1, 3, 1.0);
748  graph_edge_addBi(scip, graph, 1, 4, 1.0);
749  graph_edge_addBi(scip, graph, 3, 5, 1.0);
750  graph_edge_addBi(scip, graph, 4, 5, 1.0);
751 
752  /* add shortcut edges */
753  graph_edge_addBi(scip, graph, 0, 2, 1.0);
754  graph_edge_addBi(scip, graph, 0, 3, 1.9);
755  graph_edge_addBi(scip, graph, 0, 4, 1.9);
756 
757  /* also add dummy edges to avoid extension */
758  for( int i = firstdummynode; i < nnodes; i++ )
759  {
760  graph_edge_addBi(scip, graph, 3, i, 1.0);
761  graph_edge_addBi(scip, graph, 4, i, 1.0);
762  }
763 
764  SCIP_CALL( stptest_graphSetUp(scip, graph) );
765  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
766  extInitRedCostArrays(graph, redcostdata);
767 
768  /* put 5 as first target for both nodes 3 and 4 and set the distance to the second target too high */
769  redcosts_getNodeToTermsBasesTop(redcostdata)[3] = 5;
770  redcosts_getNodeToTermsBasesTop(redcostdata)[4] = 5;
771  redcosts_getNodeToTermsPathsTop(redcostdata)[3 + nnodes].dist = cutoff + 0.1;
772  redcosts_getNodeToTermsPathsTop(redcostdata)[4 + nnodes].dist = cutoff + 0.1;
773 
774  SCIP_CALL(extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE));
775 
776  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
777 
778  stptest_extreduceTearDown(scip, graph, &redcostdata);
779 
780  return SCIP_OKAY;
781 }
782 
783 
784 
785 
786 /** tests that edge can be deleted by exploiting multi-level reduced costs */
787 static
788 SCIP_RETCODE testEdgeDeletedByMultiRedCosts(
789  SCIP* scip /**< SCIP data structure */
790 )
791 {
792  REDCOST* redcostdata;
793  GRAPH* graph;
794  const int nnodes = 15;
795  const int nedges = 80; /* just some upper bound */
796  SCIP_Real* redcosts = NULL;
797  int testedge = 0;
798  SCIP_Bool deletable;
799  const int firstdummynode = 7;
800 
801  assert(scip);
802 
803  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
804 
805  /* build tree */
806  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
807  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
808  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
809  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
810  graph_knot_add(graph, STP_TERM); /* node 4 */
811  graph_knot_add(graph, STP_TERM); /* node 5 */
812  graph_knot_add(graph, STP_TERM); /* node 6 */
813 
814  for( int i = firstdummynode; i < nnodes; i++ )
815  graph_knot_add(graph, STP_TERM_NONE);
816 
817  graph->source = 6;
818 
819  graph_edge_addBi(scip, graph, 0, 1, 1.0); /* 0 */
820  graph_edge_addBi(scip, graph, 1, 2, 1.0); /* 2 */
821  graph_edge_addBi(scip, graph, 1, 3, 1.0); /* 4 */
822  graph_edge_addBi(scip, graph, 2, 4, 2.0); /* 6 */
823  graph_edge_addBi(scip, graph, 3, 5, 2.0); /* 8 */
824 
825  graph_edge_addBi(scip, graph, 0, 4, 1.0); /* 10 */
826  graph_edge_addBi(scip, graph, 0, 6, 1.0); /* 12 */
827 
828 
829  /* add shortcut edges */
830  graph_edge_addBi(scip, graph, 0, 2, 1.9);
831  graph_edge_addBi(scip, graph, 0, 3, 1.9);
832 
833  /* also add dummy edges to avoid extension */
834  for( int i = firstdummynode; i < nnodes; i++ )
835  {
836  graph_edge_addBi(scip, graph, 0, i, 3.0);
837  graph_edge_addBi(scip, graph, 2, i, 3.0);
838  graph_edge_addBi(scip, graph, 3, i, 3.0);
839  }
840 
841  SCIP_CALL( stptest_graphSetUp(scip, graph) );
842 
843  {
844  RCPARAMS rcparams = { .cutoff = 7.0, .nLevels = 2, .nCloseTerms = 3,
845  .nnodes = graph->knots, .nedges = graph->edges, .redCostRoot = graph->source };
846  SCIP_CALL( redcosts_initFromParams(scip, &rcparams, &redcostdata) );
847  }
848 
849  /* 1st level */
850  redcosts = redcosts_getEdgeCostsTop(redcostdata);
851  for( int i = 0; i < graph->edges; i++ )
852  redcosts[i] = graph->cost[i];
853 
854  redcosts[0] = 0;
855 
856  SCIP_CALL( redcosts_initializeDistancesTop(scip, graph, redcostdata) );
857 
858  /* 2nd level */
859  redcosts_addLevel(redcostdata);
860  redcosts = redcosts_getEdgeCostsTop(redcostdata);
861  for( int i = 0; i < graph->edges; i++ )
862  redcosts[i] = graph->cost[i];
863 
864  redcosts_setCutoffTop(6.5, redcostdata);
865  redcosts_setRootTop(4, redcostdata);
866  SCIP_CALL( redcosts_initializeDistancesTop(scip, graph, redcostdata) );
867 
868  /* call actual reduction method */
869  SCIP_CALL(extCheckEdge(scip, graph, redcostdata, NULL, testedge, &deletable, FALSE));
870 
871  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
872 
873  stptest_extreduceTearDown(scip, graph, &redcostdata);
874 
875  return SCIP_OKAY;
876 }
877 
878 /** tests that edge can be deleted by using SD MST argument */
879 static
880 SCIP_RETCODE testEdgeDeletedByMst1(
881  SCIP* scip /**< SCIP data structure */
882 )
883 {
884  REDCOST* redcostdata;
885  GRAPH* graph;
886  const int nnodes = 5;
887  const int nedges = 16;
888  const int root = 0;
889  SCIP_Real cutoff = 100.0;
890  STP_Bool* edgedeleted = NULL;
891  int testedge = 0;
892  SCIP_Bool deletable;
893 
894  assert(scip);
895 
896  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
897 
898  /* build tree */
899  graph_knot_add(graph, STP_TERM); /* node 0 */
900  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
901  graph_knot_add(graph, STP_TERM); /* node 2 */
902  graph_knot_add(graph, STP_TERM); /* node 3 */
903  graph_knot_add(graph, STP_TERM); /* node 4 */
904 
905  graph->source = 0;
906 
907  graph_edge_addBi(scip, graph, 0, 1, 1.0);
908  graph_edge_addBi(scip, graph, 1, 2, 1.0);
909  graph_edge_addBi(scip, graph, 1, 3, 1.0);
910  graph_edge_addBi(scip, graph, 1, 4, 1.0);
911 
912  /* add shortcut edges */
913  graph_edge_addBi(scip, graph, 0, 2, 1.4);
914  graph_edge_addBi(scip, graph, 0, 3, 1.4);
915  graph_edge_addBi(scip, graph, 0, 4, 1.4);
916  graph_edge_addBi(scip, graph, 2, 3, 1.1);
917 
918  SCIP_CALL( stptest_graphSetUp(scip, graph) );
919  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
920  extInitRedCostArrays(graph, redcostdata);
921 
922  SCIP_CALL(extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE));
923 
924  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
925 
926  stptest_extreduceTearDown(scip, graph, &redcostdata);
927 
928  return SCIP_OKAY;
929 }
930 
931 
932 /** tests that edge can be deleted by using SD MST argument */
933 static
934 SCIP_RETCODE testEdgeDeletedByMst2(
935  SCIP* scip /**< SCIP data structure */
936 )
937 {
938  REDCOST* redcostdata;
939  GRAPH* graph;
940  const int nnodes = 8;
941  const int nedges = 22;
942  const int root = 0;
943  SCIP_Real cutoff = 100.0;
944  STP_Bool* edgedeleted = NULL;
945  int testedge = 0;
946  SCIP_Bool deletable;
947 
948  assert(scip);
949 
950  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
951 
952  /* build tree */
953  graph_knot_add(graph, STP_TERM); /* node 0 */
954  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
955  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
956  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
957  graph_knot_add(graph, STP_TERM); /* node 4 */
958  graph_knot_add(graph, STP_TERM); /* node 5 */
959  graph_knot_add(graph, STP_TERM); /* node 6 */
960  graph_knot_add(graph, STP_TERM); /* node 7 */
961 
962  graph->source = 0;
963 
964  graph_edge_addBi(scip, graph, 0, 1, 1.0);
965  graph_edge_addBi(scip, graph, 1, 2, 1.0);
966  graph_edge_addBi(scip, graph, 1, 3, 1.2);
967  graph_edge_addBi(scip, graph, 2, 4, 1.0);
968  graph_edge_addBi(scip, graph, 2, 5, 1.0);
969  graph_edge_addBi(scip, graph, 3, 6, 1.0);
970  graph_edge_addBi(scip, graph, 3, 7, 1.0);
971 
972  /* add shortcut edges */
973  graph_edge_addBi(scip, graph, 0, 3, 1.5);
974  graph_edge_addBi(scip, graph, 0, 4, 2.5);
975  graph_edge_addBi(scip, graph, 0, 5, 2.5);
976  graph_edge_addBi(scip, graph, 4, 5, 1.1);
977 
978  SCIP_CALL( stptest_graphSetUp(scip, graph) );
979  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
980  extInitRedCostArrays(graph, redcostdata);
981 
982  SCIP_CALL( extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE) );
983 
984  STPTEST_ASSERT_MSG(deletable, "edge was deleted \n");
985 
986  stptest_extreduceTearDown(scip, graph, &redcostdata);
987 
988  return SCIP_OKAY;
989 }
990 
991 
992 
993 /** tests that edge can be deleted by using equality bottlneck test*/
994 static
995 SCIP_RETCODE testEdgeDeletedByEqBottleneck(
996  SCIP* scip /**< SCIP data structure */
997 )
998 {
999  REDCOST* redcostdata;
1000  GRAPH* graph;
1001  const int nnodes = 4;
1002  const int nedges = 12;
1003  const int root = 0;
1004  SCIP_Real cutoff = 100.0;
1005  STP_Bool* edgedeleted = NULL;
1006  int testedge = 0;
1007  SCIP_Bool deletable;
1008 
1009  assert(scip);
1010 
1011  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1012 
1013  /* build tree */
1014  graph_knot_add(graph, STP_TERM); /* node 0 */
1015  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1016  graph_knot_add(graph, STP_TERM); /* node 2 */
1017  graph_knot_add(graph, STP_TERM); /* node 3 */
1018 
1019  graph->source = 0;
1020 
1021  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1022  graph_edge_addBi(scip, graph, 1, 2, 1.0);
1023  graph_edge_addBi(scip, graph, 1, 3, 1.0);
1024 
1025  /* add shortcut edges */
1026  graph_edge_addBi(scip, graph, 0, 2, 1.9);
1027  graph_edge_addBi(scip, graph, 0, 3, 1.9);
1028  graph_edge_addBi(scip, graph, 2, 3, 1.0);
1029 
1030  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1031  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1032  extInitRedCostArrays(graph, redcostdata);
1033 
1034  SCIP_CALL(extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE));
1035 
1036  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
1037 
1038  stptest_extreduceTearDown(scip, graph, &redcostdata);
1039 
1040  return SCIP_OKAY;
1041 }
1042 
1043 
1044 /** tests that edge cannot be deleted */
1045 static
1046 SCIP_RETCODE testEdgeNotDeleted1(
1047  SCIP* scip /**< SCIP data structure */
1048 )
1049 {
1050  REDCOST* redcostdata;
1051  GRAPH* graph;
1052  const int nnodes = 8;
1053  const int nedges = 22;
1054  const int root = 0;
1055  SCIP_Real cutoff = 100.0;
1056  STP_Bool* edgedeleted = NULL;
1057  int testedge = 0;
1058  SCIP_Bool deletable;
1059 
1060  assert(scip);
1061 
1062  SCIP_CALL( redcosts_init(scip, nnodes, nedges, cutoff, root, &redcostdata) );
1063  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1064 
1065  /* build tree */
1066  graph_knot_add(graph, STP_TERM); /* node 0 */
1067  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1068  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1069  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
1070  graph_knot_add(graph, STP_TERM); /* node 4 */
1071  graph_knot_add(graph, STP_TERM); /* node 5 */
1072  graph_knot_add(graph, STP_TERM); /* node 6 */
1073  graph_knot_add(graph, STP_TERM); /* node 7 */
1074 
1075  graph->source = 0;
1076 
1077  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1078  graph_edge_addBi(scip, graph, 1, 2, 1.0);
1079  graph_edge_addBi(scip, graph, 1, 3, 1.0);
1080  graph_edge_addBi(scip, graph, 2, 4, 1.0);
1081  graph_edge_addBi(scip, graph, 2, 5, 1.0);
1082  graph_edge_addBi(scip, graph, 3, 6, 1.0);
1083  graph_edge_addBi(scip, graph, 3, 7, 1.0);
1084 
1085  /* add shortcut edges */
1086  graph_edge_addBi(scip, graph, 0, 3, 1.5);
1087  graph_edge_addBi(scip, graph, 0, 4, 2.5);
1088  graph_edge_addBi(scip, graph, 0, 5, 2.5);
1089  graph_edge_addBi(scip, graph, 4, 5, 1.1);
1090 
1091  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1092  extInitRedCostArrays(graph, redcostdata);
1093 
1094  SCIP_CALL( extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE) );
1095 
1096  STPTEST_ASSERT_MSG(!deletable, "edge was deleted \n");
1097 
1098  stptest_extreduceTearDown(scip, graph, &redcostdata);
1099 
1100  return SCIP_OKAY;
1101 }
1102 
1103 
1104 /** tests that edge can be deleted (with equality argument) */
1105 static
1106 SCIP_RETCODE testEdgeDeletedByEqBottleneck2(
1107  SCIP* scip /**< SCIP data structure */
1108 )
1109 {
1110  REDCOST* redcostdata;
1111  GRAPH* graph;
1112  const int nnodes = 5;
1113  const int nedges = 12;
1114  const int root = 0;
1115  SCIP_Real cutoff = 100.0;
1116  STP_Bool* edgedeleted = NULL;
1117  int testedge = 0;
1118  SCIP_Bool deletable;
1119 
1120  assert(scip);
1121 
1122  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1123 
1124  /* build tree */
1125  graph_knot_add(graph, STP_TERM); /* node 0 */
1126  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1127  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1128  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
1129  graph_knot_add(graph, STP_TERM); /* node 4 */
1130 
1131  graph->source = 0;
1132 
1133  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1134  graph_edge_addBi(scip, graph, 1, 2, 1.0);
1135  graph_edge_addBi(scip, graph, 1, 3, 1.0);
1136  graph_edge_addBi(scip, graph, 2, 4, 1.0);
1137  graph_edge_addBi(scip, graph, 3, 4, 1.0);
1138 
1139  graph_edge_addBi(scip, graph, 0, 4, 3.0);
1140 
1141 
1142  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1143  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1144  extInitRedCostArrays(graph, redcostdata);
1145 
1146  SCIP_CALL( extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE) );
1147 
1148  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
1149 
1150  stptest_extreduceTearDown(scip, graph, &redcostdata);
1151 
1152  return SCIP_OKAY;
1153 }
1154 
1155 
1156 
1157 /** tests that edge can be deleted by extended SPG rule-out */
1158 static
1159 SCIP_RETCODE testEdgeDeletedBy3LeafSpg(
1160  SCIP* scip /**< SCIP data structure */
1161 )
1162 {
1163  REDCOST* redcostdata;
1164  GRAPH* graph;
1165  const int nnodes = 5;
1166  const int nedges = 12;
1167  const int root = 0;
1168  SCIP_Real cutoff = 100.0;
1169  STP_Bool* edgedeleted = NULL;
1170  int testedge = 0;
1171  SCIP_Bool deletable;
1172 
1173  assert(scip);
1174 
1175  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1176 
1177  /* build tree */
1178  graph_knot_add(graph, STP_TERM); /* node 0 */
1179  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1180  graph_knot_add(graph, STP_TERM); /* node 2 */
1181  graph_knot_add(graph, STP_TERM); /* node 3 */
1182  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
1183 
1184  graph->source = 0;
1185 
1186  graph_edge_addBi(scip, graph, 0, 1, 1.1);
1187  graph_edge_addBi(scip, graph, 1, 2, 1.1);
1188  graph_edge_addBi(scip, graph, 1, 3, 1.1);
1189 
1190  graph_edge_addBi(scip, graph, 0, 4, 1.1);
1191  graph_edge_addBi(scip, graph, 2, 4, 1.0);
1192  graph_edge_addBi(scip, graph, 3, 4, 1.0);
1193 
1194 
1195  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1196  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1197  extInitRedCostArrays(graph, redcostdata);
1198 
1199  SCIP_CALL( extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE) );
1200 
1201  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
1202 
1203  stptest_extreduceTearDown(scip, graph, &redcostdata);
1204 
1205  return SCIP_OKAY;
1206 }
1207 
1208 
1209 /** tests that edge can be deleted by reduced costs argument */
1210 static
1211 SCIP_RETCODE testNode3PseudoDeletedByRedCosts1(
1212  SCIP* scip /**< SCIP data structure */
1213 )
1214 {
1215  REDCOST* redcostdata;
1216  GRAPH* graph;
1217  const int nnodes = 6;
1218  const int nedges = 14;
1219  const int root = 0;
1220  SCIP_Real cutoff = 5.9;
1221  STP_Bool* edgedeleted = NULL;
1222  int testnode = 0;
1223  SCIP_Bool deletable;
1224  SCIP_Real* redEdgeCosts;
1225 
1226  assert(scip);
1227 
1228  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1229 
1230  /* build tree */
1231  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1232  graph_knot_add(graph, STP_TERM); /* node 1 */
1233  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1234  graph_knot_add(graph, STP_TERM); /* node 3 */
1235  graph_knot_add(graph, STP_TERM); /* node 4 */
1236  graph_knot_add(graph, STP_TERM); /* node 5 */
1237 
1238  graph->source = 1;
1239 
1240  graph_edge_addBi(scip, graph, 0, 1, 1.0); /* 0 */
1241  graph_edge_addBi(scip, graph, 0, 2, 1.0); /* 2 */
1242  graph_edge_addBi(scip, graph, 0, 3, 1.0); /* 4 */
1243  graph_edge_addBi(scip, graph, 1, 4, 1.0); /* 6 */
1244  graph_edge_addBi(scip, graph, 2, 4, 1.0); /* 8 */
1245  graph_edge_addBi(scip, graph, 2, 5, 1.0); /* 10 */
1246  graph_edge_addBi(scip, graph, 3, 5, 2.2); /* 12 */
1247 
1248  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1249  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1250  extInitRedCostArrays(graph, redcostdata);
1251 
1252  redEdgeCosts = redcosts_getEdgeCostsTop(redcostdata);
1253 
1254  redEdgeCosts[2] = 3.0;
1255  redEdgeCosts[3] = 3.0;
1256  redEdgeCosts[10] = 3.0;
1257  redEdgeCosts[11] = 3.0;
1258 
1259  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
1260 
1261  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
1262 
1263  stptest_extreduceTearDown(scip, graph, &redcostdata);
1264 
1265  return SCIP_OKAY;
1266 }
1267 
1268 
1269 
1270 /** tests that node can be deleted */
1271 static
1272 SCIP_RETCODE testNode3PseudoDeletedByContraction(
1273  SCIP* scip /**< SCIP data structure */
1274 )
1275 {
1276  REDCOST* redcostdata;
1277  GRAPH* graph;
1278  const int nnodes = 9;
1279  const int nedges = 22;
1280  const int root = 0;
1281  SCIP_Real cutoff = 100.0;
1282  STP_Bool* edgedeleted = NULL;
1283  int testnode = 0;
1284  SCIP_Bool deletable;
1285 
1286  assert(scip);
1287 
1288  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1289 
1290  /* build tree */
1291  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1292  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1293  graph_knot_add(graph, STP_TERM); /* node 2 */
1294  graph_knot_add(graph, STP_TERM); /* node 3 */
1295  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
1296  graph_knot_add(graph, STP_TERM_NONE); /* node 5 */
1297  graph_knot_add(graph, STP_TERM_NONE); /* node 6 */
1298  graph_knot_add(graph, STP_TERM); /* node 7 */
1299  graph_knot_add(graph, STP_TERM); /* node 8 */
1300 
1301 
1302  graph->source = 7;
1303 
1304  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1305  graph_edge_addBi(scip, graph, 0, 2, 1.0);
1306  graph_edge_addBi(scip, graph, 0, 3, 1.0);
1307  graph_edge_addBi(scip, graph, 1, 4, 0.5);
1308  graph_edge_addBi(scip, graph, 4, 5, 1.0);
1309  graph_edge_addBi(scip, graph, 4, 6, 1.0);
1310  graph_edge_addBi(scip, graph, 5, 7, 1.0);
1311  graph_edge_addBi(scip, graph, 6, 8, 1.0);
1312 
1313  graph_edge_addBi(scip, graph, 1, 2, 1.05);
1314  graph_edge_addBi(scip, graph, 3, 5, 1.9);
1315  graph_edge_addBi(scip, graph, 3, 6, 1.9);
1316 
1317 
1318  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1319  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1320  extInitRedCostArrays(graph, redcostdata);
1321 
1322  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
1323 
1324  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
1325 
1326  stptest_extreduceTearDown(scip, graph, &redcostdata);
1327 
1328  return SCIP_OKAY;
1329 }
1330 
1331 
1332 /** tests that node can be pseudo-deleted */
1333 static
1334 SCIP_RETCODE testNode3PseudoDeletedBySdBiasedSimple(
1335  SCIP* scip /**< SCIP data structure */
1336 )
1337 {
1338  DISTDATA* distdata_default;
1339  DISTDATA* distdata_biased;
1340  REDCOST* redcostdata;
1341  GRAPH* graph;
1342  const int nnodes = 7;
1343  const int nedges = 16;
1344  const int root = 0;
1345  SCIP_Real cutoff = 100.0;
1346  int testnode = 0;
1347  SCIP_Bool deletable = FALSE;
1348 
1349  assert(scip);
1350 
1351  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1352 
1353  /* build tree */
1354  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1355  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1356  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1357  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
1358  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
1359  graph_knot_add(graph, STP_TERM); /* node 5 */
1360  graph_knot_add(graph, STP_TERM); /* node 6 */
1361 
1362 
1363  graph->source = 5;
1364 
1365  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1366  graph_edge_addBi(scip, graph, 0, 2, 1.0);
1367  graph_edge_addBi(scip, graph, 0, 3, 1.0);
1368  graph_edge_addBi(scip, graph, 2, 4, 1.0);
1369  graph_edge_addBi(scip, graph, 2, 5, 2.0);
1370  graph_edge_addBi(scip, graph, 3, 4, 1.0);
1371  graph_edge_addBi(scip, graph, 4, 5, 1.0);
1372 
1373  /* dummy */
1374  graph_edge_addBi(scip, graph, 5, 6, 12.0);
1375 
1376 
1377  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1378  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1379  extInitRedCostArrays(graph, redcostdata);
1380 
1381  SCIP_CALL( graph_init_dcsr(scip, graph) );
1382  SCIP_CALL( extreduce_distDataInit(scip, graph, STPTEST_EXT_MAXNCLOSENODES, FALSE, FALSE, &distdata_default) );
1383  SCIP_CALL( extreduce_distDataInit(scip, graph, STPTEST_EXT_MAXNCLOSENODES, TRUE, TRUE, &distdata_biased) );
1384 
1385  SCIP_CALL( extreduce_mstbiasedCheck3NodeSimple(scip, graph, testnode, distdata_default, distdata_biased, &deletable) );
1386 
1387  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
1388 
1389  extreduce_distDataFree(scip, graph, &distdata_biased);
1390  extreduce_distDataFree(scip, graph, &distdata_default);
1391  graph_free_dcsr(scip, graph);
1392  stptest_extreduceTearDown(scip, graph, &redcostdata);
1393 
1394  return SCIP_OKAY;
1395 }
1396 
1397 
1398 /** tests that node can be pseudo-deleted */
1399 static
1400 SCIP_RETCODE testNode3PseudoDeletedBySdBiased(
1401  SCIP* scip /**< SCIP data structure */
1402 )
1403 {
1404  REDCOST* redcostdata;
1405  GRAPH* graph;
1406  const int nnodes = 10;
1407  const int nedges = 22;
1408  const int root = 0;
1409  SCIP_Real cutoff = 100.0;
1410  int testnode = 0;
1411 
1412  assert(scip);
1413 
1414  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1415 
1416  /* build tree */
1417  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1418  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1419  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1420  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
1421  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
1422  graph_knot_add(graph, STP_TERM); /* node 5 */
1423  graph_knot_add(graph, STP_TERM); /* node 6 */
1424  graph_knot_add(graph, STP_TERM_NONE); /* node 7 */
1425  graph_knot_add(graph, STP_TERM); /* node 8 */
1426  graph_knot_add(graph, STP_TERM); /* node 9 */
1427 
1428  graph->source = 5;
1429 
1430  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1431  graph_edge_addBi(scip, graph, 0, 7, 1.0);
1432  graph_edge_addBi(scip, graph, 7, 2, 1.0);
1433  graph_edge_addBi(scip, graph, 0, 3, 1.0);
1434  graph_edge_addBi(scip, graph, 2, 4, 1.5);
1435  graph_edge_addBi(scip, graph, 3, 4, 1.5);
1436  graph_edge_addBi(scip, graph, 4, 5, 1.0);
1437 
1438  /* dummy */
1439  graph_edge_addBi(scip, graph, 5, 6, 12.0);
1440  graph_edge_addBi(scip, graph, 1, 8, 1.0);
1441  graph_edge_addBi(scip, graph, 3, 9, 1.0);
1442  graph_edge_addBi(scip, graph, 2, 6, 2.1);
1443 
1444 
1445  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1446  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1447  extInitRedCostArrays(graph, redcostdata);
1448 
1449  SCIP_CALL( extDeleteNodes(scip, graph, redcostdata, TRUE) );
1450 
1451  STPTEST_ASSERT_MSG(graph->grad[testnode] == 0, "node was not deleted! \n");
1452 
1453  stptest_extreduceTearDown(scip, graph, &redcostdata);
1454 
1455  return SCIP_OKAY;
1456 }
1457 
1458 
1459 /** tests that node can be deleted */
1460 static
1461 SCIP_RETCODE testNode3PseudoDeletedBySd1(
1462  SCIP* scip /**< SCIP data structure */
1463 )
1464 {
1465  REDCOST* redcostdata;
1466  GRAPH* graph;
1467  const int nnodes = 6;
1468  const int nedges = 14;
1469  const int root = 0;
1470  SCIP_Real cutoff = 100.0;
1471  STP_Bool* edgedeleted = NULL;
1472  int testnode = 0;
1473  SCIP_Bool deletable;
1474 
1475  assert(scip);
1476 
1477  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1478 
1479  /* build tree */
1480  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1481  graph_knot_add(graph, STP_TERM); /* node 1 */
1482  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1483  graph_knot_add(graph, STP_TERM); /* node 3 */
1484  graph_knot_add(graph, STP_TERM); /* node 4 */
1485  graph_knot_add(graph, STP_TERM); /* node 5 */
1486 
1487  graph->source = 1;
1488 
1489  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1490  graph_edge_addBi(scip, graph, 0, 2, 1.0);
1491  graph_edge_addBi(scip, graph, 0, 3, 1.0);
1492  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1493  graph_edge_addBi(scip, graph, 2, 4, 1.0);
1494  graph_edge_addBi(scip, graph, 2, 5, 1.0);
1495  graph_edge_addBi(scip, graph, 3, 5, 1.0);
1496 
1497  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1498  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1499  extInitRedCostArrays(graph, redcostdata);
1500 
1501  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
1502 
1503  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
1504 
1505  stptest_extreduceTearDown(scip, graph, &redcostdata);
1506 
1507  return SCIP_OKAY;
1508 }
1509 
1510 
1511 
1512 /** tests that node can be deleted */
1513 static
1514 SCIP_RETCODE testNode3PseudoDeletedBySd2(
1515  SCIP* scip /**< SCIP data structure */
1516 )
1517 {
1518  REDCOST* redcostdata;
1519  GRAPH* graph;
1520  const int nnodes = 6;
1521  const int nedges = 14;
1522  const int root = 0;
1523  SCIP_Real cutoff = 100.0;
1524  STP_Bool* edgedeleted = NULL;
1525  int testnode = 0;
1526  SCIP_Bool deletable;
1527 
1528  assert(scip);
1529 
1530  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1531 
1532  /* build tree */
1533  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1534  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1535  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1536  graph_knot_add(graph, STP_TERM); /* node 3 */
1537  graph_knot_add(graph, STP_TERM); /* node 4 */
1538  graph_knot_add(graph, STP_TERM); /* node 5 */
1539 
1540  graph->source = 3;
1541 
1542  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1543  graph_edge_addBi(scip, graph, 0, 2, 1.0);
1544  graph_edge_addBi(scip, graph, 0, 3, 1.0);
1545  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1546  graph_edge_addBi(scip, graph, 1, 5, 1.0);
1547  graph_edge_addBi(scip, graph, 2, 4, 1.0);
1548  graph_edge_addBi(scip, graph, 3, 4, 1.5);
1549 
1550  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1551  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1552  extInitRedCostArrays(graph, redcostdata);
1553 
1554  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
1555 
1556  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
1557 
1558  stptest_extreduceTearDown(scip, graph, &redcostdata);
1559 
1560  return SCIP_OKAY;
1561 }
1562 
1563 /** tests that node can be deleted */
1564 static
1565 SCIP_RETCODE testNode3PseudoDeletedBySd3(
1566  SCIP* scip /**< SCIP data structure */
1567 )
1568 {
1569  REDCOST* redcostdata;
1570  GRAPH* graph;
1571  const int nnodes = 8;
1572  const int nedges = 20;
1573  const int root = 7;
1574  SCIP_Real cutoff = 100.0;
1575  STP_Bool* edgedeleted = NULL;
1576  int testnode = 0;
1577  SCIP_Bool deletable;
1578 
1579  assert(scip);
1580 
1581  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1582 
1583  /* build tree */
1584  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1585  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1586  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1587  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
1588  graph_knot_add(graph, STP_TERM); /* node 4 */
1589  graph_knot_add(graph, STP_TERM_NONE); /* node 5 */
1590  graph_knot_add(graph, STP_TERM); /* node 6 */
1591  graph_knot_add(graph, STP_TERM); /* node 7 */
1592 
1593  graph->source = 7;
1594 
1595  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1596  graph_edge_addBi(scip, graph, 0, 2, 1.0);
1597  graph_edge_addBi(scip, graph, 0, 3, 1.0);
1598  graph_edge_addBi(scip, graph, 1, 3, 1.5);
1599  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1600  graph_edge_addBi(scip, graph, 1, 6, 2.0);
1601  graph_edge_addBi(scip, graph, 2, 5, 2.0);
1602  graph_edge_addBi(scip, graph, 2, 6, 1.0);
1603  graph_edge_addBi(scip, graph, 3, 7, 1.0);
1604  graph_edge_addBi(scip, graph, 4, 5, 1.0);
1605 
1606  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1607  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1608  extInitRedCostArrays(graph, redcostdata);
1609 
1610  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
1611 
1612  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
1613 
1614  stptest_extreduceTearDown(scip, graph, &redcostdata);
1615 
1616  return SCIP_OKAY;
1617 }
1618 
1619 
1620 
1621 /** tests that node can be deleted */
1622 static
1623 SCIP_RETCODE testNode4PseudoDeletedBySd1(
1624  SCIP* scip /**< SCIP data structure */
1625 )
1626 {
1627  REDCOST* redcostdata;
1628  GRAPH* graph;
1629  const int nnodes = 7;
1630  const int nedges = 18;
1631  const int root = 0;
1632  SCIP_Real cutoff = 100.0;
1633  STP_Bool* edgedeleted = NULL;
1634  int testnode = 0;
1635  SCIP_Bool deletable;
1636 
1637  assert(scip);
1638 
1639  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1640 
1641  /* build tree */
1642  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1643  graph_knot_add(graph, STP_TERM); /* node 1 */
1644  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1645  graph_knot_add(graph, STP_TERM); /* node 3 */
1646  graph_knot_add(graph, STP_TERM); /* node 4 */
1647  graph_knot_add(graph, STP_TERM); /* node 5 */
1648  graph_knot_add(graph, STP_TERM); /* node 6 */
1649 
1650  graph->source = 1;
1651 
1652  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1653  graph_edge_addBi(scip, graph, 0, 2, 1.5);
1654  graph_edge_addBi(scip, graph, 0, 3, 2.0);
1655  graph_edge_addBi(scip, graph, 0, 4, 2.0);
1656  graph_edge_addBi(scip, graph, 2, 5, 2.0);
1657  graph_edge_addBi(scip, graph, 2, 6, 2.0);
1658  graph_edge_addBi(scip, graph, 3, 4, 1.0);
1659  graph_edge_addBi(scip, graph, 5, 6, 1.0);
1660  graph_edge_addBi(scip, graph, 6, 3, 1.0);
1661 
1662  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1663  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1664  extInitRedCostArrays(graph, redcostdata);
1665 
1666  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
1667 
1668  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
1669 
1670  stptest_extreduceTearDown(scip, graph, &redcostdata);
1671 
1672  return SCIP_OKAY;
1673 }
1674 
1675 
1676 
1677 
1678 /** tests that node cannot be deleted */
1679 static
1680 SCIP_RETCODE testNode4PseudoNotDeletedBySd1(
1681  SCIP* scip /**< SCIP data structure */
1682 )
1683 {
1684  REDCOST* redcostdata;
1685  GRAPH* graph;
1686  const int nnodes = 7;
1687  const int nedges = 16;
1688  const int root = 0;
1689  SCIP_Real cutoff = 100.0;
1690  STP_Bool* edgedeleted = NULL;
1691  int testnode = 0;
1692  SCIP_Bool deletable;
1693 
1694  assert(scip);
1695 
1696  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1697 
1698  /* build tree */
1699  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1700  graph_knot_add(graph, STP_TERM); /* node 1 */
1701  graph_knot_add(graph, STP_TERM_NONE); /* node 2 */
1702  graph_knot_add(graph, STP_TERM); /* node 3 */
1703  graph_knot_add(graph, STP_TERM); /* node 4 */
1704  graph_knot_add(graph, STP_TERM); /* node 5 */
1705  graph_knot_add(graph, STP_TERM); /* node 6 */
1706 
1707  graph->source = 1;
1708 
1709  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1710  graph_edge_addBi(scip, graph, 0, 2, 1.5);
1711  graph_edge_addBi(scip, graph, 0, 3, 2.0);
1712  graph_edge_addBi(scip, graph, 0, 4, 2.0);
1713  graph_edge_addBi(scip, graph, 2, 5, 2.0);
1714  graph_edge_addBi(scip, graph, 2, 6, 2.0);
1715  graph_edge_addBi(scip, graph, 5, 6, 1.0);
1716  graph_edge_addBi(scip, graph, 6, 3, 1.0);
1717 
1718  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1719  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1720  extInitRedCostArrays(graph, redcostdata);
1721 
1722  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
1723 
1724  STPTEST_ASSERT_MSG(!deletable, "node was marked as deleteable! \n");
1725 
1726  stptest_extreduceTearDown(scip, graph, &redcostdata);
1727 
1728  return SCIP_OKAY;
1729 }
1730 
1731 
1732 /** tests that edge can be deleted by general star test */
1733 static
1734 SCIP_RETCODE testGeneralStarDeletedEdge1(
1735  SCIP* scip /**< SCIP data structure */
1736 )
1737 {
1738  REDCOST* redcostdata;
1739  GRAPH* graph;
1740  int nelims = 0;
1741  const int nnodes = 8;
1742  const int nedges = 20;
1743  const int root = 0;
1744  SCIP_Real cutoff = 100.0;
1745 
1746  assert(scip);
1747 
1748  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1749 
1750  /* build tree */
1751  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1752  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1753  graph_knot_add(graph, STP_TERM); /* node 2 */
1754  graph_knot_add(graph, STP_TERM); /* node 3 */
1755  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
1756  graph_knot_add(graph, STP_TERM); /* node 5 */
1757  graph_knot_add(graph, STP_TERM); /* node 6 */
1758  graph_knot_add(graph, STP_TERM_NONE); /* node 7 */
1759 
1760  graph->source = 2;
1761 
1762  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1763  graph_edge_addBi(scip, graph, 0, 2, 1.0);
1764  graph_edge_addBi(scip, graph, 0, 3, 1.0);
1765  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1766  graph_edge_addBi(scip, graph, 1, 5, 1.0);
1767 
1768  graph_edge_addBi(scip, graph, 4, 6, 1.1);
1769  graph_edge_addBi(scip, graph, 4, 7, 1.0);
1770 
1771  /* short cuts */
1772  graph_edge_addBi(scip, graph, 2, 3, 2.0);
1773  graph_edge_addBi(scip, graph, 3, 6, 2.0);
1774  graph_edge_addBi(scip, graph, 2, 5, 2.0);
1775 
1776  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1777  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1778  extInitRedCostArrays(graph, redcostdata);
1779 
1780  /* actual test */
1781  SCIP_CALL( extreduce_deleteGeneralStars(scip, redcostdata, NULL, graph, NULL, &nelims) );
1782 
1783  STPTEST_ASSERT_MSG(graph_edge_isDeleted(graph, 0), "edge 0 was not deleted \n");
1784 
1785  stptest_extreduceTearDown(scip, graph, &redcostdata);
1786 
1787  return SCIP_OKAY;
1788 }
1789 
1790 
1791 /** tests that edge can be deleted by general star test */
1792 static
1793 SCIP_RETCODE testGeneralStarDeletedEdge2(
1794  SCIP* scip /**< SCIP data structure */
1795 )
1796 {
1797  REDCOST* redcostdata;
1798  GRAPH* graph;
1799  int nelims = 0;
1800  const int nnodes = 6;
1801  const int nedges = 20;
1802  const int root = 0;
1803  SCIP_Real cutoff = 100.0;
1804 
1805  assert(scip);
1806 
1807  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1808 
1809  /* build tree */
1810  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1811  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1812  graph_knot_add(graph, STP_TERM); /* node 2 */
1813  graph_knot_add(graph, STP_TERM); /* node 3 */
1814  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
1815  graph_knot_add(graph, STP_TERM_NONE); /* node 5 */
1816 
1817  graph->source = 2;
1818 
1819  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1820  graph_edge_addBi(scip, graph, 0, 2, 1.0);
1821  graph_edge_addBi(scip, graph, 0, 3, 1.0);
1822  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1823  graph_edge_addBi(scip, graph, 1, 5, 1.0);
1824 
1825  /* redundant */
1826  graph_edge_addBi(scip, graph, 0, 5, 1.0);
1827 
1828  /* short cuts */
1829  graph_edge_addBi(scip, graph, 2, 3, 3.0);
1830  graph_edge_addBi(scip, graph, 3, 4, 3.0);
1831  graph_edge_addBi(scip, graph, 4, 5, 3.0);
1832  graph_edge_addBi(scip, graph, 5, 2, 3.0);
1833 
1834  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1835  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1836  extInitRedCostArrays(graph, redcostdata);
1837 
1838  /* actual test */
1839  SCIP_CALL( extreduce_deleteGeneralStars(scip, redcostdata, NULL, graph, NULL, &nelims) );
1840 
1841  STPTEST_ASSERT_MSG(graph_edge_isDeleted(graph, 0), "edge 0 was not deleted \n");
1842 
1843  stptest_extreduceTearDown(scip, graph, &redcostdata);
1844 
1845  return SCIP_OKAY;
1846 }
1847 
1848 
1849 
1850 /** tests that edge can be deleted by general star test */
1851 static
1852 SCIP_RETCODE testGeneralStarDeletedEdge3(
1853  SCIP* scip /**< SCIP data structure */
1854 )
1855 {
1856  REDCOST* redcostdata;
1857  GRAPH* graph;
1858  int nelims = 0;
1859  const int nnodes = 10;
1860  const int nedges = 26;
1861  const int root = 0;
1862  SCIP_Real cutoff = 100.0;
1863 
1864  assert(scip);
1865 
1866  SCIP_CALL( redcosts_init(scip, nnodes, nedges, cutoff, root, &redcostdata) );
1867  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1868 
1869  /* build tree */
1870  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
1871  graph_knot_add(graph, STP_TERM_NONE); /* node 1 */
1872  graph_knot_add(graph, STP_TERM); /* node 2 */
1873  graph_knot_add(graph, STP_TERM); /* node 3 */
1874  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
1875  graph_knot_add(graph, STP_TERM_NONE); /* node 5 */
1876  graph_knot_add(graph, STP_TERM); /* node 6 */
1877  graph_knot_add(graph, STP_TERM); /* node 7 */
1878  graph_knot_add(graph, STP_TERM_NONE); /* node 8 */
1879  graph_knot_add(graph, STP_TERM); /* node 9 */
1880 
1881  graph->source = 2;
1882 
1883  graph_edge_addBi(scip, graph, 0, 1, 2.0);
1884  graph_edge_addBi(scip, graph, 0, 2, 2.0);
1885  graph_edge_addBi(scip, graph, 0, 3, 2.0);
1886  graph_edge_addBi(scip, graph, 1, 4, 2.0);
1887  graph_edge_addBi(scip, graph, 1, 5, 3.0);
1888 
1889  graph_edge_addBi(scip, graph, 4, 7, 2.0);
1890  graph_edge_addBi(scip, graph, 4, 8, 2.0);
1891  graph_edge_addBi(scip, graph, 8, 9, 3.0);
1892  graph_edge_addBi(scip, graph, 5, 6, 10.0);
1893 
1894  /* short cuts */
1895  graph_edge_addBi(scip, graph, 2, 3, 2.0);
1896  graph_edge_addBi(scip, graph, 2, 5, 7.0);
1897  graph_edge_addBi(scip, graph, 3, 7, 2.0);
1898  graph_edge_addBi(scip, graph, 5, 8, 3.0);
1899 
1900  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1901  extInitRedCostArrays(graph, redcostdata);
1902 
1903  /* actual test */
1904  SCIP_CALL( extreduce_deleteGeneralStars(scip, redcostdata, NULL, graph, NULL, &nelims) );
1905 
1906  STPTEST_ASSERT_MSG(graph_edge_isDeleted(graph, 0), "edge 0 was not deleted \n");
1907 
1908  stptest_extreduceTearDown(scip, graph, &redcostdata);
1909 
1910  return SCIP_OKAY;
1911 }
1912 
1913 
1914 /** tests that edge can be deleted by using SD MST argument */
1915 static
1916 SCIP_RETCODE testPcEdgeDeletedByMst1(
1917  SCIP* scip /**< SCIP data structure */
1918 )
1919 {
1920  REDCOST* redcostdata;
1921  GRAPH* graph;
1922  const int nnodes = 5;
1923  const int nedges = 16;
1924  const int root = 0;
1925  SCIP_Real cutoff = 100.0;
1926  STP_Bool* edgedeleted = NULL;
1927  int testedge = 0;
1928  SCIP_Bool deletable;
1929 
1930  assert(scip);
1931 
1932  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1933 
1934  /* build tree */
1935  graph_knot_add(graph, STP_TERM); /* node 0 */
1936  graph_knot_add(graph, STP_TERM); /* node 1 */
1937  graph_knot_add(graph, STP_TERM); /* node 2 */
1938  graph_knot_add(graph, STP_TERM); /* node 3 */
1939  graph_knot_add(graph, STP_TERM); /* node 4 */
1940 
1941  graph->source = 0;
1942 
1943  graph_edge_addBi(scip, graph, 0, 1, 1.0);
1944  graph_edge_addBi(scip, graph, 1, 2, 1.0);
1945  graph_edge_addBi(scip, graph, 1, 3, 1.0);
1946  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1947 
1948  /* add shortcut edges */
1949  graph_edge_addBi(scip, graph, 0, 2, 1.4);
1950  graph_edge_addBi(scip, graph, 0, 3, 1.4);
1951  graph_edge_addBi(scip, graph, 0, 4, 1.4);
1952  graph_edge_addBi(scip, graph, 2, 3, 1.1);
1953 
1954  SCIP_CALL( graph_pc_initPrizes(scip, graph, nnodes) );
1955 
1956  for( int i = 0; i < nnodes; i++ )
1957  graph->prize[i] = FARAWAY;
1958 
1959  graph->prize[1] = 0.09;
1960 
1961  SCIP_CALL( stptest_graphSetUpRpcOrg(scip, graph, NULL, NULL) );
1962 
1963  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
1964  extInitRedCostArraysPc(graph, redcostdata);
1965 
1966  SCIP_CALL(extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE));
1967 
1968  STPTEST_ASSERT_MSG(deletable, "edge was not deleted \n");
1969 
1970  stptest_extreduceTearDown(scip, graph, &redcostdata);
1971 
1972  return SCIP_OKAY;
1973 }
1974 
1975 
1976 
1977 /** tests that edge cannot be deleted (by using SD MST argument) */
1978 static
1979 SCIP_RETCODE testPcEdgeNotDeleted(
1980  SCIP* scip /**< SCIP data structure */
1981 )
1982 {
1983  REDCOST* redcostdata;
1984  GRAPH* graph;
1985  const int nnodes = 5;
1986  const int nedges = 16;
1987  const int root = 0;
1988  SCIP_Real cutoff = 100.0;
1989  STP_Bool* edgedeleted = NULL;
1990  int testedge = 0;
1991  SCIP_Bool deletable;
1992 
1993  assert(scip);
1994 
1995  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1996 
1997  /* build tree */
1998  graph_knot_add(graph, STP_TERM); /* node 0 */
1999  graph_knot_add(graph, STP_TERM); /* node 1 */
2000  graph_knot_add(graph, STP_TERM); /* node 2 */
2001  graph_knot_add(graph, STP_TERM); /* node 3 */
2002  graph_knot_add(graph, STP_TERM); /* node 4 */
2003 
2004  graph->source = 0;
2005 
2006  graph_edge_addBi(scip, graph, 0, 1, 1.0);
2007  graph_edge_addBi(scip, graph, 1, 2, 1.0);
2008  graph_edge_addBi(scip, graph, 1, 3, 1.0);
2009  graph_edge_addBi(scip, graph, 1, 4, 1.0);
2010 
2011  /* add shortcut edges */
2012  graph_edge_addBi(scip, graph, 0, 2, 1.4);
2013  graph_edge_addBi(scip, graph, 0, 3, 1.4);
2014  graph_edge_addBi(scip, graph, 0, 4, 1.4);
2015  graph_edge_addBi(scip, graph, 2, 3, 1.1);
2016 
2017  SCIP_CALL( graph_pc_initPrizes(scip, graph, nnodes) );
2018 
2019  for( int i = 0; i < nnodes; i++ )
2020  graph->prize[i] = FARAWAY;
2021 
2022  graph->prize[1] = 0.11;
2023 
2024  SCIP_CALL( stptest_graphSetUpRpcOrg(scip, graph, NULL, NULL) );
2025 
2026  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
2027  extInitRedCostArraysPc(graph, redcostdata);
2028 
2029  SCIP_CALL(extCheckEdge(scip, graph, redcostdata, edgedeleted, testedge, &deletable, FALSE));
2030 
2031  STPTEST_ASSERT_MSG(!deletable, "edge was deleted \n");
2032 
2033  stptest_extreduceTearDown(scip, graph, &redcostdata);
2034 
2035  return SCIP_OKAY;
2036 }
2037 
2038 
2039 /** tests that node can be deleted */
2040 static
2041 SCIP_RETCODE testPcNode3PseudoDeletedBySd1(
2042  SCIP* scip /**< SCIP data structure */
2043 )
2044 {
2045  REDCOST* redcostdata;
2046  GRAPH* graph;
2047  const int nnodes = 6;
2048  const int nedges = 14;
2049  const int root = 0;
2050  SCIP_Real cutoff = 100.0;
2051  STP_Bool* edgedeleted = NULL;
2052  int testnode = 0;
2053  SCIP_Bool deletable;
2054 
2055  assert(scip);
2056 
2057  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
2058 
2059  /* build tree */
2060  graph_knot_add(graph, STP_TERM); /* node 0 */
2061  graph_knot_add(graph, STP_TERM); /* node 1 */
2062  graph_knot_add(graph, STP_TERM); /* node 2 */
2063  graph_knot_add(graph, STP_TERM); /* node 3 */
2064  graph_knot_add(graph, STP_TERM); /* node 4 */
2065  graph_knot_add(graph, STP_TERM); /* node 5 */
2066 
2067  graph->source = 1;
2068 
2069  graph_edge_addBi(scip, graph, 0, 1, 1.0);
2070  graph_edge_addBi(scip, graph, 0, 2, 1.0);
2071  graph_edge_addBi(scip, graph, 0, 3, 1.0);
2072  graph_edge_addBi(scip, graph, 1, 4, 1.0);
2073  graph_edge_addBi(scip, graph, 2, 4, 1.0);
2074  graph_edge_addBi(scip, graph, 2, 5, 1.0);
2075  graph_edge_addBi(scip, graph, 3, 5, 1.0);
2076 
2077  SCIP_CALL( graph_pc_initPrizes(scip, graph, nnodes) );
2078 
2079  for( int i = 0; i < nnodes; i++ )
2080  graph->prize[i] = FARAWAY;
2081 
2082  graph->prize[0] = 1.0;
2083  graph->prize[2] = 0.9;
2084 
2085  SCIP_CALL( stptest_graphSetUpRpcOrg(scip, graph, NULL, NULL) );
2086 
2087  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
2088  extInitRedCostArraysPc(graph, redcostdata);
2089 
2090  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
2091 
2092  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
2093 
2094  stptest_extreduceTearDown(scip, graph, &redcostdata);
2095 
2096  return SCIP_OKAY;
2097 }
2098 
2099 
2100 /** tests that node can be deleted */
2101 static
2102 SCIP_RETCODE testPcNode4PseudoDeletedBySd1(
2103  SCIP* scip /**< SCIP data structure */
2104 )
2105 {
2106  REDCOST* redcostdata;
2107  GRAPH* graph;
2108  const int nnodes = 7;
2109  const int nedges = 18;
2110  const int root = 0;
2111  SCIP_Real cutoff = 100.0;
2112  STP_Bool* edgedeleted = NULL;
2113  int testnode = 0;
2114  SCIP_Bool deletable;
2115 
2116  assert(scip);
2117 
2118  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
2119 
2120  /* build tree */
2121  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
2122  graph_knot_add(graph, STP_TERM); /* node 1 */
2123  graph_knot_add(graph, STP_TERM); /* node 2 */
2124  graph_knot_add(graph, STP_TERM); /* node 3 */
2125  graph_knot_add(graph, STP_TERM); /* node 4 */
2126  graph_knot_add(graph, STP_TERM); /* node 5 */
2127  graph_knot_add(graph, STP_TERM); /* node 6 */
2128 
2129  graph->source = 1;
2130 
2131  graph_edge_addBi(scip, graph, 0, 1, 1.0);
2132  graph_edge_addBi(scip, graph, 0, 2, 1.5);
2133  graph_edge_addBi(scip, graph, 0, 3, 2.0);
2134  graph_edge_addBi(scip, graph, 0, 4, 2.0);
2135  graph_edge_addBi(scip, graph, 2, 5, 2.0);
2136  graph_edge_addBi(scip, graph, 2, 6, 2.0);
2137  graph_edge_addBi(scip, graph, 3, 4, 1.0);
2138  graph_edge_addBi(scip, graph, 5, 6, 1.0);
2139  graph_edge_addBi(scip, graph, 6, 3, 2.0);
2140 
2141  SCIP_CALL( graph_pc_initPrizes(scip, graph, nnodes) );
2142 
2143  for( int i = 0; i < nnodes; i++ )
2144  graph->prize[i] = FARAWAY;
2145 
2146  graph->prize[0] = 0.0;
2147  graph->prize[2] = 1.0;
2148  graph->prize[3] = 0.6;
2149 
2150  SCIP_CALL( stptest_graphSetUpRpcOrg(scip, graph, NULL, NULL) );
2151 
2152  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
2153  extInitRedCostArraysPc(graph, redcostdata);
2154 
2155  SCIP_CALL( extCheckNode(scip, graph, redcostdata, edgedeleted, testnode, &deletable, FALSE) );
2156 
2157  STPTEST_ASSERT_MSG(deletable, "node was not marked as deleteable! \n");
2158 
2159  stptest_extreduceTearDown(scip, graph, &redcostdata);
2160 
2161  return SCIP_OKAY;
2162 }
2163 
2164 /* requires interface change! */
2165 #ifdef SCIP_DISABLED
2166 /** tests correctness of pseudo deletion of all nodes */
2167 static
2168 SCIP_RETCODE testPcNodesPseudoDeletedBySd1(
2169  SCIP* scip /**< SCIP data structure */
2170 )
2171 {
2172  REDCOST* redcostdata;
2173  GRAPH* graph;
2174  const int nnodes = 6;
2175  const int nedges = 14;
2176  const int root = 0;
2177  SCIP_Real cutoff = 100.0;
2178  int nelims = 0;
2179  SCIP_Real offset = 0.0;
2180 
2181  assert(scip);
2182 
2183  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
2184 
2185  /* build tree */
2186  graph_knot_add(graph, STP_TERM); /* node 0 */
2187  graph_knot_add(graph, STP_TERM); /* node 1 */
2188  graph_knot_add(graph, STP_TERM); /* node 2 */
2189  graph_knot_add(graph, STP_TERM); /* node 3 */
2190  graph_knot_add(graph, STP_TERM); /* node 4 */
2191  graph_knot_add(graph, STP_TERM); /* node 5 */
2192 
2193  graph->source = 4;
2194 
2195  graph_edge_addBi(scip, graph, 0, 1, 1.0);
2196  graph_edge_addBi(scip, graph, 0, 2, 1.0);
2197  graph_edge_addBi(scip, graph, 0, 3, 1.0);
2198  graph_edge_addBi(scip, graph, 1, 4, 1.0);
2199  graph_edge_addBi(scip, graph, 2, 4, 1.0);
2200  graph_edge_addBi(scip, graph, 2, 5, 1.0);
2201  graph_edge_addBi(scip, graph, 3, 5, 1.0);
2202 
2203  SCIP_CALL( graph_pc_initPrizes(scip, graph, nnodes) );
2204 
2205  for( int i = 0; i < nnodes; i++ )
2206  graph->prize[i] = FARAWAY;
2207 
2208  graph->prize[0] = 1.0;
2209  graph->prize[2] = 0.9;
2210 
2211  SCIP_CALL( stptest_graphSetUpRpcOrg(scip, graph, NULL, NULL) );
2212 
2213  SCIP_CALL( redcosts_init(scip, graph->knots, graph->edges, cutoff, root, &redcostdata) );
2214  extInitRedCostArraysPcWithBase(graph, nnodes - 2, redcostdata);
2215 
2216  SCIP_CALL( extreduce_pseudoDeleteNodes(scip, NULL, redcostdata, graph, &offset, &nelims) );
2217 
2218  STPTEST_ASSERT_MSG(nelims == 1, "not enough eliminations \n");
2219  STPTEST_ASSERT_MSG(graph->grad[0] == 0, "node was not marked as deleteable! \n");
2220 
2221  stptest_extreduceTearDown(scip, graph, &redcostdata);
2222 
2223  return SCIP_OKAY;
2224 }
2225 #endif
2226 
2227 
2228 
2229 
2230 /** tests that path replacement deletes an edge */
2231 static
2232 SCIP_RETCODE testPathReplaceDeletesEdge(
2233  SCIP* scip /**< SCIP data structure */
2234 )
2235 {
2236  GRAPH* graph;
2237  const int nnodes = 9;
2238  const int nedges = 28;
2239  int nelims = 0;
2240  int testedge = 4;
2241 
2242  assert(scip);
2243 
2244  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
2245 
2246  /* build tree */
2247  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
2248  graph_knot_add(graph, STP_TERM); /* node 1 */
2249  graph_knot_add(graph, STP_TERM); /* node 2 */
2250  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
2251  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
2252  graph_knot_add(graph, STP_TERM_NONE); /* node 5 */
2253  graph_knot_add(graph, STP_TERM_NONE); /* node 6 */
2254  graph_knot_add(graph, STP_TERM_NONE); /* node 7 */
2255  graph_knot_add(graph, STP_TERM_NONE); /* node 8 */
2256 
2257 
2258  graph->source = 1;
2259 
2260  graph_edge_addBi(scip, graph, 0, 1, 1.0);
2261  graph_edge_addBi(scip, graph, 0, 2, 1.0);
2262  graph_edge_addBi(scip, graph, 0, 3, 1.0);
2263  graph_edge_addBi(scip, graph, 1, 5, 1.0);
2264  graph_edge_addBi(scip, graph, 2, 7, 1.0);
2265  graph_edge_addBi(scip, graph, 3, 4, 1.0);
2266  graph_edge_addBi(scip, graph, 3, 5, 1.0);
2267  graph_edge_addBi(scip, graph, 3, 7, 1.0);
2268  graph_edge_addBi(scip, graph, 4, 6, 1.0);
2269  graph_edge_addBi(scip, graph, 4, 8, 1.0);
2270  graph_edge_addBi(scip, graph, 5, 6, 1.0);
2271  graph_edge_addBi(scip, graph, 7, 8, 0.1);
2272 
2273  stptest_graphSetUp(scip, graph);
2274 
2275  SCIP_CALL( reduce_pathreplace(scip, graph, &nelims) );
2276  STPTEST_ASSERT_MSG(graph_edge_isDeleted(graph, testedge), "edge was not deleted! \n");
2277 
2278  stptest_graphTearDown(scip, graph);
2279 
2280  return SCIP_OKAY;
2281 }
2282 
2283 
2284 
2285 /** tests that path replacement deletes an edge */
2286 static
2287 SCIP_RETCODE testPathReplaceDeletesEdge2(
2288  SCIP* scip /**< SCIP data structure */
2289 )
2290 {
2291  GRAPH* graph;
2292  const int nnodes = 10;
2293  const int nedges = 28;
2294  int nelims = 0;
2295  int testedge = 4;
2296 
2297  assert(scip);
2298 
2299  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
2300 
2301  /* build tree */
2302  graph_knot_add(graph, STP_TERM_NONE); /* node 0 */
2303  graph_knot_add(graph, STP_TERM); /* node 1 */
2304  graph_knot_add(graph, STP_TERM); /* node 2 */
2305  graph_knot_add(graph, STP_TERM_NONE); /* node 3 */
2306  graph_knot_add(graph, STP_TERM_NONE); /* node 4 */
2307  graph_knot_add(graph, STP_TERM_NONE); /* node 5 */
2308  graph_knot_add(graph, STP_TERM_NONE); /* node 6 */
2309  graph_knot_add(graph, STP_TERM_NONE); /* node 7 */
2310  graph_knot_add(graph, STP_TERM_NONE); /* node 8 */
2311  graph_knot_add(graph, STP_TERM); /* node 9 */
2312 
2313 
2314  graph->source = 1;
2315 
2316  graph_edge_addBi(scip, graph, 0, 1, 1.0);
2317  graph_edge_addBi(scip, graph, 0, 2, 1.0);
2318  graph_edge_addBi(scip, graph, 0, 3, 2.0);
2319  graph_edge_addBi(scip, graph, 1, 5, 1.0);
2320  graph_edge_addBi(scip, graph, 2, 7, 1.0);
2321  graph_edge_addBi(scip, graph, 3, 4, 1.0);
2322  graph_edge_addBi(scip, graph, 3, 5, 1.0);
2323  graph_edge_addBi(scip, graph, 3, 7, 1.0);
2324  graph_edge_addBi(scip, graph, 4, 6, 1.0);
2325  graph_edge_addBi(scip, graph, 4, 8, 1.0);
2326  graph_edge_addBi(scip, graph, 5, 6, 1.0);
2327  graph_edge_addBi(scip, graph, 7, 8, 0.1);
2328 
2329  graph_edge_addBi(scip, graph, 9, 2, 0.5);
2330  graph_edge_addBi(scip, graph, 0, 9, 0.5);
2331 
2332 
2333  stptest_graphSetUp(scip, graph);
2334 
2335  SCIP_CALL( reduce_pathreplace(scip, graph, &nelims) );
2336  STPTEST_ASSERT_MSG(graph_edge_isDeleted(graph, testedge), "edge was not deleted! \n");
2337 
2338  stptest_graphTearDown(scip, graph);
2339 
2340 
2341  return SCIP_OKAY;
2342 }
2343 
2344 
2345 /** frees, etc. */
2346 void stptest_extreduceTearDown(
2347  SCIP* scip, /**< SCIP data structure */
2348  GRAPH* graph, /**< the graph */
2349  REDCOST** redcostdata /**< reduced cost data */
2350  )
2351 {
2352  assert(scip && graph);
2353 
2354  if( redcostdata )
2355  redcosts_free(scip, redcostdata);
2356 
2357  stptest_graphTearDown(scip, graph);
2358 }
2359 
2360 
2361 /** tests extended reduction techniques */
2362 SCIP_RETCODE stptest_extreduce(
2363  SCIP* scip /**< SCIP data structure */
2364 )
2365 {
2366  assert(scip);
2367  SCIP_CALL( testPathReplaceDeletesEdge2(scip) );
2368 
2369  SCIP_CALL( testPathReplaceDeletesEdge(scip) );
2370 
2371 
2372  SCIP_CALL( testNode3PseudoDeletedBySdBiased(scip) );
2373 
2374 
2375  SCIP_CALL( testNode3PseudoDeletedBySdBiasedSimple(scip) );
2376 
2377 
2378  SCIP_CALL( testNode3PseudoDeletedByContraction(scip) );
2379 
2380  SCIP_CALL( testEdgeDeletedBy3LeafSpg(scip) );
2381 
2382  SCIP_CALL( testEdgeDeletedByMultiRedCosts(scip) );
2383 
2384  SCIP_CALL( testGeneralStarDeletedEdge1(scip) );
2385  SCIP_CALL( testGeneralStarDeletedEdge2(scip) );
2386  SCIP_CALL( testGeneralStarDeletedEdge3(scip) );
2387 
2388  SCIP_CALL( testEdgeDeletedByEqBottleneck2(scip) );
2389  SCIP_CALL( testEdgeDeletedByEqBottleneck(scip) );
2390 
2391 
2392  SCIP_CALL( testNode4PseudoDeletedBySd1(scip) );
2393  SCIP_CALL( testNode4PseudoNotDeletedBySd1(scip) );
2394 
2395  SCIP_CALL( testNode3PseudoDeletedByRedCosts1(scip) );
2396 
2397  SCIP_CALL( testPcNode4PseudoDeletedBySd1(scip) );
2398  // SCIP_CALL( testPcNodesPseudoDeletedBySd1(scip) );
2399  SCIP_CALL( testPcNode3PseudoDeletedBySd1(scip) );
2400  SCIP_CALL( testPcEdgeDeletedByMst1(scip) );
2401  SCIP_CALL( testPcEdgeNotDeleted(scip) );
2402 
2403  //SCIP_CALL( testPcNode3NotPseudoDeletedBySd1(scip) );
2404  SCIP_CALL( testNode3PseudoDeletedBySd1(scip) );
2405  SCIP_CALL( testNode3PseudoDeletedBySd2(scip) );
2406  SCIP_CALL( testNode3PseudoDeletedBySd3(scip) );
2407 
2408 
2409  SCIP_CALL( testEdgeDeletedByCommonRedCostsTargets(scip) );
2410  SCIP_CALL( testEdgeDeletedByMst2(scip) );
2411  SCIP_CALL( testEdgeDeletedByMst1(scip) );
2412  SCIP_CALL( testEdgeNotDeleted1(scip) );
2413  SCIP_CALL( testEdgeDeletion5_deprecated(scip, 1) );
2414  SCIP_CALL( testEdgeDeletion5_deprecated(scip, 2) );
2415  SCIP_CALL( testEdgeDeletion4_deprecated(scip, 1) );
2416  SCIP_CALL( testEdgeDeletion4_deprecated(scip, 2) );
2417  SCIP_CALL( testEdgeDeletion4_deprecated(scip, 3) );
2418  SCIP_CALL( testEdgeDeletion3_deprecated(scip, 1) );
2419  SCIP_CALL( testEdgeDeletion3_deprecated(scip, 2) );
2420  SCIP_CALL( testEdgeDeletion3_deprecated(scip, 3) );
2421  SCIP_CALL( testEdgeDeletion3_deprecated(scip, 4) );
2422  SCIP_CALL( testEdgeDeletion2_deprecated(scip, 1) );
2423  SCIP_CALL( testEdgeDeletion1_deprecated(scip) );
2424 
2425 
2426 
2427  printf("extreduce test: all ok \n");
2428 
2429  return SCIP_OKAY;
2430 }
testEdgeDeletedByMst2
static SCIP_RETCODE testEdgeDeletedByMst2(SCIP *scip)
Definition: stptest_extreduce.c:934
reduced_costs_parameters::cutoff
SCIP_Real cutoff
Definition: redcosts.h:44
testNode3PseudoDeletedByContraction
static SCIP_RETCODE testNode3PseudoDeletedByContraction(SCIP *scip)
Definition: stptest_extreduce.c:1272
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
extension_data_permanent::distdata_biased
DISTDATA * distdata_biased
Definition: extreducedefs.h:107
testNode4PseudoDeletedBySd1
static SCIP_RETCODE testNode4PseudoDeletedBySd1(SCIP *scip)
Definition: stptest_extreduce.c:1623
GRAPH::head
int *RESTRICT head
Definition: graphdefs.h:224
GRAPH::source
int source
Definition: graphdefs.h:195
testPcNode3PseudoDeletedBySd1
static SCIP_RETCODE testPcNode3PseudoDeletedBySd1(SCIP *scip)
Definition: stptest_extreduce.c:2041
shortest_path::edge
signed int edge
Definition: graphdefs.h:287
testEdgeDeletedByMst1
static SCIP_RETCODE testEdgeDeletedByMst1(SCIP *scip)
Definition: stptest_extreduce.c:880
graph_edge_addBi
void graph_edge_addBi(SCIP *, GRAPH *, int, int, double)
extreduce_distDataFree
void extreduce_distDataFree(SCIP *, const GRAPH *, DISTDATA **)
Definition: extreduce_dist.c:1784
extreduce_checkArc
SCIP_RETCODE extreduce_checkArc(SCIP *, const GRAPH *, REDCOST *, int, EXTPERMA *, SCIP_Bool *)
Definition: extreduce_base.c:1794
testPathReplaceDeletesEdge
static SCIP_RETCODE testPathReplaceDeletesEdge(SCIP *scip)
Definition: stptest_extreduce.c:2232
graph_mark
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
graph_free_dcsr
void graph_free_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1807
redcosts_addLevel
void redcosts_addLevel(REDCOST *redcostdata)
Definition: redcosts.c:460
extension_data_permanent
Definition: extreducedefs.h:101
testNode3PseudoDeletedBySd2
static SCIP_RETCODE testNode3PseudoDeletedBySd2(SCIP *scip)
Definition: stptest_extreduce.c:1514
graph_path_init
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
FALSE
#define FALSE
Definition: def.h:87
extension_data_permanent::distdata_default
DISTDATA * distdata_default
Definition: extreducedefs.h:106
TRUE
#define TRUE
Definition: def.h:86
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
graph.h
includes various files containing graph methods used for Steiner tree problems
testEdgeDeletedByEqBottleneck2
static SCIP_RETCODE testEdgeDeletedByEqBottleneck2(SCIP *scip)
Definition: stptest_extreduce.c:1106
shortest_path
Definition: graphdefs.h:284
redcosts_free
void redcosts_free(SCIP *scip, REDCOST **redcostdata)
Definition: redcosts.c:743
extInitRedCostArraysPc
static void extInitRedCostArraysPc(const GRAPH *graph, REDCOST *redcostdata)
Definition: stptest_extreduce.c:226
EAT_LAST
#define EAT_LAST
Definition: graphdefs.h:58
stptest_graphSetUpRpcOrg
SCIP_RETCODE stptest_graphSetUpRpcOrg(SCIP *, GRAPH *, int *, int *)
Definition: stptest_graph.c:317
FARAWAY
#define FARAWAY
Definition: graphdefs.h:89
extreduce_checkEdge
SCIP_RETCODE extreduce_checkEdge(SCIP *, const GRAPH *, const REDCOST *, int, EXTPERMA *, SCIP_Bool *)
Definition: extreduce_base.c:1854
stptest_extreduceTearDown
void stptest_extreduceTearDown(SCIP *scip, GRAPH *graph, REDCOST **redcostdata)
Definition: stptest_extreduce.c:2346
reduce_starInit
SCIP_RETCODE reduce_starInit(SCIP *, int, STAR **)
Definition: reduce_util.c:1725
redcosts_initializeDistancesTop
SCIP_RETCODE redcosts_initializeDistancesTop(SCIP *scip, GRAPH *g, REDCOST *redcostdata)
Definition: redcosts.c:573
testEdgeNotDeleted1
static SCIP_RETCODE testEdgeNotDeleted1(SCIP *scip)
Definition: stptest_extreduce.c:1046
graph_init_dcsr
SCIP_RETCODE graph_init_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1721
STP_TERM_NONE
#define STP_TERM_NONE
Definition: graphdefs.h:62
graph_pc_initPrizes
SCIP_RETCODE graph_pc_initPrizes(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:741
stptest_extreduce
SCIP_RETCODE stptest_extreduce(SCIP *scip)
Definition: stptest_extreduce.c:2362
extCheckArc
static SCIP_RETCODE extCheckArc(SCIP *scip, GRAPH *graph, REDCOST *redcostdata, STP_Bool *edgedeleted, int edge, int edgedelete, int nclosenodes, SCIP_Bool *deletable, SCIP_Bool equality)
Definition: stptest_extreduce.c:42
GRAPH::oeat
int *RESTRICT oeat
Definition: graphdefs.h:231
extreduce.h
This file implements extended reduction techniques for several Steiner problems.
STPTEST_ASSERT_MSG
#define STPTEST_ASSERT_MSG(cond, msg)
Definition: stptest.h:51
extreduce_extPermaInit
SCIP_RETCODE extreduce_extPermaInit(SCIP *, enum EXTRED_MODE, const GRAPH *, STP_Bool *, EXTPERMA **)
Definition: extreduce_data.c:162
reduce_starFree
void reduce_starFree(SCIP *, STAR **)
Definition: reduce_util.c:1758
testEdgeDeletedBy3LeafSpg
static SCIP_RETCODE testEdgeDeletedBy3LeafSpg(SCIP *scip)
Definition: stptest_extreduce.c:1159
redcosts_getEdgeCostsTop
SCIP_Real * redcosts_getEdgeCostsTop(const REDCOST *redcostdata)
Definition: redcosts.c:202
GRAPH::prize
SCIP_Real * prize
Definition: graphdefs.h:210
graph_initHistory
SCIP_RETCODE graph_initHistory(SCIP *, GRAPH *)
Definition: graph_base.c:695
redcosts_getNnodes
int redcosts_getNnodes(const REDCOST *redcostdata)
Definition: redcosts.c:165
shortest_path::dist
SCIP_Real dist
Definition: graphdefs.h:286
GRAPH::grad
int *RESTRICT grad
Definition: graphdefs.h:201
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
graph_pseudoAncestors_addToEdge
SCIP_RETCODE graph_pseudoAncestors_addToEdge(SCIP *, int, int, GRAPH *)
Definition: graph_history.c:1523
NULL
#define NULL
Definition: lpi_spx1.cpp:155
extreduce_edgeRemove
void extreduce_edgeRemove(SCIP *, int, GRAPH *, DISTDATA *, EXTPERMA *)
Definition: extreduce_base.c:1946
redcosts_getNedges
int redcosts_getNedges(const REDCOST *redcostdata)
Definition: redcosts.c:176
SCIP_OKAY
Definition: type_retcode.h:33
GRAPH::knots
int knots
Definition: graphdefs.h:190
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:384
testGeneralStarDeletedEdge3
static SCIP_RETCODE testGeneralStarDeletedEdge3(SCIP *scip)
Definition: stptest_extreduce.c:1852
testEdgeDeletion4_deprecated
static SCIP_RETCODE testEdgeDeletion4_deprecated(SCIP *scip, int variant)
Definition: stptest_extreduce.c:359
extension_data_permanent::redcostEqualAllow
SCIP_Bool redcostEqualAllow
Definition: extreducedefs.h:128
testNode3PseudoDeletedBySdBiasedSimple
static SCIP_RETCODE testNode3PseudoDeletedBySdBiasedSimple(SCIP *scip)
Definition: stptest_extreduce.c:1334
testGeneralStarDeletedEdge2
static SCIP_RETCODE testGeneralStarDeletedEdge2(SCIP *scip)
Definition: stptest_extreduce.c:1793
STP_Bool
unsigned char STP_Bool
Definition: portab.h:34
stptest_graphTearDown
void stptest_graphTearDown(SCIP *, GRAPH *)
Definition: stptest_graph.c:274
extreduce_extPermaFree
void extreduce_extPermaFree(SCIP *, EXTPERMA **)
Definition: extreduce_data.c:386
SCIP_Bool
#define SCIP_Bool
Definition: def.h:84
graph_edge_isDeleted
SCIP_Bool graph_edge_isDeleted(const GRAPH *, int)
Definition: graph_stats.c:121
extension_data_permanent::redcostdata
REDCOST * redcostdata
Definition: extreducedefs.h:105
testPcEdgeDeletedByMst1
static SCIP_RETCODE testPcEdgeDeletedByMst1(SCIP *scip)
Definition: stptest_extreduce.c:1916
graph_isMarked
SCIP_Bool graph_isMarked(const GRAPH *)
Definition: graph_base.c:1165
reduce_pathreplace
SCIP_RETCODE reduce_pathreplace(SCIP *, GRAPH *, int *)
Definition: reduce_path.c:1119
GRAPH::tail
int *RESTRICT tail
Definition: graphdefs.h:223
redcosts_getNodeToTermsPathsTop
PATH * redcosts_getNodeToTermsPathsTop(const REDCOST *redcostdata)
Definition: redcosts.c:253
redcosts_init
SCIP_RETCODE redcosts_init(SCIP *scip, int nnodes, int nedges, SCIP_Real cutoff, int redCostRoot, REDCOST **redcostdata)
Definition: redcosts.c:605
flipedge
#define flipedge(edge)
Definition: graphdefs.h:84
STP_TERM
#define STP_TERM
Definition: graphdefs.h:61
testEdgeDeletion5_deprecated
static SCIP_RETCODE testEdgeDeletion5_deprecated(SCIP *scip, int variant)
Definition: stptest_extreduce.c:269
distance_data
Definition: extreducedefs.h:79
testNode3PseudoDeletedBySdBiased
static SCIP_RETCODE testNode3PseudoDeletedBySdBiased(SCIP *scip)
Definition: stptest_extreduce.c:1400
extInitRedCostArrays
static void extInitRedCostArrays(const GRAPH *graph, REDCOST *redcostdata)
Definition: stptest_extreduce.c:194
extDeleteNodes
static SCIP_RETCODE extDeleteNodes(SCIP *scip, GRAPH *graph, REDCOST *redcostdata, SCIP_Bool allowEquality)
Definition: stptest_extreduce.c:156
graph_pc_isPc
SCIP_Bool graph_pc_isPc(const GRAPH *)
Definition: graph_pcbase.c:2463
redcosts_getNodeToTermsBasesTop
int * redcosts_getNodeToTermsBasesTop(const REDCOST *redcostdata)
Definition: redcosts.c:277
testPcNode4PseudoDeletedBySd1
static SCIP_RETCODE testPcNode4PseudoDeletedBySd1(SCIP *scip)
Definition: stptest_extreduce.c:2102
portab.h
Portable definitions.
testGeneralStarDeletedEdge1
static SCIP_RETCODE testGeneralStarDeletedEdge1(SCIP *scip)
Definition: stptest_extreduce.c:1734
testEdgeDeletedByEqBottleneck
static SCIP_RETCODE testEdgeDeletedByEqBottleneck(SCIP *scip)
Definition: stptest_extreduce.c:995
testEdgeDeletedByCommonRedCostsTargets
static SCIP_RETCODE testEdgeDeletedByCommonRedCostsTargets(SCIP *scip)
Definition: stptest_extreduce.c:712
testEdgeDeletedByMultiRedCosts
static SCIP_RETCODE testEdgeDeletedByMultiRedCosts(SCIP *scip)
Definition: stptest_extreduce.c:788
redcosts_setCutoffTop
void redcosts_setCutoffTop(SCIP_Real cutoff, REDCOST *redcostdata)
Definition: redcosts.c:394
extreduce_distDataInit
SCIP_RETCODE extreduce_distDataInit(SCIP *, GRAPH *, int, SCIP_Bool, SCIP_Bool, DISTDATA **)
Definition: extreduce_dist.c:1218
testNode3PseudoDeletedBySd3
static SCIP_RETCODE testNode3PseudoDeletedBySd3(SCIP *scip)
Definition: stptest_extreduce.c:1565
stptest.h
includes various testing methods for Steiner tree problems
GRAPH::cost
SCIP_Real * cost
Definition: graphdefs.h:221
testPathReplaceDeletesEdge2
static SCIP_RETCODE testPathReplaceDeletesEdge2(SCIP *scip)
Definition: stptest_extreduce.c:2287
testNode3PseudoDeletedByRedCosts1
static SCIP_RETCODE testNode3PseudoDeletedByRedCosts1(SCIP *scip)
Definition: stptest_extreduce.c:1211
extreduce_deleteGeneralStars
SCIP_RETCODE extreduce_deleteGeneralStars(SCIP *, REDCOST *, const int *, GRAPH *, STP_Bool *, int *)
Definition: extreduce_base.c:1750
stptest_graphSetUp
SCIP_RETCODE stptest_graphSetUp(SCIP *, GRAPH *)
Definition: stptest_graph.c:286
testPcEdgeNotDeleted
static SCIP_RETCODE testPcEdgeNotDeleted(SCIP *scip)
Definition: stptest_extreduce.c:1979
extCheckEdge
static SCIP_RETCODE extCheckEdge(SCIP *scip, GRAPH *graph, REDCOST *redcostdata, STP_Bool *edgedeleted, int edge, SCIP_Bool *deletable, SCIP_Bool allowEquality)
Definition: stptest_extreduce.c:84
SCIP_Real
#define SCIP_Real
Definition: def.h:177
testNode4PseudoNotDeletedBySd1
static SCIP_RETCODE testNode4PseudoNotDeletedBySd1(SCIP *scip)
Definition: stptest_extreduce.c:1680
GRAPH::outbeg
int *RESTRICT outbeg
Definition: graphdefs.h:204
redcosts_getRootToNodeDistTop
SCIP_Real * redcosts_getRootToNodeDistTop(const REDCOST *redcostdata)
Definition: redcosts.c:228
reduced_costs_parameters
Definition: redcosts.h:42
graph_addPseudoAncestor
void graph_addPseudoAncestor(GRAPH *, int *)
Definition: graph_history.c:1293
GRAPH::edges
int edges
Definition: graphdefs.h:219
extreduce_mstbiasedCheck3NodeSimple
SCIP_RETCODE extreduce_mstbiasedCheck3NodeSimple(SCIP *, const GRAPH *, int, DISTDATA *, DISTDATA *, SCIP_Bool *)
Definition: extreduce_extmstbiased.c:226
extreduce_checkNode
SCIP_RETCODE extreduce_checkNode(SCIP *, const GRAPH *, const REDCOST *, int, STAR *, EXTPERMA *, SCIP_Bool *)
Definition: extreduce_base.c:1890
testEdgeDeletion1_deprecated
static SCIP_RETCODE testEdgeDeletion1_deprecated(SCIP *scip)
Definition: stptest_extreduce.c:651
nnodes
#define nnodes
Definition: gastrans.c:65
testEdgeDeletion2_deprecated
static SCIP_RETCODE testEdgeDeletion2_deprecated(SCIP *scip, int variant)
Definition: stptest_extreduce.c:569
reduce_costs_data
Definition: redcosts.c:34
graph_init
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
node_one_hop_star
Definition: reduce_util.c:53
STPTEST_EXT_MAXNCLOSENODES
#define STPTEST_EXT_MAXNCLOSENODES
Definition: stptest_extreduce.c:38
extCheckNode
static SCIP_RETCODE extCheckNode(SCIP *scip, GRAPH *graph, REDCOST *redcostdata, STP_Bool *edgedeleted, int node, SCIP_Bool *deletable, SCIP_Bool allowEquality)
Definition: stptest_extreduce.c:118
reduce.h
includes various reduction methods for Steiner tree problems
testNode3PseudoDeletedBySd1
static SCIP_RETCODE testNode3PseudoDeletedBySd1(SCIP *scip)
Definition: stptest_extreduce.c:1461
redcosts_setRootTop
void redcosts_setRootTop(int root, REDCOST *redcostdata)
Definition: redcosts.c:447
testEdgeDeletion3_deprecated
static SCIP_RETCODE testEdgeDeletion3_deprecated(SCIP *scip, int variant)
Definition: stptest_extreduce.c:459
redcosts_initFromParams
SCIP_RETCODE redcosts_initFromParams(SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
Definition: redcosts.c:590
extreduce_pseudoDeleteNodes
SCIP_RETCODE extreduce_pseudoDeleteNodes(SCIP *, const SCIP_Bool *, EXTPERMA *, GRAPH *, SCIP_Real *, int *)
Definition: extreduce_base.c:1668