Scippy

SCIP

Solving Constraint Integer Programs

stptest_reducesepa.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_reducesepa.c
17  * @brief tests for Steiner tree node-separator reductions
18  * @author Daniel Rehfeldt
19  *
20  * This file implements unit tests for Steiner tree node-separator based reduction methods.
21  *
22  * A list of all interface methods can be found in stptest.h.
23  *
24  */
25 
26 //#define SCIP_DEBUG
27 
28 #include <stdio.h>
29 #include <assert.h>
30 #include "stptest.h"
31 #include "graph.h"
32 #include "reduce.h"
33 #include "portab.h"
34 #include "mincut.h"
35 
36 
37 /** tests terminal separator method */
38 static
39 SCIP_RETCODE testTerminalSeparatorsAreFound(
40  SCIP* scip /**< SCIP data structure */
41 )
42 {
43  const int* sepaterms;
44  TERMSEPAS* termsepas;
45  GRAPH* graph;
46  int nnodes = 5;
47  int nedges = 10;
48  int nsinknodes;
49  int sinkterm;
50 
51  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
52 
53  for( int i = 0; i < nnodes; i++ )
54  graph_knot_add(graph, STP_TERM_NONE);
55 
56  graph_knot_chg(graph, 0, STP_TERM);
57  graph_knot_chg(graph, 1, STP_TERM);
58  graph_knot_chg(graph, 2, STP_TERM);
59  graph_knot_chg(graph, 4, STP_TERM);
60 
61  graph->source = 0;
62 
63  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
64  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
65  graph_edge_addBi(scip, graph, 1, 3, 1.0);
66  graph_edge_addBi(scip, graph, 2, 3, 1.0);
67  graph_edge_addBi(scip, graph, 3, 4, 1.0);
68 
69  SCIP_CALL( stptest_graphSetUp(scip, graph) );
70 
71  SCIP_CALL( mincut_termsepasInit(scip, graph, 10, 5, &termsepas) );
72  SCIP_CALL( mincut_findTerminalSeparators(scip, NULL, graph, termsepas) );
73  sepaterms = mincut_termsepasGetFirst(2, termsepas, &sinkterm, &nsinknodes);
74 
75  STPTEST_ASSERT(sepaterms != NULL);
76  STPTEST_ASSERT(sinkterm == 4);
77  STPTEST_ASSERT(mincut_termsepasGetNall(termsepas) == 1);
78 
79  sepaterms = mincut_termsepasGetNext(2, termsepas, &sinkterm, &nsinknodes);
80  STPTEST_ASSERT(sepaterms == NULL);
81 
82  mincut_termsepasFree(scip, &termsepas);
83 
84  stptest_graphTearDown(scip, graph);
85 
86  return SCIP_OKAY;
87 }
88 
89 
90 
91 /** tests terminal separator method */
92 static
93 SCIP_RETCODE testTerminalSeparatorsAreFound2(
94  SCIP* scip /**< SCIP data structure */
95 )
96 {
97  const int* sepaterms;
98  TERMSEPAS* termsepas;
99  GRAPH* graph;
100  int nnodes = 8;
101  int nedges = 22;
102  int nsinknodes;
103  int sinkterm;
104 
105  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
106 
107  for( int i = 0; i < nnodes; i++ )
108  graph_knot_add(graph, STP_TERM_NONE);
109 
110  graph_knot_chg(graph, 0, STP_TERM);
111  graph_knot_chg(graph, 1, STP_TERM);
112  graph_knot_chg(graph, 2, STP_TERM);
113  graph_knot_chg(graph, 4, STP_TERM);
114  graph_knot_chg(graph, 5, STP_TERM);
115  graph_knot_chg(graph, 7, STP_TERM);
116 
117  graph->source = 0;
118 
119  graph_edge_addBi(scip, graph, 0, 1, 1.0);
120  graph_edge_addBi(scip, graph, 0, 2, 1.0);
121  graph_edge_addBi(scip, graph, 0, 6, 1.0);
122  graph_edge_addBi(scip, graph, 0, 7, 1.0);
123 
124  graph_edge_addBi(scip, graph, 1, 2, 1.0);
125  graph_edge_addBi(scip, graph, 1, 3, 1.0);
126  graph_edge_addBi(scip, graph, 1, 5, 1.0);
127  graph_edge_addBi(scip, graph, 2, 4, 1.0);
128  graph_edge_addBi(scip, graph, 3, 4, 1.0);
129 
130  graph_edge_addBi(scip, graph, 5, 7, 1.0);
131  graph_edge_addBi(scip, graph, 6, 7, 1.0);
132 
133 
134  SCIP_CALL( stptest_graphSetUp(scip, graph) );
135 
136  SCIP_CALL( mincut_termsepasInit(scip, graph, 10, 5, &termsepas) );
137 
138  SCIP_CALL( mincut_findTerminalSeparators(scip, NULL, graph, termsepas) );
139  sepaterms = mincut_termsepasGetFirst(2, termsepas, &sinkterm, &nsinknodes);
140 
141  STPTEST_ASSERT(sepaterms != NULL);
142  STPTEST_ASSERT(sinkterm == 4 || sinkterm == 5);
143 
144  sepaterms = mincut_termsepasGetNext(2, termsepas, &sinkterm, &nsinknodes);
145 
146  STPTEST_ASSERT(sepaterms != NULL);
147  STPTEST_ASSERT(sinkterm == 4 || sinkterm == 5);
148 
149  // printf("%d %d \n", sepaterms[0], sepaterms[1]);
150 
151  mincut_termsepasFree(scip, &termsepas);
152 
153  stptest_graphTearDown(scip, graph);
154 
155  return SCIP_OKAY;
156 }
157 
158 
159 
160 /** tests terminal separator method */
161 static
162 SCIP_RETCODE testTerminalSeparatorsAreFound3(
163  SCIP* scip /**< SCIP data structure */
164 )
165 {
166  TERMSEPAS* termsepas;
167  GRAPH* graph;
168  const int* sepaterms;
169  int nsinknodes;
170  int sinkterm;
171  int nnodes = 9;
172  int nedges = 26;
173 
174  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
175 
176  for( int i = 0; i < nnodes; i++ )
177  graph_knot_add(graph, STP_TERM_NONE);
178 
179  graph_knot_chg(graph, 0, STP_TERM);
180  graph_knot_chg(graph, 2, STP_TERM);
181  graph_knot_chg(graph, 3, STP_TERM);
182  graph_knot_chg(graph, 5, STP_TERM);
183  graph_knot_chg(graph, 8, STP_TERM);
184  graph_knot_chg(graph, 7, STP_TERM);
185 
186 
187  graph->source = 0;
188 
189  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
190  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
191  graph_edge_addBi(scip, graph, 0, 3, 1.0);
192  graph_edge_addBi(scip, graph, 0, 4, 1.0);
193  graph_edge_addBi(scip, graph, 1, 5, 1.0);
194  graph_edge_addBi(scip, graph, 2, 5, 1.0);
195  graph_edge_addBi(scip, graph, 3, 7, 1.0);
196  graph_edge_addBi(scip, graph, 4, 6, 1.0);
197  graph_edge_addBi(scip, graph, 6, 7, 1.0);
198  graph_edge_addBi(scip, graph, 2, 8, 1.0);
199  graph_edge_addBi(scip, graph, 5, 8, 1.0);
200  graph_edge_addBi(scip, graph, 8, 7, 1.0);
201 
202 
203  SCIP_CALL( stptest_graphSetUp(scip, graph) );
204 
205  SCIP_CALL( mincut_termsepasInit(scip, graph, 10, 5, &termsepas) );
206  SCIP_CALL( mincut_findTerminalSeparators(scip, NULL, graph, termsepas) );
207  sepaterms = mincut_termsepasGetNext(3, termsepas, &sinkterm, &nsinknodes);
208 
209  STPTEST_ASSERT(sepaterms != NULL);
210  STPTEST_ASSERT(sinkterm == 8);
211  sepaterms = mincut_termsepasGetNext(3, termsepas, &sinkterm, &nsinknodes);
212  STPTEST_ASSERT(sepaterms == NULL);
213 
214  mincut_termsepasFree(scip, &termsepas);
215 
216  stptest_graphTearDown(scip, graph);
217 
218  return SCIP_OKAY;
219 }
220 
221 
222 /** tests biconnected components method */
223 static
224 SCIP_RETCODE testBiconnectedComponentsAreFound(
225  SCIP* scip /**< SCIP data structure */
226 )
227 {
228  GRAPH* graph;
229  int nnodes = 8;
230  int nedges = 24;
231  int nelims = 0;
232  SCIP_Real offset = 0.0;
233 
234  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
235 
236  for( int i = 0; i < nnodes; i++ )
237  graph_knot_add(graph, STP_TERM_NONE);
238 
239  graph_knot_chg(graph, 1, STP_TERM);
240  graph_knot_chg(graph, 4, STP_TERM);
241  graph_knot_chg(graph, 0, STP_TERM);
242  graph->source = 0;
243 
244  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
245  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
246  graph_edge_addBi(scip, graph, 0, 3, 1.0);
247  graph_edge_addBi(scip, graph, 1, 2, 1.0);
248  graph_edge_addBi(scip, graph, 2, 3, 1.0);
249  graph_edge_addBi(scip, graph, 2, 4, 1.0);
250  graph_edge_addBi(scip, graph, 3, 4, 1.0);
251  graph_edge_addBi(scip, graph, 4, 5, 1.0);
252  graph_edge_addBi(scip, graph, 4, 6, 1.0);
253  graph_edge_addBi(scip, graph, 5, 6, 1.0);
254  graph_edge_addBi(scip, graph, 5, 7, 1.0);
255  graph_edge_addBi(scip, graph, 6, 7, 1.0);
256 
257  SCIP_CALL( stptest_graphSetUp(scip, graph) );
258 
259  SCIP_CALL( reduce_articulations(scip, graph, &offset, &nelims) );
260 
261  STPTEST_ASSERT(graph->grad[5] == 0);
262  STPTEST_ASSERT(graph->grad[6] == 0);
263  STPTEST_ASSERT(graph->grad[7] == 0);
264 
265  stptest_graphTearDown(scip, graph);
266 
267  return SCIP_OKAY;
268 }
269 
270 
271 
272 /** tests biconnected components method */
273 static
274 SCIP_RETCODE testBiconnectedComponentsAreFound2(
275  SCIP* scip /**< SCIP data structure */
276 )
277 {
278  GRAPH* graph;
279  int nnodes = 11;
280  int nedges = 24;
281  int nelims = 0;
282  SCIP_Real offset = 0.0;
283 
284  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
285 
286  for( int i = 0; i < nnodes; i++ )
287  graph_knot_add(graph, STP_TERM_NONE);
288 
289  graph_knot_chg(graph, 1, STP_TERM);
290  graph_knot_chg(graph, 9, STP_TERM);
291  graph->source = 9;
292 
293  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
294  graph_edge_addBi(scip, graph, 1, 2, 1.0); // 2
295  graph_edge_addBi(scip, graph, 1, 3, 1.0);
296  graph_edge_addBi(scip, graph, 1, 5, 1.0);
297  graph_edge_addBi(scip, graph, 2, 6, 1.0);
298  graph_edge_addBi(scip, graph, 5, 4, 1.0);
299  graph_edge_addBi(scip, graph, 3, 4, 1.0);
300 
301  graph_edge_addBi(scip, graph, 0, 7, 1.0);
302  graph_edge_addBi(scip, graph, 7, 8, 1.0);
303  graph_edge_addBi(scip, graph, 8, 10, 1.0);
304  graph_edge_addBi(scip, graph, 8, 9, 1.0);
305  graph_edge_addBi(scip, graph, 9, 10, 1.0);
306 
307  SCIP_CALL( stptest_graphSetUp(scip, graph) );
308 
309  SCIP_CALL( reduce_articulations(scip, graph, &offset, &nelims) );
310 
311  STPTEST_ASSERT(graph->grad[2] == 0);
312  STPTEST_ASSERT(graph->grad[3] == 0);
313  STPTEST_ASSERT(graph->grad[4] == 0);
314  STPTEST_ASSERT(graph->grad[5] == 0);
315  STPTEST_ASSERT(graph->grad[6] == 0);
316  STPTEST_ASSERT(Is_term(graph->term[0]));
317  STPTEST_ASSERT(Is_term(graph->term[7]));
318  STPTEST_ASSERT(Is_term(graph->term[8]));
319 
320  stptest_graphTearDown(scip, graph);
321 
322  return SCIP_OKAY;
323 }
324 
325 
326 
327 
328 
329 /** tests biconnected components method */
330 static
331 SCIP_RETCODE testBiconnectedComponentsAreFound3(
332  SCIP* scip /**< SCIP data structure */
333 )
334 {
335  GRAPH* graph;
336  int nnodes = 7;
337  int nedges = 16;
338  int nelims = 0;
339  SCIP_Real offset = 0.0;
340 
341  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
342 
343  for( int i = 0; i < nnodes; i++ )
344  graph_knot_add(graph, STP_TERM_NONE);
345 
346  graph_knot_chg(graph, 5, STP_TERM);
347  graph_knot_chg(graph, 2, STP_TERM);
348  graph->source = 2;
349 
350  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
351  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
352  graph_edge_addBi(scip, graph, 0, 3, 1.0);
353  graph_edge_addBi(scip, graph, 0, 4, 1.0);
354  graph_edge_addBi(scip, graph, 3, 4, 1.0);
355  graph_edge_addBi(scip, graph, 4, 5, 1.0);
356  graph_edge_addBi(scip, graph, 4, 6, 1.0);
357  graph_edge_addBi(scip, graph, 5, 6, 1.0);
358 
359  SCIP_CALL( stptest_graphSetUp(scip, graph) );
360 
361  SCIP_CALL( reduce_articulations(scip, graph, &offset, &nelims) );
362 
363  STPTEST_ASSERT(graph->grad[1] == 0);
364  STPTEST_ASSERT(Is_term(graph->term[0]));
365  STPTEST_ASSERT(Is_term(graph->term[4]));
366 
367  stptest_graphTearDown(scip, graph);
368 
369  return SCIP_OKAY;
370 }
371 
372 
373 
374 /** tests biconnected components method */
375 static
376 SCIP_RETCODE testBiconnectedDecomposition(
377  SCIP* scip /**< SCIP data structure */
378 )
379 {
380  REDBASE* redbase;
381  GRAPH* graph;
382  int nnodes = 8;
383  int nedges = 22;
384  SCIP_Real obj = 0.0;
385  SCIP_Bool wasDecomposed;
386 
387  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
388 
389  for( int i = 0; i < nnodes; i++ )
390  graph_knot_add(graph, STP_TERM_NONE);
391 
392  graph_knot_chg(graph, 1, STP_TERM);
393  graph_knot_chg(graph, 4, STP_TERM);
394  graph_knot_chg(graph, 0, STP_TERM);
395  graph_knot_chg(graph, 6, STP_TERM);
396 
397  graph->source = 0;
398 
399  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
400  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
401  graph_edge_addBi(scip, graph, 0, 3, 1.0);
402  graph_edge_addBi(scip, graph, 1, 2, 1.0);
403  graph_edge_addBi(scip, graph, 2, 3, 1.0);
404  graph_edge_addBi(scip, graph, 2, 4, 1.0);
405  graph_edge_addBi(scip, graph, 3, 4, 1.0);
406  graph_edge_addBi(scip, graph, 4, 5, 1.0);
407  // graph_edge_addBi(scip, graph, 4, 6, 1.0);
408  graph_edge_addBi(scip, graph, 5, 6, 1.0);
409  graph_edge_addBi(scip, graph, 5, 7, 1.0);
410  graph_edge_addBi(scip, graph, 6, 7, 1.0);
411 
412  SCIP_CALL( stptest_graphSetUp(scip, graph) );
413 
414 
415  SCIP_CALL( reduce_baseInit(scip, graph, &redbase) );
416 
417  {
418  BIDECPARAMS decparameters = { .depth = 0, .maxdepth = 2, .newLevelStarted = FALSE };
419  RPARAMS parameters = { .dualascent = 1, .boundreduce = 1, .nodereplacing = 1, .reductbound_min = 10,
420  .reductbound = 10, .userec = 1, .fullreduce = 1, .usestrongreds = TRUE };
421  redbase->redparameters = &parameters;
422  redbase->bidecompparams = &decparameters;
423  graph->stp_type = STP_SPG;
424 
425  SCIP_CALL( reduce_solInit(scip, graph, TRUE, &(redbase->redsol)) );
426  SCIP_CALL( reduce_solInitLocal(scip, graph, redbase->redsol, NULL));
427 
428  SCIP_CALL( reduce_bidecomposition(scip, graph, redbase, NULL, &wasDecomposed) );
429 
430  reduce_solFinalizeLocal(scip, graph, redbase->redsol);
431  }
432 
433  obj = reduce_solGetUpperBoundWithOffset(redbase->redsol);
434  reduce_solFree(scip, &(redbase->redsol));
435  reduce_baseFree(scip, &redbase);
436 
437  STPTEST_ASSERT(graph->terms == 1);
438  STPTEST_ASSERT(EQ(obj, 5.0));
439  stptest_graphTearDown(scip, graph);
440 
441  return SCIP_OKAY;
442 }
443 
444 
445 /** tests biconnected decomposition method */
446 static
447 SCIP_RETCODE testBiconnectedDecomposition2(
448  SCIP* scip /**< SCIP data structure */
449 )
450 {
451  REDBASE* redbase;
452  GRAPH* graph;
453  int nnodes = 11;
454  int nedges = 24;
455  SCIP_Real obj = 0.0;
456  SCIP_Bool wasDecomposed;
457 
458  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
459 
460  for( int i = 0; i < nnodes; i++ )
461  graph_knot_add(graph, STP_TERM_NONE);
462 
463  graph_knot_chg(graph, 1, STP_TERM);
464  graph_knot_chg(graph, 9, STP_TERM);
465  graph->source = 9;
466 
467  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
468  graph_edge_addBi(scip, graph, 1, 2, 1.0); // 2
469  graph_edge_addBi(scip, graph, 1, 3, 1.0);
470  graph_edge_addBi(scip, graph, 1, 5, 1.0);
471  graph_edge_addBi(scip, graph, 2, 6, 1.0);
472  graph_edge_addBi(scip, graph, 5, 4, 1.0);
473  graph_edge_addBi(scip, graph, 3, 4, 1.0);
474 
475  graph_edge_addBi(scip, graph, 0, 7, 1.0);
476  graph_edge_addBi(scip, graph, 7, 8, 1.0);
477  graph_edge_addBi(scip, graph, 8, 10, 1.0);
478  graph_edge_addBi(scip, graph, 8, 9, 1.0);
479  graph_edge_addBi(scip, graph, 9, 10, 1.0);
480 
481  SCIP_CALL( stptest_graphSetUp(scip, graph) );
482 
483  SCIP_CALL( reduce_baseInit(scip, graph, &redbase) );
484 
485  {
486  BIDECPARAMS decparameters = { .depth = 0, .maxdepth = 2, .newLevelStarted = FALSE };
487  RPARAMS parameters = { .dualascent = 1, .boundreduce = 1, .nodereplacing = 1, .reductbound_min = 10,
488  .reductbound = 10, .userec = 1, .fullreduce = 1, .usestrongreds = TRUE };
489  redbase->redparameters = &parameters;
490  redbase->bidecompparams = &decparameters;
491  graph->stp_type = STP_SPG;
492 
493  SCIP_CALL( reduce_solInit(scip, graph, TRUE, &(redbase->redsol)) );
494  SCIP_CALL( reduce_solInitLocal(scip, graph, redbase->redsol, NULL));
495 
496  SCIP_CALL( reduce_bidecomposition(scip, graph, redbase, NULL, &wasDecomposed) );
497 
498  reduce_solFinalizeLocal(scip, graph, redbase->redsol);
499  }
500 
501  obj = reduce_solGetUpperBoundWithOffset(redbase->redsol);
502  reduce_solFree(scip, &(redbase->redsol));
503  reduce_baseFree(scip, &redbase);
504 
505  STPTEST_ASSERT(graph->terms == 1);
506  STPTEST_ASSERT(EQ(obj, 4.0));
507 
508  stptest_graphTearDown(scip, graph);
509 
510  return SCIP_OKAY;
511 }
512 
513 /** tests biconnected decomposition method */
514 static
515 SCIP_RETCODE testBiconnectedDecomposition3(
516  SCIP* scip /**< SCIP data structure */
517 )
518 {
519  GRAPH* graph;
520  int nnodes = 7;
521  int nedges = 16;
522  SCIP_Real obj = 0.0;
523  REDBASE* redbase;
524  SCIP_Bool wasDecomposed;
525 
526  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
527 
528  for( int i = 0; i < nnodes; i++ )
529  graph_knot_add(graph, STP_TERM_NONE);
530 
531  graph_knot_chg(graph, 5, STP_TERM);
532  graph_knot_chg(graph, 2, STP_TERM);
533  graph->source = 2;
534 
535  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
536  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
537  graph_edge_addBi(scip, graph, 0, 3, 1.0);
538  graph_edge_addBi(scip, graph, 0, 4, 1.0);
539  graph_edge_addBi(scip, graph, 3, 4, 1.0);
540  graph_edge_addBi(scip, graph, 4, 5, 1.0);
541  graph_edge_addBi(scip, graph, 4, 6, 1.0);
542  graph_edge_addBi(scip, graph, 5, 6, 1.0);
543 
544  SCIP_CALL( stptest_graphSetUp(scip, graph) );
545 
546  SCIP_CALL( reduce_baseInit(scip, graph, &redbase) );
547 
548  {
549  BIDECPARAMS decparameters = { .depth = 0, .maxdepth = 2, .newLevelStarted = FALSE };
550  RPARAMS parameters = { .dualascent = 1, .boundreduce = 1, .nodereplacing = 1,
551  .reductbound_min = 10, .reductbound = 10, .userec = 1, .fullreduce = 1, .usestrongreds = TRUE };
552  redbase->redparameters = &parameters;
553  redbase->bidecompparams = &decparameters;
554  graph->stp_type = STP_SPG;
555 
556  SCIP_CALL( reduce_solInit(scip, graph, TRUE, &(redbase->redsol)) );
557  SCIP_CALL( reduce_solInitLocal(scip, graph, redbase->redsol, NULL));
558 
559  SCIP_CALL( reduce_bidecomposition(scip, graph, redbase, NULL, &wasDecomposed) );
560 
561  reduce_solFinalizeLocal(scip, graph, redbase->redsol);
562  }
563 
564  obj = reduce_solGetUpperBoundWithOffset(redbase->redsol);
565  reduce_solFree(scip, &(redbase->redsol));
566  reduce_baseFree(scip, &redbase);
567 
568  STPTEST_ASSERT(graph->terms == 1);
569  STPTEST_ASSERT(EQ(obj, 3.0));
570 
571  stptest_graphTearDown(scip, graph);
572 
573  return SCIP_OKAY;
574 }
575 
576 /** tests simple cut nodes methods */
577 SCIP_RETCODE stptest_reduceBiconnected(
578  SCIP* scip /**< SCIP data structure */
579 )
580 {
581  SCIP_CALL( testTerminalSeparatorsAreFound(scip) );
582  SCIP_CALL( testTerminalSeparatorsAreFound3(scip) );
583  SCIP_CALL( testTerminalSeparatorsAreFound2(scip) );
584 
585  SCIP_CALL( testBiconnectedDecomposition(scip) );
586  SCIP_CALL( testBiconnectedDecomposition2(scip) );
587  SCIP_CALL( testBiconnectedDecomposition3(scip) );
588 
589  SCIP_CALL( testBiconnectedComponentsAreFound(scip) );
590  SCIP_CALL( testBiconnectedComponentsAreFound2(scip) );
591  SCIP_CALL( testBiconnectedComponentsAreFound3(scip) );
592 
593  printf("reduce biconnected test: all ok \n");
594 
595 
596  return SCIP_OKAY;
597 }
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
testTerminalSeparatorsAreFound2
static SCIP_RETCODE testTerminalSeparatorsAreFound2(SCIP *scip)
Definition: stptest_reducesepa.c:93
STPTEST_ASSERT
#define STPTEST_ASSERT(cond)
Definition: stptest.h:63
GRAPH::source
int source
Definition: graphdefs.h:195
Is_term
#define Is_term(a)
Definition: graphdefs.h:102
graph_edge_addBi
void graph_edge_addBi(SCIP *, GRAPH *, int, int, double)
testBiconnectedComponentsAreFound3
static SCIP_RETCODE testBiconnectedComponentsAreFound3(SCIP *scip)
Definition: stptest_reducesepa.c:331
reduce_solInit
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
reduce_solFinalizeLocal
void reduce_solFinalizeLocal(SCIP *, const GRAPH *, REDSOL *)
Definition: reduce_sol.c:735
GRAPH::terms
int terms
Definition: graphdefs.h:192
FALSE
#define FALSE
Definition: def.h:87
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
STP_SPG
#define STP_SPG
Definition: graphdefs.h:42
reduction_base
Definition: reducedefs.h:100
mincut_termsepasGetNall
int mincut_termsepasGetNall(const TERMSEPAS *termsepas)
Definition: mincut.c:2135
reduce_solGetUpperBoundWithOffset
SCIP_Real reduce_solGetUpperBoundWithOffset(const REDSOL *)
Definition: reduce_sol.c:1263
reduce_solInitLocal
SCIP_RETCODE reduce_solInitLocal(SCIP *, const GRAPH *, REDSOL *, REDSOLLOCAL **)
Definition: reduce_sol.c:717
stptest_reduceBiconnected
SCIP_RETCODE stptest_reduceBiconnected(SCIP *scip)
Definition: stptest_reducesepa.c:577
STP_TERM_NONE
#define STP_TERM_NONE
Definition: graphdefs.h:62
testBiconnectedDecomposition2
static SCIP_RETCODE testBiconnectedDecomposition2(SCIP *scip)
Definition: stptest_reducesepa.c:447
bidecomposition_reduction_parameters::depth
int depth
Definition: reducedefs.h:93
testTerminalSeparatorsAreFound3
static SCIP_RETCODE testTerminalSeparatorsAreFound3(SCIP *scip)
Definition: stptest_reducesepa.c:162
GRAPH::stp_type
int stp_type
Definition: graphdefs.h:264
mincut_findTerminalSeparators
SCIP_RETCODE mincut_findTerminalSeparators(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, GRAPH *g, TERMSEPAS *termsepas)
Definition: mincut.c:2274
GRAPH::grad
int *RESTRICT grad
Definition: graphdefs.h:201
reduction_parameters::dualascent
SCIP_Bool dualascent
Definition: reducedefs.h:77
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
NULL
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_OKAY
Definition: type_retcode.h:33
EQ
#define EQ(a, b)
Definition: portab.h:79
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:384
reduction_parameters
Definition: reducedefs.h:75
reduce_solFree
void reduce_solFree(SCIP *, REDSOL **)
Definition: reduce_sol.c:818
testBiconnectedDecomposition3
static SCIP_RETCODE testBiconnectedDecomposition3(SCIP *scip)
Definition: stptest_reducesepa.c:515
stptest_graphTearDown
void stptest_graphTearDown(SCIP *, GRAPH *)
Definition: stptest_graph.c:274
testBiconnectedComponentsAreFound2
static SCIP_RETCODE testBiconnectedComponentsAreFound2(SCIP *scip)
Definition: stptest_reducesepa.c:274
terminal_separator_storage
Definition: mincut.c:89
SCIP_Bool
#define SCIP_Bool
Definition: def.h:84
testTerminalSeparatorsAreFound
static SCIP_RETCODE testTerminalSeparatorsAreFound(SCIP *scip)
Definition: stptest_reducesepa.c:39
reduction_base::redsol
REDSOL * redsol
Definition: reducedefs.h:105
mincut_termsepasFree
void mincut_termsepasFree(SCIP *scip, TERMSEPAS **termsepas)
Definition: mincut.c:2113
STP_TERM
#define STP_TERM
Definition: graphdefs.h:61
testBiconnectedComponentsAreFound
static SCIP_RETCODE testBiconnectedComponentsAreFound(SCIP *scip)
Definition: stptest_reducesepa.c:224
GRAPH::term
int *RESTRICT term
Definition: graphdefs.h:196
portab.h
Portable definitions.
mincut_termsepasInit
SCIP_RETCODE mincut_termsepasInit(SCIP *scip, const GRAPH *g, int maxnsepas, int maxsepasize, TERMSEPAS **termsepas)
Definition: mincut.c:2074
bidecomposition_reduction_parameters
Definition: reducedefs.h:91
mincut_termsepasGetFirst
const int * mincut_termsepasGetFirst(int sepasize, TERMSEPAS *termsepas, int *sinkterm, int *nsinknodes)
Definition: mincut.c:2162
stptest.h
includes various testing methods for Steiner tree problems
stptest_graphSetUp
SCIP_RETCODE stptest_graphSetUp(SCIP *, GRAPH *)
Definition: stptest_graph.c:286
mincut_termsepasGetNext
const int * mincut_termsepasGetNext(int sepasize, TERMSEPAS *termsepas, int *sinkterm, int *nsinknodes)
Definition: mincut.c:2179
SCIP_Real
#define SCIP_Real
Definition: def.h:177
reduce_baseFree
void reduce_baseFree(SCIP *, REDBASE **)
Definition: reduce_base.c:1155
reduction_base::bidecompparams
BIDECPARAMS * bidecompparams
Definition: reducedefs.h:103
reduce_baseInit
SCIP_RETCODE reduce_baseInit(SCIP *, const GRAPH *, REDBASE **)
Definition: reduce_base.c:1120
reduction_base::redparameters
RPARAMS * redparameters
Definition: reducedefs.h:102
testBiconnectedDecomposition
static SCIP_RETCODE testBiconnectedDecomposition(SCIP *scip)
Definition: stptest_reducesepa.c:376
nnodes
#define nnodes
Definition: gastrans.c:65
reduce_bidecomposition
SCIP_RETCODE reduce_bidecomposition(SCIP *, GRAPH *, REDBASE *, int *, SCIP_Bool *)
Definition: reduce_sepa.c:1039
graph_init
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
reduce_articulations
SCIP_RETCODE reduce_articulations(SCIP *, GRAPH *, SCIP_Real *, int *)
Definition: reduce_sepa.c:1130
mincut.h
Minimum cut routines for Steiner problems.
reduce.h
includes various reduction methods for Steiner tree problems