Scippy

SCIP

Solving Constraint Integer Programs

stptest_reducesd.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_reducesd.c
17  * @brief tests for Steiner tree reductions
18  * @author Daniel Rehfeldt
19  *
20  * This file implements unit tests for Steiner special distance (Steiner bottleneck distance) 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 
35 
36 
37 
38 /** tests SD getter */
39 static
40 SCIP_RETCODE testSdGetterReturnsCorrectSds(
41  SCIP* scip /**< SCIP data structure */
42 )
43 {
44  SD* sddata;
45  GRAPH* graph;
46  GRAPH* cliquegraph;
47  DIJK* dijkdata;
48  int nnodes = 7;
49  int nedges = 16;
50  int cliqueNodeMap[] = { 3,4,5,6 };
51 
52  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
53 
54  for( int i = 0; i < nnodes; i++ )
55  graph_knot_add(graph, STP_TERM_NONE);
56 
57  graph_knot_chg(graph, 0, STP_TERM);
58  graph_knot_chg(graph, 1, STP_TERM);
59  graph_knot_chg(graph, 2, STP_TERM);
60  graph->source = 0;
61 
62  graph_edge_addBi(scip, graph, 0, 1, 3.0); // 0
63  graph_edge_addBi(scip, graph, 1, 2, 2.0); // 2
64 
65  graph_edge_addBi(scip, graph, 3, 0, 1.0); // 4
66  graph_edge_addBi(scip, graph, 4, 0, 1.0); // 6
67  graph_edge_addBi(scip, graph, 4, 1, 2.0); // 8
68  graph_edge_addBi(scip, graph, 5, 1, 4.0); // 10
69  graph_edge_addBi(scip, graph, 6, 1, 4.0); // 12
70  graph_edge_addBi(scip, graph, 6, 2, 2.0); // 14
71 
72  SCIP_CALL( stptest_graphSetUp(scip, graph) );
73 
74  SCIP_CALL( graph_buildCompleteGraph(scip, &cliquegraph, 4) );
75  SCIP_CALL( graph_path_init(scip, cliquegraph) );
76  for( int i = 0; i < 4; i++ )
77  cliquegraph->mark[i] = TRUE;
78 
79  SCIP_CALL( reduce_sdInit(scip, graph, &sddata) );
80 
81  SCIP_CALL( graph_dijkLimited_init(scip, graph, &(dijkdata)) );
82  graph_dijkLimited_clean(graph, dijkdata);
83  dijkdata->edgelimit = 500;
84 
85  SCIP_CALL( reduce_sdGetSdsCliquegraph(scip, graph, -1, cliqueNodeMap, dijkdata, sddata, cliquegraph) );
86 
87  for( int e = cliquegraph->outbeg[0]; e != EAT_LAST; e = cliquegraph->oeat[e] )
88  {
89  const int head = cliquegraph->head[e];
90  const SCIP_Real cost = cliquegraph->cost[e];
91  if( head == 1 )
92  {
93  STPTEST_ASSERT(EQ(cost, 1.0));
94  }
95 
96  if( head == 2 )
97  {
98  STPTEST_ASSERT(EQ(cost, 3.0));
99  }
100 
101  if( head == 3 )
102  {
103  STPTEST_ASSERT(EQ(cost, 3.0));
104  }
105  }
106 
107  for( int e = cliquegraph->outbeg[1]; e != EAT_LAST; e = cliquegraph->oeat[e] )
108  {
109  const int head = cliquegraph->head[e];
110  const SCIP_Real cost = cliquegraph->cost[e];
111  if( head == 0 )
112  {
113  STPTEST_ASSERT(EQ(cost, 1.0));
114  }
115 
116  if( head == 2 )
117  {
118  STPTEST_ASSERT(EQ(cost, 3.0));
119  }
120 
121  if( head == 3 )
122  {
123  STPTEST_ASSERT(EQ(cost, 2.0));
124  }
125  }
126 
127  graph_dijkLimited_free(scip, &(dijkdata));
128  reduce_sdFree(scip, &sddata);
129  stptest_graphTearDown(scip, cliquegraph);
130  stptest_graphTearDown(scip, graph);
131 
132 
133  return SCIP_OKAY;
134 }
135 
136 
137 
138 /** tests SD getter */
139 static
140 SCIP_RETCODE testSdGraphDistsAreValid(
141  SCIP* scip /**< SCIP data structure */
142 )
143 {
144  GRAPH* graph;
145  SD* sddata;
146  int nnodes = 5;
147  int nedges = 8;
148  const SCIP_Real* sddists;
149 
150  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
151 
152  for( int i = 0; i < nnodes; i++ )
153  graph_knot_add(graph, STP_TERM_NONE);
154 
155  graph_knot_chg(graph, 1, STP_TERM);
156  graph_knot_chg(graph, 2, STP_TERM);
157  graph_knot_chg(graph, 3, STP_TERM);
158  graph->source = 1;
159 
160  graph_edge_addBi(scip, graph, 0, 1, 1.9); // 0
161  graph_edge_addBi(scip, graph, 0, 2, 2.0); // 2
162  graph_edge_addBi(scip, graph, 0, 3, 2.0); // 4
163  graph_edge_addBi(scip, graph, 1, 4, 1.0); // 4
164 
165 
166  SCIP_CALL( stptest_graphSetUp(scip, graph) );
167 
168  SCIP_CALL( reduce_sdInitBiased(scip, graph, &(sddata)) );
169  reduce_sdgraphInitOrderedMstCosts(sddata->sdgraph);
170 
171  sddists = reduce_sdgraphGetOrderedMstCosts(sddata->sdgraph);
172 
173 
174  STPTEST_ASSERT(EQ(sddists[0], 2.0));
175  STPTEST_ASSERT(EQ(sddists[1], 2.0));
176 
177  reduce_sdFree(scip, &sddata);
178  stptest_graphTearDown(scip, graph);
179 
180  return SCIP_OKAY;
181 }
182 
183 
184 
185 /** tests SD getter */
186 static
187 SCIP_RETCODE testSdGraphDistsAreValid2(
188  SCIP* scip /**< SCIP data structure */
189 )
190 {
191  GRAPH* graph;
192  SD* sddata;
193  int nnodes = 5;
194  int nedges = 10;
195  const SCIP_Real* sddists;
196 
197  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
198 
199  for( int i = 0; i < nnodes; i++ )
200  graph_knot_add(graph, STP_TERM_NONE);
201 
202  graph_knot_chg(graph, 1, STP_TERM);
203  graph_knot_chg(graph, 2, STP_TERM);
204  graph_knot_chg(graph, 3, STP_TERM);
205  graph_knot_chg(graph, 4, STP_TERM);
206 
207  graph->source = 1;
208 
209  graph_edge_addBi(scip, graph, 0, 1, 2.0); // 0
210  graph_edge_addBi(scip, graph, 0, 2, 2.0); // 2
211  graph_edge_addBi(scip, graph, 0, 3, 2.0); // 4
212  graph_edge_addBi(scip, graph, 2, 4, 3.5);
213  graph_edge_addBi(scip, graph, 3, 4, 2.0);
214 
215  SCIP_CALL( stptest_graphSetUp(scip, graph) );
216 
217  SCIP_CALL( reduce_sdInitBiased(scip, graph, &sddata) );
218  reduce_sdgraphInitOrderedMstCosts(sddata->sdgraph);
219 
220  sddists = reduce_sdgraphGetOrderedMstCosts(sddata->sdgraph);
221 
222  STPTEST_ASSERT(EQ(sddists[0], 3.5));
223  STPTEST_ASSERT(EQ(sddists[1], 2.5));
224 
225  reduce_sdFree(scip, &sddata);
226  stptest_graphTearDown(scip, graph);
227 
228  return SCIP_OKAY;
229 }
230 
231 
232 /** tests SD queries */
233 static
234 SCIP_RETCODE testSdGraphQueriesAreValid(
235  SCIP* scip /**< SCIP data structure */
236 )
237 {
238  GRAPH* graph;
239  SD* sddata;
240  SDGRAPH* sdgraph;
241  int nnodes = 9;
242  int nedges = 16;
243 
244  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
245 
246  for( int i = 0; i < nnodes; i++ )
247  graph_knot_add(graph, STP_TERM);
248 
249  graph->source = 0;
250 
251  graph_edge_addBi(scip, graph, 0, 1, 7.0); // 0
252  graph_edge_addBi(scip, graph, 0, 3, 8.0); // 2
253  graph_edge_addBi(scip, graph, 0, 4, 9.0);
254  graph_edge_addBi(scip, graph, 0, 5, 66.0);
255  graph_edge_addBi(scip, graph, 1, 2, 7.5);
256  graph_edge_addBi(scip, graph, 5, 6, 3.0);
257  graph_edge_addBi(scip, graph, 5, 7, 12.0);
258  graph_edge_addBi(scip, graph, 7, 8, 11.0);
259 
260  SCIP_CALL( stptest_graphSetUp(scip, graph) );
261  SCIP_CALL( reduce_sdInit(scip, graph, &sddata) );
262 
263  sdgraph = sddata->sdgraph;
264  reduce_sdgraphInitOrderedMstCosts(sdgraph);
265 
266  STPTEST_ASSERT(EQ(reduce_sdgraphGetSd(0, 1, sdgraph), 7.0));
267  STPTEST_ASSERT(EQ(reduce_sdgraphGetSd(0, 2, sdgraph), 7.5));
268  STPTEST_ASSERT(EQ(reduce_sdgraphGetSd(0, 3, sdgraph), 8.0));
269  STPTEST_ASSERT(EQ(reduce_sdgraphGetSd(8, 4, sdgraph), 66.0));
270  STPTEST_ASSERT(EQ(reduce_sdgraphGetSd(8, 6, sdgraph), 12.0));
271  STPTEST_ASSERT(EQ(reduce_sdgraphGetSd(3, 2, sdgraph), 8.0));
272 
273  reduce_sdFree(scip, &sddata);
274  stptest_graphTearDown(scip, graph);
275 
276  return SCIP_OKAY;
277 }
278 
279 
280 /** tests SD getter */
281 static
282 SCIP_RETCODE testSdGraphStrongBiasedDistsAreValid(
283  SCIP* scip /**< SCIP data structure */
284 )
285 {
286  GRAPH* graph;
287  SDPROFIT* sdprofit;
288  TPATHS* tpaths;
289  SDGRAPH* sdgraph;
290  int nnodes = 5;
291  int nedges = 8;
292  const SCIP_Real* sddists;
293 
294  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
295 
296  for( int i = 0; i < nnodes; i++ )
297  graph_knot_add(graph, STP_TERM_NONE);
298 
299  graph_knot_chg(graph, 1, STP_TERM);
300  graph_knot_chg(graph, 2, STP_TERM);
301  graph_knot_chg(graph, 3, STP_TERM);
302  graph->source = 1;
303 
304  graph_edge_addBi(scip, graph, 0, 1, 2.0); // 0
305  graph_edge_addBi(scip, graph, 0, 2, 1.9); // 2
306  graph_edge_addBi(scip, graph, 0, 3, 2.0); // 4
307  graph_edge_addBi(scip, graph, 1, 4, 2.0); // 4
308 
309  SCIP_CALL( stptest_graphSetUp(scip, graph) );
310 
311  SCIP_CALL( reduce_sdprofitInit(scip, graph, &(sdprofit)) );
312  SCIP_CALL( graph_tpathsInitBiased(scip, sdprofit, graph, &(tpaths)) );
313  SCIP_CALL( reduce_sdgraphInitBiasedFromTpaths(scip, graph, sdprofit, tpaths, &(sdgraph)) );
314 
315  reduce_sdgraphInitOrderedMstCosts(sdgraph);
316 
317  sddists = reduce_sdgraphGetOrderedMstCosts(sdgraph);
318 
319  STPTEST_ASSERT(EQ(sddists[0], 2.0));
320  STPTEST_ASSERT(EQ(sddists[1], 2.0));
321 
322  reduce_sdgraphFree(scip, &(sdgraph));
323  graph_tpathsFree(scip, &(tpaths));
324  reduce_sdprofitFree(scip, &(sdprofit));
325 
326  stptest_graphTearDown(scip, graph);
327 
328  return SCIP_OKAY;
329 }
330 
331 
332 /** tests that BDk test pseudo-eliminates node of degree 4 */
333 static
334 SCIP_RETCODE testBdkTreeDistDeletesNodeDeg4(
335  SCIP* scip /**< SCIP data structure */
336 )
337 {
338  GRAPH* graph;
339  int nnodes = 7;
340  int nedges = 12;
341  int nelims = 0;
342 
343  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
344 
345  for( int i = 0; i < nnodes; i++ )
346  graph_knot_add(graph, STP_TERM_NONE);
347 
348  graph_knot_chg(graph, 1, STP_TERM);
349  graph_knot_chg(graph, 2, STP_TERM);
350  graph_knot_chg(graph, 5, STP_TERM);
351  graph_knot_chg(graph, 6, STP_TERM);
352  graph->source = 1;
353 
354  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
355  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
356  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
357 
358  graph_edge_addBi(scip, graph, 0, 4, 1.1); // 6
359  graph_edge_addBi(scip, graph, 1, 5, 1.0); // 8
360  graph_edge_addBi(scip, graph, 5, 6, 1.0); // 10
361 
362  SCIP_CALL( stptest_graphSetUp(scip, graph) );
363  SCIP_CALL( reduce_bdk(scip, 100, graph, &nelims) );
364 
365  STPTEST_ASSERT(nelims == 1);
366  STPTEST_ASSERT(graph->grad[0] == 0);
367 
368  stptest_graphTearDown(scip, graph);
369 
370  return SCIP_OKAY;
371 }
372 
373 
374 /** tests that BDk test pseudo-eliminates node of degree 4 */
375 static
376 SCIP_RETCODE testBdkSdMstDeletesNodeDeg4(
377  SCIP* scip /**< SCIP data structure */
378 )
379 {
380  GRAPH* graph;
381  int nnodes = 8;
382  int nedges = 20;
383  int nelims = 0;
384 
385  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
386 
387  for( int i = 0; i < nnodes; i++ )
388  graph_knot_add(graph, STP_TERM_NONE);
389 
390  graph_knot_chg(graph, 1, STP_TERM);
391  graph_knot_chg(graph, 5, STP_TERM);
392  graph_knot_chg(graph, 6, STP_TERM);
393  graph_knot_chg(graph, 7, STP_TERM);
394 
395  graph->source = 5;
396 
397  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
398  graph_edge_addBi(scip, graph, 0, 2, 2.0); // 2
399  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
400  graph_edge_addBi(scip, graph, 0, 4, 1.0); // 6
401 
402  graph_edge_addBi(scip, graph, 1, 5, 1.0); // 8
403  graph_edge_addBi(scip, graph, 3, 5, 1.0); // 10
404  graph_edge_addBi(scip, graph, 3, 6, 1.0); // 14
405  graph_edge_addBi(scip, graph, 4, 6, 1.0); // 14
406  graph_edge_addBi(scip, graph, 3, 7, 1.0); // 14
407 
408 
409  SCIP_CALL( stptest_graphSetUp(scip, graph) );
410  SCIP_CALL( reduce_bdk(scip, 100, graph, &nelims) );
411 
412  STPTEST_ASSERT(nelims == 1);
413  STPTEST_ASSERT(graph->grad[0] == 0);
414 
415  stptest_graphTearDown(scip, graph);
416 
417  return SCIP_OKAY;
418 }
419 
420 
421 
422 /** tests that BDk test pseudo-eliminates node of degree 4 */
423 static
424 SCIP_RETCODE testBdkSdMstStarDeletesNodeDeg4(
425  SCIP* scip /**< SCIP data structure */
426 )
427 {
428  GRAPH* graph;
429  int nnodes = 9;
430  int nedges = 22;
431  int nelims = 0;
432 
433  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
434 
435  for( int i = 0; i < nnodes; i++ )
436  graph_knot_add(graph, STP_TERM_NONE);
437 
438  graph_knot_chg(graph, 1, STP_TERM);
439  graph_knot_chg(graph, 6, STP_TERM);
440  graph_knot_chg(graph, 7, STP_TERM);
441  graph_knot_chg(graph, 8, STP_TERM);
442 
443 
444  graph->source = 1;
445 
446  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
447  graph_edge_addBi(scip, graph, 0, 2, 2.0); // 2
448  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
449  graph_edge_addBi(scip, graph, 0, 4, 1.0); // 6
450 
451  graph_edge_addBi(scip, graph, 1, 5, 0.5); // 8
452  graph_edge_addBi(scip, graph, 3, 5, 0.5); // 10
453  graph_edge_addBi(scip, graph, 3, 6, 1.0); //
454  graph_edge_addBi(scip, graph, 4, 6, 1.0); //
455  graph_edge_addBi(scip, graph, 3, 7, 1.0); //
456  graph_edge_addBi(scip, graph, 7, 8, 1.0); //
457 
458 
459  SCIP_CALL( stptest_graphSetUp(scip, graph) );
460  SCIP_CALL( reduce_bdk(scip, 100, graph, &nelims) );
461 
462  STPTEST_ASSERT(nelims == 1);
463  STPTEST_ASSERT(graph->grad[0] == 0);
464 
465  stptest_graphTearDown(scip, graph);
466 
467 
468  return SCIP_OKAY;
469 }
470 
471 
472 #if 0
473 /** tests that BDk test fully eliminates edge */
474 static
475 SCIP_RETCODE testBdkDeletesEdge(
476  SCIP* scip /**< SCIP data structure */
477 )
478 {
479  GRAPH* graph;
480  int nnodes = 6;
481  int nedges = 16;
482  int nelims = 0;
483 
484  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
485 
486  graph_knot_add(graph, STP_TERM_NONE);
487  for( int i = 1; i < nnodes; i++ )
488  graph_knot_add(graph, STP_TERM);
489 
490  graph->source = 3;
491 
492  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
493  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
494  graph_edge_addBi(scip, graph, 0, 3, 0.1); // 4
495  graph_edge_addBi(scip, graph, 0, 4, 2.1); // 6
496 
497  graph_edge_addBi(scip, graph, 1, 2, 2.0);
498  graph_edge_addBi(scip, graph, 2, 3, 2.1);
499  graph_edge_addBi(scip, graph, 3, 4, 2.0);
500 
501  /* dummy */
502  graph_edge_addBi(scip, graph, 3, 5, 22.0);
503 
504 
505  SCIP_CALL( stptest_graphSetUp(scip, graph) );
506 
507  SCIP_CALL( reduce_bdk(scip, 100, graph, &nelims) );
508 
509  STPTEST_ASSERT(nelims == 1);
510  STPTEST_ASSERT(graph->grad[0] == 3);
511  STPTEST_ASSERT(graph->grad[4] == 1);
512 
513  stptest_graphTearDown(scip, graph);
514 
515  return SCIP_OKAY;
516 }
517 
518 /** tests that BDk test properly pseudo-eliminates edge, i.e adds new one */
519 static
520 SCIP_RETCODE testBdkReplacesEdge(
521  SCIP* scip /**< SCIP data structure */
522 )
523 {
524  GRAPH* graph;
525  int nnodes = 6;
526  int nedges = 16;
527  int nelims = 0;
528 
529  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
530 
531  graph_knot_add(graph, STP_TERM_NONE);
532  for( int i = 1; i < nnodes; i++ )
533  graph_knot_add(graph, STP_TERM);
534 
535  graph->source = 3;
536 
537  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
538  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
539  graph_edge_addBi(scip, graph, 0, 3, 0.1); // 4
540  graph_edge_addBi(scip, graph, 0, 4, 2.1); // 6
541 
542  graph_edge_addBi(scip, graph, 1, 2, 2.0);
543  graph_edge_addBi(scip, graph, 2, 3, 2.1);
544  graph_edge_addBi(scip, graph, 3, 4, 2.0);
545 
546  /* dummy */
547  graph_edge_addBi(scip, graph, 3, 5, 22.0);
548 
549 
550  SCIP_CALL( stptest_graphSetUp(scip, graph) );
551 
552  SCIP_CALL( reduce_bdk(scip, 100, graph, &nelims) );
553 
554  STPTEST_ASSERT(nelims == 1);
555  STPTEST_ASSERT(graph->grad[0] == 3);
556  STPTEST_ASSERT(graph->grad[4] == 1);
557 
558  stptest_graphTearDown(scip, graph);
559 
560  return SCIP_OKAY;
561 }
562 #endif
563 
564 /** tests that BDk test pseudo-eliminates node of degree 3 */
565 static
566 SCIP_RETCODE testBdkSdMstDeletesNodeDeg3(
567  SCIP* scip /**< SCIP data structure */
568 )
569 {
570  GRAPH* graph;
571  int nnodes = 7;
572  int nedges = 16;
573  int nelims = 0;
574 
575  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
576 
577  for( int i = 0; i < nnodes; i++ )
578  graph_knot_add(graph, STP_TERM_NONE);
579 
580  graph_knot_chg(graph, 4, STP_TERM);
581  graph_knot_chg(graph, 5, STP_TERM);
582  graph_knot_chg(graph, 6, STP_TERM);
583 
584  graph->source = 5;
585 
586  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
587  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
588  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
589 
590  graph_edge_addBi(scip, graph, 1, 4, 1.0);
591  graph_edge_addBi(scip, graph, 2, 5, 1.0);
592  graph_edge_addBi(scip, graph, 3, 4, 1.0);
593  graph_edge_addBi(scip, graph, 3, 6, 1.0);
594  graph_edge_addBi(scip, graph, 5, 6, 2.0);
595 
596 
597  SCIP_CALL( stptest_graphSetUp(scip, graph) );
598  SCIP_CALL( reduce_bdk(scip, 100, graph, &nelims) );
599 
600  STPTEST_ASSERT(graph->grad[0] == 0);
601 
602  stptest_graphTearDown(scip, graph);
603 
604  return SCIP_OKAY;
605 }
606 
607 
608 /** tests that SD star biased test finds edge for deletion */
609 static
610 SCIP_RETCODE testSdStarBiasedDeletesEdge(
611  SCIP* scip /**< SCIP data structure */
612 )
613 {
614  GRAPH* graph;
615  int nnodes = 5;
616  int nedges = 10;
617  int nelims = 0;
618 
619  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
620 
621  graph_knot_add(graph, STP_TERM);
622  for( int i = 1; i < nnodes; i++ )
623  graph_knot_add(graph, STP_TERM_NONE);
624 
625  graph->source = 0;
626 
627  graph_knot_chg(graph, 4, STP_TERM);
628 
629  graph_edge_addBi(scip, graph, 0, 1, 2.0); // 0
630  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
631  graph_edge_addBi(scip, graph, 1, 3, 1.0); // 4
632  graph_edge_addBi(scip, graph, 2, 3, 1.0); // 6
633  graph_edge_addBi(scip, graph, 3, 4, 1.0); // 6
634 
635  SCIP_CALL( stptest_graphSetUp(scip, graph) );
636 
637  SCIP_CALL( reduce_sdStarBiased(scip, 10, TRUE, graph, &nelims) );
638 
639  STPTEST_ASSERT(nelims == 1);
640  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
641 
642  stptest_graphTearDown(scip, graph);
643 
644  return SCIP_OKAY;
645 }
646 
647 /** tests that SD star biased test finds edge for deletion */
648 static
649 SCIP_RETCODE testSdStarBiasedDeletesEdge2(
650  SCIP* scip /**< SCIP data structure */
651 )
652 {
653  GRAPH* graph;
654  int nnodes = 6;
655  int nedges = 12;
656  int nelims = 0;
657 
658  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
659 
660  graph_knot_add(graph, STP_TERM);
661  for( int i = 1; i < nnodes; i++ )
662  graph_knot_add(graph, STP_TERM_NONE);
663 
664  graph->source = 0;
665 
666  graph_knot_chg(graph, 1, STP_TERM); /* not necessary ... */
667  graph_knot_chg(graph, 4, STP_TERM);
668 
669  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
670  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
671  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 2
672  graph_edge_addBi(scip, graph, 1, 2, 1.0);
673  graph_edge_addBi(scip, graph, 2, 4, 1.0);
674  graph_edge_addBi(scip, graph, 4, 5, 2.0);
675 
676  SCIP_CALL( stptest_graphSetUp(scip, graph) );
677 
678  SCIP_CALL( reduce_sdStarBiased(scip, 10, TRUE, graph, &nelims) );
679 
680  STPTEST_ASSERT(nelims == 1);
681  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
682 
683  stptest_graphTearDown(scip, graph);
684 
685  return SCIP_OKAY;
686 }
687 
688 
689 /** tests that SD star biased test finds edge for deletion */
690 static
691 SCIP_RETCODE testSdStarBiasedDeletesEdge3(
692  SCIP* scip /**< SCIP data structure */
693 )
694 {
695  GRAPH* graph;
696  int nnodes = 6;
697  int nedges = 14;
698  int nelims = 0;
699 
700  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
701 
702  for( int i = 0; i < nnodes; i++ )
703  graph_knot_add(graph, STP_TERM_NONE);
704 
705  graph->source = 4;
706 
707  graph_knot_chg(graph, 4, STP_TERM);
708  graph_knot_chg(graph, 5, STP_TERM);
709 
710  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
711  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
712  graph_edge_addBi(scip, graph, 1, 3, 1.0); // 2
713  graph_edge_addBi(scip, graph, 2, 3, 1.0);
714  graph_edge_addBi(scip, graph, 2, 4, 0.9);
715  graph_edge_addBi(scip, graph, 3, 5, 0.9);
716  graph_edge_addBi(scip, graph, 4, 5, 1.9);
717 
718  SCIP_CALL( stptest_graphSetUp(scip, graph) );
719 
720  SCIP_CALL( reduce_sdStarBiased(scip, 20, TRUE, graph, &nelims) );
721 
722  STPTEST_ASSERT(nelims == 1);
723  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
724 
725  stptest_graphTearDown(scip, graph);
726 
727  return SCIP_OKAY;
728 }
729 
730 
731 /** tests that SD star clique test finds edge for deletion */
732 static
733 SCIP_RETCODE testSdCliqueStarDeletesEdge(
734  SCIP* scip /**< SCIP data structure */
735 )
736 {
737  GRAPH* graph;
738  int nnodes = 6;
739  int nedges = 14;
740  int nelims = 0;
741 
742  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
743 
744  for( int i = 0; i < nnodes; i++ )
745  graph_knot_add(graph, STP_TERM_NONE);
746 
747  graph->source = 3;
748  graph_knot_chg(graph, 3, STP_TERM);
749  graph_knot_chg(graph, 4, STP_TERM);
750 
751  graph_edge_addBi(scip, graph, 0, 1, 1.5); // 0
752  graph_edge_addBi(scip, graph, 1, 2, 1.0); // 2
753  graph_edge_addBi(scip, graph, 2, 3, 1.0); // 4
754  graph_edge_addBi(scip, graph, 2, 5, 1.0);
755  graph_edge_addBi(scip, graph, 3, 4, 1.8);
756  graph_edge_addBi(scip, graph, 4, 5, 1.0);
757  graph_edge_addBi(scip, graph, 5, 0, 1.0);
758 
759  SCIP_CALL( stptest_graphSetUp(scip, graph) );
760 
761  SCIP_CALL( reduce_sdEdgeCliqueStar(scip, 20, graph, &nelims) );
762 
763  /* biased SD should be 1.4 */
764  STPTEST_ASSERT(nelims == 1);
765  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
766 
767  stptest_graphTearDown(scip, graph);
768 
769  return SCIP_OKAY;
770 }
771 
772 
773 /** tests that SD biased test finds edge for deletion */
774 static
775 SCIP_RETCODE testSdBiasedDeletesEdge(
776  SCIP* scip /**< SCIP data structure */
777 )
778 {
779  SD* sddata;
780  GRAPH* graph;
781  int nnodes = 6;
782  int nedges = 12;
783  int nelims = 0;
784 
785  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
786 
787  for( int i = 0; i < nnodes; i++ )
788  graph_knot_add(graph, STP_TERM_NONE);
789 
790  graph->source = 2;
791  graph_knot_chg(graph, 2, STP_TERM);
792  graph_knot_chg(graph, 4, STP_TERM);
793  graph_knot_chg(graph, 5, STP_TERM);
794 
795  graph_edge_addBi(scip, graph, 0, 1, 1.1); // 0
796  graph_edge_addBi(scip, graph, 1, 2, 1.0); // 2
797  graph_edge_addBi(scip, graph, 2, 3, 1.0); // 4
798  graph_edge_addBi(scip, graph, 3, 4, 1.0);
799  graph_edge_addBi(scip, graph, 3, 5, 1.0);
800  graph_edge_addBi(scip, graph, 5, 0, 1.0);
801 
802  SCIP_CALL( stptest_graphSetUp(scip, graph) );
803  SCIP_CALL( reduce_sdInitBiased(scip, graph, &sddata) );
804 
805  SCIP_CALL( reduce_sdBiased(scip, sddata, graph, &nelims) );
806 
807  STPTEST_ASSERT(nelims == 1);
808  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
809 
810  reduce_sdFree(scip, &sddata);
811  stptest_graphTearDown(scip, graph);
812 
813  return SCIP_OKAY;
814 }
815 
816 
817 #if 0
818 /** tests that SD biased neighbor test finds edge for deletion */
819 static
820 SCIP_RETCODE testSdBiasedNeighborDeletesEdge(
821  SCIP* scip /**< SCIP data structure */
822 )
823 {
824  SD* sddata;
825  GRAPH* graph;
826  int nnodes = 6;
827  int nedges = 16;
828  int nelims = 0;
829 
830  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
831 
832  for( int i = 0; i < nnodes; i++ )
833  graph_knot_add(graph, STP_TERM_NONE);
834 
835  graph->source = 4;
836  graph_knot_chg(graph, 4, STP_TERM);
837  graph_knot_chg(graph, 5, STP_TERM);
838 
839  graph_edge_addBi(scip, graph, 0, 1, 1.1); // 0
840  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
841  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
842  graph_edge_addBi(scip, graph, 1, 2, 1.0);
843  graph_edge_addBi(scip, graph, 1, 3, 1.0);
844  graph_edge_addBi(scip, graph, 2, 4, 3.0);
845  graph_edge_addBi(scip, graph, 3, 4, 3.0);
846  graph_edge_addBi(scip, graph, 1, 5, 1.0); // dummy edge
847 
848  SCIP_CALL( stptest_graphSetUp(scip, graph) );
849  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
850  SCIP_CALL( reduce_sdAddNeighborSd(scip, graph, sddata) );
851 
852  SCIP_CALL( reduce_sdBiasedNeighbor(scip, sddata, graph, &nelims) );
853 
854  STPTEST_ASSERT(nelims == 1);
855  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
856 
857  reduce_sdFree(scip, &sddata);
858  stptest_graphTearDown(scip, graph);
859 
860  return SCIP_OKAY;
861 }
862 
863 
864 
865 /** tests that SD biased neighbor test finds edge for deletion */
866 static
867 SCIP_RETCODE testSdBiasedNeighborDeletesEdge2(
868  SCIP* scip /**< SCIP data structure */
869 )
870 {
871  SD* sddata;
872  GRAPH* graph;
873  int nnodes = 7;
874  int nedges = 18;
875  int nelims = 0;
876 
877  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
878 
879  for( int i = 0; i < nnodes; i++ )
880  graph_knot_add(graph, STP_TERM_NONE);
881 
882  graph->source = 5;
883  graph_knot_chg(graph, 5, STP_TERM);
884  graph_knot_chg(graph, 6, STP_TERM);
885 
886  graph_edge_addBi(scip, graph, 0, 1, 2.1); // 0
887  graph_edge_addBi(scip, graph, 0, 2, 2.0); // 2
888  graph_edge_addBi(scip, graph, 0, 3, 2.0); // 4
889  graph_edge_addBi(scip, graph, 1, 3, 2.0);
890  graph_edge_addBi(scip, graph, 1, 4, 2.0);
891  graph_edge_addBi(scip, graph, 5, 2, 2.0);
892  graph_edge_addBi(scip, graph, 5, 3, 1.0);
893  graph_edge_addBi(scip, graph, 6, 3, 1.0);
894  graph_edge_addBi(scip, graph, 6, 4, 2.0);
895 
896  SCIP_CALL( stptest_graphSetUp(scip, graph) );
897  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
898  SCIP_CALL( reduce_sdAddNeighborSd(scip, graph, sddata) );
899 
900  SCIP_CALL( reduce_sdBiasedNeighbor(scip, sddata, graph, &nelims) );
901 
902  STPTEST_ASSERT(nelims == 1);
903  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
904 
905  reduce_sdFree(scip, &sddata);
906  stptest_graphTearDown(scip, graph);
907 
908  return SCIP_OKAY;
909 }
910 #endif
911 
912 /** tests clique star correctly identifies adjacency distances for degree 3 node */
913 static
914 SCIP_RETCODE testSdCliqueStarDeg3AdjacencyIsCorrect(
915  SCIP* scip /**< SCIP data structure */
916 )
917 {
918  GRAPH* graph;
919  int nnodes = 5;
920  int nedges = 12;
921  const int nsds = 3;
922  SCIP_Real sds[3];
923  int cliquenodes[] = { 1, 2, 3 };
924  SDCLIQUE cliquedata = { .dijkdata = NULL, .cliquenodes = cliquenodes, .ncliquenodes = 3, .sds = sds };
925 
926  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
927 
928  for( int i = 0; i < nsds; i++ )
929  sds[i] = FARAWAY - 1.0;
930 
931  for( int i = 0; i < nnodes; i++ )
932  graph_knot_add(graph, STP_TERM_NONE);
933 
934  graph->source = 4;
935 
936  graph_knot_chg(graph, 4, STP_TERM);
937 
938  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
939  graph_edge_addBi(scip, graph, 0, 2, 0.99); // 2
940  graph_edge_addBi(scip, graph, 0, 3, 1.0);
941  graph_edge_addBi(scip, graph, 1, 2, 1.8);
942  graph_edge_addBi(scip, graph, 1, 3, 1.9);
943  graph_edge_addBi(scip, graph, 1, 4, 3.9); // dummy terminal
944 
945  SCIP_CALL( stptest_graphSetUp(scip, graph) );
946 
947  SCIP_CALL( graph_dijkLimited_init(scip, graph, &(cliquedata.dijkdata)) );
948  graph_dijkLimited_clean(graph, (cliquedata.dijkdata));
949  cliquedata.dijkdata->edgelimit = 50;
950 
951  SCIP_CALL( graph_sdComputeCliqueStar(scip, graph, NULL, &cliquedata) );
952 
953  STPTEST_ASSERT(EQ(sds[0], 1.8));
954  STPTEST_ASSERT(EQ(sds[1], 1.9));
955  STPTEST_ASSERT(EQ(sds[2], 1.99));
956 
957  graph_dijkLimited_free(scip, &(cliquedata.dijkdata));
958 
959  stptest_graphTearDown(scip, graph);
960 
961  return SCIP_OKAY;
962 }
963 
964 
965 
966 /** tests clique star correctly identifies distances for degree 3 node */
967 static
968 SCIP_RETCODE testSdCliqueStarDeg3IsCorrect(
969  SCIP* scip /**< SCIP data structure */
970 )
971 {
972  GRAPH* graph;
973  SD* sddata;
974  int nnodes = 12;
975  int nedges = 28;
976  const int nsds = 3;
977  SCIP_Real sds[3];
978  int cliquenodes[] = { 1, 2, 3 };
979  SDCLIQUE cliquedata = { .dijkdata = NULL, .cliquenodes = cliquenodes, .ncliquenodes = 3, .sds = sds };
980 
981  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
982 
983  for( int i = 0; i < nsds; i++ )
984  sds[i] = FARAWAY - 1.0;
985 
986  for( int i = 0; i < nnodes; i++ )
987  graph_knot_add(graph, STP_TERM_NONE);
988 
989  graph->source = 5;
990  graph_knot_chg(graph, 5, STP_TERM);
991  graph_knot_chg(graph, 10, STP_TERM);
992  graph_knot_chg(graph, 11, STP_TERM);
993 
994  /* star: */
995  graph_edge_addBi(scip, graph, 0, 1, 2.0); // 0
996  graph_edge_addBi(scip, graph, 0, 2, 2.0); // 2
997  graph_edge_addBi(scip, graph, 0, 3, 2.0);
998 
999  /* first cycle: */
1000  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1001  graph_edge_addBi(scip, graph, 4, 5, 1.0);
1002  graph_edge_addBi(scip, graph, 5, 2, 1.0);
1003 
1004  /* second cycle: */
1005  graph_edge_addBi(scip, graph, 2, 6, 2.0);
1006  graph_edge_addBi(scip, graph, 6, 7, 1.0);
1007  graph_edge_addBi(scip, graph, 7, 8, 1.0);
1008  graph_edge_addBi(scip, graph, 8, 9, 1.0);
1009  graph_edge_addBi(scip, graph, 9, 3, 2.0);
1010 
1011  /* third cycle: */
1012  graph_edge_addBi(scip, graph, 6, 10, 10.0);
1013  graph_edge_addBi(scip, graph, 10, 11, 15.0);
1014  graph_edge_addBi(scip, graph, 11, 9, 10.0);
1015 
1016  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1017  SCIP_CALL( graph_dijkLimited_init(scip, graph, &(cliquedata.dijkdata)) );
1018  graph_dijkLimited_clean(graph, (cliquedata.dijkdata));
1019  cliquedata.dijkdata->edgelimit = 50;
1020  SCIP_CALL( reduce_sdInitBiased(scip, graph, &sddata) );
1021 
1022  SCIP_CALL( graph_sdComputeCliqueStar(scip, graph, sddata->sdprofit, &cliquedata) );
1023 
1024  STPTEST_ASSERT(EQ(sds[0], 2.0));
1025  STPTEST_ASSERT(EQ(sds[1], 4.0));
1026  STPTEST_ASSERT(EQ(sds[2], 3.0));
1027 
1028  reduce_sdFree(scip, &sddata);
1029  graph_dijkLimited_free(scip, &(cliquedata.dijkdata));
1030  stptest_graphTearDown(scip, graph);
1031 
1032  return SCIP_OKAY;
1033 }
1034 
1035 
1036 
1037 /** tests clique star correctly identifies distances for degree 3 node */
1038 static
1039 SCIP_RETCODE testSdCliqueStarDeg3IsCorrect2(
1040  SCIP* scip /**< SCIP data structure */
1041 )
1042 {
1043  GRAPH* graph;
1044  SD* sddata;
1045  int nnodes = 10;
1046  int nedges = 24;
1047  const int nsds = 3;
1048  SCIP_Real sds[3];
1049  int cliquenodes[] = { 1, 2, 3 };
1050  SDCLIQUE cliquedata = { .dijkdata = NULL, .cliquenodes = cliquenodes, .ncliquenodes = 3, .sds = sds };
1051 
1052  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1053 
1054  for( int i = 0; i < nsds; i++ )
1055  sds[i] = FARAWAY - 1.0;
1056 
1057  for( int i = 0; i < nnodes; i++ )
1058  graph_knot_add(graph, STP_TERM_NONE);
1059 
1060  graph->source = 1;
1061  graph_knot_chg(graph, 1, STP_TERM);
1062  graph_knot_chg(graph, 2, STP_TERM);
1063  graph_knot_chg(graph, 5, STP_TERM);
1064  graph_knot_chg(graph, 7, STP_TERM);
1065  graph_knot_chg(graph, 9, STP_TERM);
1066 
1067 
1068  /* star: */
1069  graph_edge_addBi(scip, graph, 0, 1, 2.0); // 0
1070  graph_edge_addBi(scip, graph, 0, 2, 2.0); // 2
1071  graph_edge_addBi(scip, graph, 0, 3, 2.0);
1072 
1073  /* first cycle: */
1074  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1075  graph_edge_addBi(scip, graph, 4, 5, 1.0);
1076  graph_edge_addBi(scip, graph, 5, 2, 1.0);
1077 
1078  /* second cycle: */
1079  graph_edge_addBi(scip, graph, 2, 6, 1.5);
1080  graph_edge_addBi(scip, graph, 6, 7, 0.5);
1081  graph_edge_addBi(scip, graph, 7, 8, 2.0);
1082  graph_edge_addBi(scip, graph, 8, 3, 1.0);
1083 
1084  /* profit path */
1085  graph_edge_addBi(scip, graph, 8, 9, 10.5); /* node 8 gets profit of 0.5 */
1086  graph_edge_addBi(scip, graph, 9, 5, 11.0);
1087 
1088 
1089 
1090  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1091  SCIP_CALL( graph_dijkLimited_init(scip, graph, &(cliquedata.dijkdata)) );
1092  graph_dijkLimited_clean(graph, (cliquedata.dijkdata));
1093  cliquedata.dijkdata->edgelimit = 50;
1094  SCIP_CALL( reduce_sdInitBiased(scip, graph, &sddata) );
1095 
1096  SCIP_CALL( graph_sdComputeCliqueStar(scip, graph, sddata->sdprofit, &cliquedata) );
1097 
1098  STPTEST_ASSERT(EQ(sds[0], 2.0));
1099  STPTEST_ASSERT(EQ(sds[1], 4.0));
1100  STPTEST_ASSERT(EQ(sds[2], 2.5));
1101 
1102  reduce_sdFree(scip, &sddata);
1103  graph_dijkLimited_free(scip, &(cliquedata.dijkdata));
1104  stptest_graphTearDown(scip, graph);
1105 
1106  return SCIP_OKAY;
1107 }
1108 
1109 
1110 /** tests clique star correctly identifies distances for degree 4 node */
1111 static
1112 SCIP_RETCODE testSdCliqueStarDeg4IsCorrect(
1113  SCIP* scip /**< SCIP data structure */
1114 )
1115 {
1116  GRAPH* graph;
1117  int nnodes = 7;
1118  int nedges = 16;
1119  const int nsds = 6;
1120  SCIP_Real sds[6];
1121  int cliquenodes[] = { 1, 2, 3, 4 };
1122  SDCLIQUE cliquedata = { .dijkdata = NULL, .cliquenodes = cliquenodes, .ncliquenodes = 4, .sds = sds };
1123 
1124  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1125 
1126  for( int i = 0; i < nsds; i++ )
1127  sds[i] = FARAWAY - 1.0;
1128 
1129  for( int i = 0; i < nnodes; i++ )
1130  graph_knot_add(graph, STP_TERM_NONE);
1131 
1132  graph->source = 6; // dummy
1133  graph_knot_chg(graph, 6, STP_TERM);
1134 
1135  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
1136  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
1137  graph_edge_addBi(scip, graph, 0, 3, 0.9);
1138  graph_edge_addBi(scip, graph, 0, 4, 1.0);
1139  graph_edge_addBi(scip, graph, 1, 5, 0.4);
1140  graph_edge_addBi(scip, graph, 2, 5, 0.4);
1141  graph_edge_addBi(scip, graph, 2, 3, 1.5);
1142 
1143  graph_edge_addBi(scip, graph, 1, 6, 3.9); // dummy terminal
1144 
1145  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1146 
1147  SCIP_CALL( graph_dijkLimited_init(scip, graph, &(cliquedata.dijkdata)) );
1148  graph_dijkLimited_clean(graph, (cliquedata.dijkdata));
1149  cliquedata.dijkdata->edgelimit = 50;
1150 
1151  SCIP_CALL( graph_sdComputeCliqueStar(scip, graph, NULL, &cliquedata) );
1152 
1153  STPTEST_ASSERT(EQ(sds[0], 0.8)); // 1-2
1154  STPTEST_ASSERT(EQ(sds[1], 1.9)); // 1-3
1155  STPTEST_ASSERT(EQ(sds[2], 2.0)); // 1-4
1156  STPTEST_ASSERT(EQ(sds[3], 1.5)); // 2-3
1157  STPTEST_ASSERT(EQ(sds[4], FARAWAY - 1.0)); // 2-4
1158  STPTEST_ASSERT(EQ(sds[5], 1.9)); // 3-4
1159 
1160  graph_dijkLimited_free(scip, &(cliquedata.dijkdata));
1161 
1162  stptest_graphTearDown(scip, graph);
1163 
1164  return SCIP_OKAY;
1165 }
1166 
1167 
1168 /** tests that fully biased SD deletes edge */
1169 static
1170 SCIP_RETCODE testSdBiasedBottleneckDeletesEdge(
1171  SCIP* scip /**< SCIP data structure */
1172 )
1173 {
1174  SD* sddata;
1175  GRAPH* graph;
1176  int nnodes = 9;
1177  int nedges = 20;
1178  int nelims = 0;
1179 
1180  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1181 
1182  for( int i = 0; i < nnodes; i++ )
1183  graph_knot_add(graph, STP_TERM_NONE);
1184 
1185  graph->source = 2;
1186  graph_knot_chg(graph, 2, STP_TERM);
1187  graph_knot_chg(graph, 4, STP_TERM);
1188  graph_knot_chg(graph, 5, STP_TERM);
1189  graph_knot_chg(graph, 8, STP_TERM);
1190 
1191 
1192  /* first cycle */
1193  graph_edge_addBi(scip, graph, 0, 1, 1.2); // 0
1194  graph_edge_addBi(scip, graph, 1, 2, 1.0); // 2
1195  graph_edge_addBi(scip, graph, 2, 3, 1.0); // 4
1196  graph_edge_addBi(scip, graph, 3, 4, 1.0);
1197  graph_edge_addBi(scip, graph, 4, 0, 1.0);
1198 
1199  /* bottleneck path */
1200  graph_edge_addBi(scip, graph, 5, 3, 2.0);
1201  graph_edge_addBi(scip, graph, 5, 6, 2.0);
1202  graph_edge_addBi(scip, graph, 6, 7, 2.85);
1203  graph_edge_addBi(scip, graph, 7, 0, 2.0);
1204 
1205  /* dummy edge to avoid long edge reduction */
1206  graph_edge_addBi(scip, graph, 5, 8, 3.5);
1207 
1208  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1209  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
1210 
1211  SCIP_CALL( reduce_sdBiased(scip, sddata, graph, &nelims) );
1212 
1213  STPTEST_ASSERT(nelims == 1);
1214  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
1215 
1216  reduce_sdFree(scip, &sddata);
1217  stptest_graphTearDown(scip, graph);
1218 
1219  return SCIP_OKAY;
1220 }
1221 
1222 
1223 #if 0
1224 /** tests that (implied) NSV contracts edge */
1225 static
1226 SCIP_RETCODE testNsvRpcImpliedContractsEdge(
1227  SCIP* scip /**< SCIP data structure */
1228 )
1229 {
1230  SD* sdistance;
1231  GRAPH* graph;
1232  int nnodes = 6;
1233  int nedges = 14;
1234  int nelims = 0;
1235  SCIP_Real fixed = 0.0;
1236 
1237  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1238 
1239  for( int i = 0; i < nnodes; i++ )
1240  graph_knot_add(graph, STP_TERM_NONE);
1241 
1242  graph->source = 0;
1243  graph_knot_chg(graph, 0, STP_TERM);
1244  graph_knot_chg(graph, 3, STP_TERM);
1245  graph_knot_chg(graph, 4, STP_TERM);
1246 
1247  /* first cycle */
1248  graph_edge_addBi(scip, graph, 0, 1, 0.9); // 0
1249  graph_edge_addBi(scip, graph, 1, 2, 1.1); // 2
1250  graph_edge_addBi(scip, graph, 2, 3, 1.1); // 4
1251  graph_edge_addBi(scip, graph, 3, 0, 2.1);
1252 
1253  /* second cycle */
1254  graph_edge_addBi(scip, graph, 2, 4, 1.1);
1255  graph_edge_addBi(scip, graph, 4, 5, 1.1);
1256  graph_edge_addBi(scip, graph, 5, 0, 2.1);
1257 
1258  graph_pc_initPrizes(scip, graph, nnodes);
1259  graph->prize[0] = FARAWAY;
1260  graph->prize[1] = 0.0;
1261  graph->prize[2] = 0.0;
1262  graph->prize[3] = 2.0;
1263  graph->prize[4] = FARAWAY;
1264  graph->prize[5] = 0.0;
1265 
1266 
1267  SCIP_CALL( stptest_graphSetUpRpcOrg(scip, graph, NULL, NULL) );
1268  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sdistance) );
1269 
1270 // SCIP_CALL( reduce_nsvImplied(scip, sdistance, graph, NULL, fixed, nelims) );
1271 
1272 
1273 // graph_writeGml(graph, "unit.gml", NULL);
1274 
1275 
1276  STPTEST_ASSERT(1);
1277 
1278  printf("nelims=%d \n", nelims);
1279 
1280 
1281  reduce_sdFree(scip, &sdistance);
1282  stptest_graphTearDown(scip, graph);
1283 
1284  assert(0);
1285 
1286 
1287  return SCIP_OKAY;
1288 }
1289 #endif
1290 
1291 /** tests that (implied) NSV contracts edge */
1292 static
1293 SCIP_RETCODE testNsvImpliedContractsEdge(
1294  SCIP* scip /**< SCIP data structure */
1295 )
1296 {
1297  SD* sddata;
1298  GRAPH* graph;
1299  int nnodes = 6;
1300  int nedges = 14;
1301  int nelims = 0;
1302  SCIP_Real fixed = 0.0;
1303 
1304  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1305 
1306  for( int i = 0; i < nnodes; i++ )
1307  graph_knot_add(graph, STP_TERM_NONE);
1308 
1309  graph->source = 0;
1310  graph_knot_chg(graph, 0, STP_TERM);
1311  graph_knot_chg(graph, 3, STP_TERM);
1312  graph_knot_chg(graph, 4, STP_TERM);
1313 
1314  /* first cycle */
1315  graph_edge_addBi(scip, graph, 0, 1, 0.9); // 0
1316  graph_edge_addBi(scip, graph, 1, 2, 1.1); // 2
1317  graph_edge_addBi(scip, graph, 2, 3, 1.1); // 4
1318  graph_edge_addBi(scip, graph, 3, 0, 2.1);
1319 
1320  /* second cycle */
1321  graph_edge_addBi(scip, graph, 2, 4, 1.1);
1322  graph_edge_addBi(scip, graph, 4, 5, 1.1);
1323  graph_edge_addBi(scip, graph, 5, 0, 2.1);
1324 
1325  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1326  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
1327 
1328  SCIP_CALL( reduce_nsvImplied(scip, sddata, graph, NULL, &fixed, &nelims) );
1329 
1330  STPTEST_ASSERT(graph->grad[1] == 0 || graph->grad[0] == 0);
1331 
1332  reduce_sdFree(scip, &sddata);
1333  stptest_graphTearDown(scip, graph);
1334 
1335  return SCIP_OKAY;
1336 }
1337 
1338 
1339 
1340 /** tests that (implied) NSV contracts edge */
1341 static
1342 SCIP_RETCODE testNsvImpliedContractsEdge2(
1343  SCIP* scip /**< SCIP data structure */
1344 )
1345 {
1346  SD* sddata;
1347  GRAPH* graph;
1348  int nnodes = 6;
1349  int nedges = 14;
1350  int nelims = 0;
1351  SCIP_Real fixed = 0.0;
1352 
1353  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1354 
1355  for( int i = 0; i < nnodes; i++ )
1356  graph_knot_add(graph, STP_TERM_NONE);
1357 
1358  graph->source = 0;
1359  graph_knot_chg(graph, 0, STP_TERM);
1360  graph_knot_chg(graph, 3, STP_TERM);
1361  graph_knot_chg(graph, 5, STP_TERM);
1362 
1363  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
1364  graph_edge_addBi(scip, graph, 1, 2, 1.0); // 2
1365  graph_edge_addBi(scip, graph, 2, 3, 1.1); // 4
1366  graph_edge_addBi(scip, graph, 3, 4, 0.9);
1367  graph_edge_addBi(scip, graph, 4, 5, 1.9);
1368  graph_edge_addBi(scip, graph, 5, 0, 2.1);
1369  graph_edge_addBi(scip, graph, 5, 2, 0.9);
1370 
1371  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1372  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
1373 
1374  SCIP_CALL( reduce_nsvImplied(scip, sddata, graph, NULL, &fixed, &nelims) );
1375 
1376  STPTEST_ASSERT(graph->grad[1] == 0 || graph->grad[0] == 0);
1377 
1378  reduce_sdFree(scip, &sddata);
1379  stptest_graphTearDown(scip, graph);
1380 
1381  return SCIP_OKAY;
1382 }
1383 
1384 
1385 
1386 /** tests that (implied) NSV contracts edge by using node distances to cut */
1387 static
1388 SCIP_RETCODE testNsvImpliedContractsCutDistEdge(
1389  SCIP* scip /**< SCIP data structure */
1390 )
1391 {
1392  SD* sddata;
1393  GRAPH* graph;
1394  int nnodes = 4;
1395  int nedges = 10;
1396  int nelims = 0;
1397  SCIP_Real fixed = 0.0;
1398 
1399  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1400 
1401  for( int i = 0; i < nnodes; i++ )
1402  graph_knot_add(graph, STP_TERM_NONE);
1403 
1404  graph->source = 0;
1405  graph_knot_chg(graph, 0, STP_TERM);
1406  graph_knot_chg(graph, 3, STP_TERM);
1407 
1408  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
1409  graph_edge_addBi(scip, graph, 0, 2, 2.0);
1410  graph_edge_addBi(scip, graph, 1, 2, 1.0);
1411  graph_edge_addBi(scip, graph, 1, 3, 2.0);
1412  graph_edge_addBi(scip, graph, 2, 3, 2.0);
1413 
1414  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1415  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
1416 
1417  SCIP_CALL( reduce_nsvImplied(scip, sddata, graph, NULL, &fixed, &nelims) );
1418 
1419  STPTEST_ASSERT(graph->grad[1] == 0 || graph->grad[0] == 0);
1420  STPTEST_ASSERT(nelims == 1);
1421 
1422 
1423  reduce_sdFree(scip, &sddata);
1424  stptest_graphTearDown(scip, graph);
1425 
1426  return SCIP_OKAY;
1427 }
1428 
1429 
1430 
1431 /** tests that (implied) NSV contracts edge by using node distances to cut */
1432 static
1433 SCIP_RETCODE testNsvImpliedContractsCutDistMiddleEdge(
1434  SCIP* scip /**< SCIP data structure */
1435 )
1436 {
1437  SD* sddata;
1438  GRAPH* graph;
1439  int nnodes = 6;
1440  int nedges = 18;
1441  int nelims = 0;
1442  SCIP_Real fixed = 0.0;
1443 
1444  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1445 
1446  for( int i = 0; i < nnodes; i++ )
1447  graph_knot_add(graph, STP_TERM_NONE);
1448 
1449  graph->source = 2;
1450  graph_knot_chg(graph, 2, STP_TERM);
1451  graph_knot_chg(graph, 3, STP_TERM);
1452 
1453  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
1454  graph_edge_addBi(scip, graph, 0, 2, 1.1);
1455  graph_edge_addBi(scip, graph, 1, 3, 2.0);
1456  graph_edge_addBi(scip, graph, 1, 4, 1.0);
1457  graph_edge_addBi(scip, graph, 1, 5, 0.5);
1458  graph_edge_addBi(scip, graph, 2, 4, 3.1);
1459  graph_edge_addBi(scip, graph, 2, 5, 3.1);
1460  graph_edge_addBi(scip, graph, 3, 4, 2.0);
1461  graph_edge_addBi(scip, graph, 3, 5, 2.0);
1462 
1463  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1464  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
1465 
1466  SCIP_CALL( reduce_nsvImplied(scip, sddata, graph, NULL, &fixed, &nelims) );
1467 
1468  STPTEST_ASSERT(nelims == 1);
1469  STPTEST_ASSERT(graph->grad[2] == 0 || graph->grad[0] == 0);
1470 
1471  reduce_sdFree(scip, &sddata);
1472  stptest_graphTearDown(scip, graph);
1473 
1474  return SCIP_OKAY;
1475 }
1476 
1477 
1478 /** tests that (implied) NSV contracts edge between vertex with implied profit and terminal */
1479 static
1480 SCIP_RETCODE testNsvImpliedContractsImpliedToTermEdge(
1481  SCIP* scip /**< SCIP data structure */
1482 )
1483 {
1484  SD* sddata;
1485  GRAPH* graph;
1486  int nnodes = 4;
1487  int nedges = 8;
1488  int nelims = 0;
1489  SCIP_Real fixed = 0.0;
1490 
1491  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1492 
1493  for( int i = 0; i < nnodes; i++ )
1494  graph_knot_add(graph, STP_TERM_NONE);
1495 
1496  graph->source = 0;
1497  graph_knot_chg(graph, 0, STP_TERM);
1498  graph_knot_chg(graph, 2, STP_TERM);
1499 
1500  graph_edge_addBi(scip, graph, 0, 1, 0.9); // 0
1501  graph_edge_addBi(scip, graph, 1, 2, 2.1); // 2
1502  graph_edge_addBi(scip, graph, 2, 3, 3.0); // 4
1503  graph_edge_addBi(scip, graph, 3, 0, 2.0);
1504 
1505  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1506  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
1507 
1508  SCIP_CALL( reduce_nsvImplied(scip, sddata, graph, NULL, &fixed, &nelims) );
1509 
1510  STPTEST_ASSERT(graph->grad[1] == 0);
1511 
1512  reduce_sdFree(scip, &sddata);
1513  stptest_graphTearDown(scip, graph);
1514 
1515  return SCIP_OKAY;
1516 }
1517 
1518 
1519 /** tests that fully biased SD with biased on terminal path deletes edge */
1520 static
1521 SCIP_RETCODE testSdBiasedBottleneckTermPathDeletesEdge(
1522  SCIP* scip /**< SCIP data structure */
1523 )
1524 {
1525  SD* sddata;
1526  GRAPH* graph;
1527  int nnodes = 8;
1528  int nedges = 18;
1529  int nelims = 0;
1530 
1531  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
1532 
1533  for( int i = 0; i < nnodes; i++ )
1534  graph_knot_add(graph, STP_TERM_NONE);
1535 
1536  graph->source = 3;
1537  graph_knot_chg(graph, 3, STP_TERM);
1538  graph_knot_chg(graph, 4, STP_TERM);
1539  graph_knot_chg(graph, 5, STP_TERM);
1540 
1541  /* first cycle */
1542  graph_edge_addBi(scip, graph, 0, 1, 1.2); // 0
1543  graph_edge_addBi(scip, graph, 1, 2, 1.1); // 2
1544  graph_edge_addBi(scip, graph, 2, 3, 1.1); // 4
1545  graph_edge_addBi(scip, graph, 3, 4, 1.1);
1546  graph_edge_addBi(scip, graph, 4, 0, 1.0);
1547 
1548  /* bottleneck path */
1549  graph_edge_addBi(scip, graph, 2, 5, 2.0);
1550  graph_edge_addBi(scip, graph, 5, 6, 2.0);
1551  graph_edge_addBi(scip, graph, 6, 7, 3.105); // 14
1552  graph_edge_addBi(scip, graph, 7, 1, 2.0);
1553 
1554 
1555  SCIP_CALL( stptest_graphSetUp(scip, graph) );
1556  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, graph, &sddata) );
1557 
1558  SCIP_CALL( reduce_sdBiased(scip, sddata, graph, &nelims) );
1559 
1560  STPTEST_ASSERT(nelims == 2);
1561  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
1562  STPTEST_ASSERT(graph->oeat[14] == EAT_FREE); // deleted by SD MST
1563 
1564 
1565  reduce_sdFree(scip, &sddata);
1566  stptest_graphTearDown(scip, graph);
1567 
1568  return SCIP_OKAY;
1569 }
1570 
1571 
1572 /** tests Bdk methods */
1573 SCIP_RETCODE stptest_reduceBdk(
1574  SCIP* scip /**< SCIP data structure */
1575 )
1576 {
1577 #if 0
1578  SCIP_CALL( testBdkDeletesEdge(scip) );
1579  SCIP_CALL( testBdkReplacesEdge(scip) );
1580 #endif
1581  SCIP_CALL( testBdkSdMstDeletesNodeDeg3(scip) );
1582  SCIP_CALL( testBdkTreeDistDeletesNodeDeg4(scip) );
1583  SCIP_CALL( testBdkSdMstDeletesNodeDeg4(scip) );
1584  SCIP_CALL( testBdkSdMstStarDeletesNodeDeg4(scip) );
1585 
1586 
1587  printf("reduce BDk test: all ok \n");
1588 
1589  return SCIP_OKAY;
1590 }
1591 
1592 
1593 /** tests biased SD methods */
1594 SCIP_RETCODE stptest_reduceSdBiased(
1595  SCIP* scip /**< SCIP data structure */
1596 )
1597 {
1598 
1599 
1600  // SCIP_CALL( testSdBiasedNeighborDeletesEdge(scip) );
1601  // SCIP_CALL( testSdBiasedNeighborDeletesEdge2(scip) );
1602 
1603  SCIP_CALL( testSdBiasedDeletesEdge(scip) );
1604  SCIP_CALL( testSdCliqueStarDeletesEdge(scip) );
1605 
1606  printf("reduce SD biased test: all ok \n");
1607 
1608  return SCIP_OKAY;
1609 }
1610 
1611 
1612 /** tests SD clique star methods */
1613 SCIP_RETCODE stptest_reduceSdCliqueStar(
1614  SCIP* scip /**< SCIP data structure */
1615 )
1616 {
1617  SCIP_CALL( testSdCliqueStarDeg3IsCorrect(scip) );
1618  SCIP_CALL( testSdCliqueStarDeg3IsCorrect2(scip) );
1619  SCIP_CALL( testSdCliqueStarDeg3AdjacencyIsCorrect(scip) );
1620  SCIP_CALL( testSdCliqueStarDeg4IsCorrect(scip) );
1621 
1622  printf("reduce clique star test: all ok \n");
1623 
1624  return SCIP_OKAY;
1625 }
1626 
1627 
1628 /** tests SD getter methods */
1629 SCIP_RETCODE stptest_reduceSdGetter(
1630  SCIP* scip /**< SCIP data structure */
1631 )
1632 {
1633 
1634  SCIP_CALL( testSdGraphQueriesAreValid(scip) );
1635 
1636 
1637  SCIP_CALL( testSdGraphStrongBiasedDistsAreValid(scip) );
1638 
1639  SCIP_CALL( testSdGetterReturnsCorrectSds(scip) );
1640  SCIP_CALL( testSdGraphDistsAreValid(scip) );
1641  SCIP_CALL( testSdGraphDistsAreValid2(scip) );
1642 
1643  printf("reduce sd getter test: all ok \n");
1644 
1645  return SCIP_OKAY;
1646 }
1647 
1648 
1649 /** tests implied profit based routine */
1650 SCIP_RETCODE stptest_reduceSdBiasedBottleneck(
1651  SCIP* scip /**< SCIP data structure */
1652 )
1653 {
1654  SCIP_CALL( testSdBiasedBottleneckTermPathDeletesEdge(scip) );
1655  SCIP_CALL( testSdBiasedBottleneckDeletesEdge(scip) );
1656 
1657  printf("implied profit based reductions test: all ok \n");
1658 
1659  return SCIP_OKAY;
1660 }
1661 
1662 /** tests NSV */
1663 SCIP_RETCODE stptest_reduceNsvImplied(
1664  SCIP* scip /**< SCIP data structure */
1665 )
1666 {
1667  // SCIP_CALL( testNsvRpcImpliedContractsEdge(scip) );
1668 
1669  SCIP_CALL( testNsvImpliedContractsEdge(scip) );
1670  SCIP_CALL( testNsvImpliedContractsEdge2(scip) );
1671  SCIP_CALL( testNsvImpliedContractsImpliedToTermEdge(scip) );
1672 
1673  SCIP_CALL( testNsvImpliedContractsCutDistMiddleEdge(scip) );
1674  SCIP_CALL( testNsvImpliedContractsCutDistEdge(scip) );
1675 
1676  printf("implied NSV reduction test: all ok \n");
1677 
1678  return SCIP_OKAY;
1679 }
1680 
1681 
1682 /** tests SD biased methods */
1683 SCIP_RETCODE stptest_reduceSdStarBias(
1684  SCIP* scip /**< SCIP data structure */
1685 )
1686 {
1687  SCIP_CALL( testSdStarBiasedDeletesEdge(scip) );
1688  SCIP_CALL( testSdStarBiasedDeletesEdge2(scip) );
1689  SCIP_CALL( testSdStarBiasedDeletesEdge3(scip) );
1690 
1691  printf("reduce SD test: all ok \n");
1692 
1693  return SCIP_OKAY;
1694 }
reduce_sdInit
SCIP_RETCODE reduce_sdInit(SCIP *, GRAPH *, SD **)
Definition: reduce_sdutil.c:724
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
reduce_bdk
SCIP_RETCODE reduce_bdk(SCIP *, int, GRAPH *, int *)
Definition: reduce_sdcomp.c:774
STPTEST_ASSERT
#define STPTEST_ASSERT(cond)
Definition: stptest.h:63
testNsvImpliedContractsCutDistEdge
static SCIP_RETCODE testNsvImpliedContractsCutDistEdge(SCIP *scip)
Definition: stptest_reducesd.c:1388
GRAPH::head
int *RESTRICT head
Definition: graphdefs.h:224
testSdGraphDistsAreValid
static SCIP_RETCODE testSdGraphDistsAreValid(SCIP *scip)
Definition: stptest_reducesd.c:140
GRAPH::source
int source
Definition: graphdefs.h:195
testSdGraphQueriesAreValid
static SCIP_RETCODE testSdGraphQueriesAreValid(SCIP *scip)
Definition: stptest_reducesd.c:234
testSdCliqueStarDeg3AdjacencyIsCorrect
static SCIP_RETCODE testSdCliqueStarDeg3AdjacencyIsCorrect(SCIP *scip)
Definition: stptest_reducesd.c:914
graph_edge_addBi
void graph_edge_addBi(SCIP *, GRAPH *, int, int, double)
stptest_reduceSdCliqueStar
SCIP_RETCODE stptest_reduceSdCliqueStar(SCIP *scip)
Definition: stptest_reducesd.c:1613
testSdCliqueStarDeg4IsCorrect
static SCIP_RETCODE testSdCliqueStarDeg4IsCorrect(SCIP *scip)
Definition: stptest_reducesd.c:1112
testSdGetterReturnsCorrectSds
static SCIP_RETCODE testSdGetterReturnsCorrectSds(SCIP *scip)
Definition: stptest_reducesd.c:40
testBdkSdMstDeletesNodeDeg4
static SCIP_RETCODE testBdkSdMstDeletesNodeDeg4(SCIP *scip)
Definition: stptest_reducesd.c:376
testSdBiasedDeletesEdge
static SCIP_RETCODE testSdBiasedDeletesEdge(SCIP *scip)
Definition: stptest_reducesd.c:775
reduce_sdgraphGetSd
SCIP_Real reduce_sdgraphGetSd(int, int, SDGRAPH *)
Definition: reduce_sdgraph.c:1958
graph_path_init
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
EAT_FREE
#define EAT_FREE
Definition: graphdefs.h:57
reduce_sdgraphInitOrderedMstCosts
void reduce_sdgraphInitOrderedMstCosts(SDGRAPH *)
Definition: reduce_sdgraph.c:1938
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
reduce_sdgraphFree
void reduce_sdgraphFree(SCIP *, SDGRAPH **)
Definition: reduce_sdgraph.c:2055
testSdStarBiasedDeletesEdge3
static SCIP_RETCODE testSdStarBiasedDeletesEdge3(SCIP *scip)
Definition: stptest_reducesd.c:691
reduce_sdInitBiased
SCIP_RETCODE reduce_sdInitBiased(SCIP *, GRAPH *, SD **)
Definition: reduce_sdutil.c:751
testSdGraphStrongBiasedDistsAreValid
static SCIP_RETCODE testSdGraphStrongBiasedDistsAreValid(SCIP *scip)
Definition: stptest_reducesd.c:282
special_distance_storage::sdprofit
SDPROFIT * sdprofit
Definition: reducedefs.h:124
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
testBdkTreeDistDeletesNodeDeg4
static SCIP_RETCODE testBdkTreeDistDeletesNodeDeg4(SCIP *scip)
Definition: stptest_reducesd.c:334
stptest_reduceSdStarBias
SCIP_RETCODE stptest_reduceSdStarBias(SCIP *scip)
Definition: stptest_reducesd.c:1683
reduce_sdgraphGetOrderedMstCosts
const SCIP_Real * reduce_sdgraphGetOrderedMstCosts(const SDGRAPH *)
Definition: reduce_sdgraph.c:1989
reduce_sdAddNeighborSd
SCIP_RETCODE reduce_sdAddNeighborSd(SCIP *, const GRAPH *, SD *)
Definition: reduce_sdutil.c:868
STP_TERM_NONE
#define STP_TERM_NONE
Definition: graphdefs.h:62
GRAPH::mark
int *RESTRICT mark
Definition: graphdefs.h:198
testSdCliqueStarDeg3IsCorrect2
static SCIP_RETCODE testSdCliqueStarDeg3IsCorrect2(SCIP *scip)
Definition: stptest_reducesd.c:1039
graph_pc_initPrizes
SCIP_RETCODE graph_pc_initPrizes(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:741
special_distance_clique::dijkdata
DIJK * dijkdata
Definition: graphdefs.h:339
GRAPH::oeat
int *RESTRICT oeat
Definition: graphdefs.h:231
graph_tpathsInitBiased
SCIP_RETCODE graph_tpathsInitBiased(SCIP *, const SDPROFIT *, GRAPH *, TPATHS **)
Definition: graph_tpath.c:1700
stptest_reduceSdBiased
SCIP_RETCODE stptest_reduceSdBiased(SCIP *scip)
Definition: stptest_reducesd.c:1594
stptest_reduceSdGetter
SCIP_RETCODE stptest_reduceSdGetter(SCIP *scip)
Definition: stptest_reducesd.c:1629
reduce_sdBiasedNeighbor
SCIP_RETCODE reduce_sdBiasedNeighbor(SCIP *, SD *, GRAPH *, int *)
Definition: reduce_sd.c:1922
special_distance_implied_profit
Definition: reducedefs.h:135
testSdCliqueStarDeg3IsCorrect
static SCIP_RETCODE testSdCliqueStarDeg3IsCorrect(SCIP *scip)
Definition: stptest_reducesd.c:968
testSdStarBiasedDeletesEdge
static SCIP_RETCODE testSdStarBiasedDeletesEdge(SCIP *scip)
Definition: stptest_reducesd.c:610
GRAPH::prize
SCIP_Real * prize
Definition: graphdefs.h:210
GRAPH::grad
int *RESTRICT grad
Definition: graphdefs.h:201
stptest_reduceNsvImplied
SCIP_RETCODE stptest_reduceNsvImplied(SCIP *scip)
Definition: stptest_reducesd.c:1663
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
testNsvImpliedContractsImpliedToTermEdge
static SCIP_RETCODE testNsvImpliedContractsImpliedToTermEdge(SCIP *scip)
Definition: stptest_reducesd.c:1480
NULL
#define NULL
Definition: lpi_spx1.cpp:155
testNsvImpliedContractsEdge
static SCIP_RETCODE testNsvImpliedContractsEdge(SCIP *scip)
Definition: stptest_reducesd.c:1293
SCIP_OKAY
Definition: type_retcode.h:33
EQ
#define EQ(a, b)
Definition: portab.h:79
reduce_sdBiased
SCIP_RETCODE reduce_sdBiased(SCIP *, SD *, GRAPH *, int *)
Definition: reduce_sd.c:1840
reduce_sdprofitFree
void reduce_sdprofitFree(SCIP *, SDPROFIT **)
Definition: reduce_sdutil.c:1102
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:384
reduce_sdFree
void reduce_sdFree(SCIP *, SD **)
Definition: reduce_sdutil.c:886
graph_sdComputeCliqueStar
SCIP_RETCODE graph_sdComputeCliqueStar(SCIP *, const GRAPH *, const SDPROFIT *, SDCLIQUE *)
Definition: graph_sdpath.c:2398
special_distance_graph
Definition: reduce_sdgraph.c:46
graph_dijkLimited_init
SCIP_RETCODE graph_dijkLimited_init(SCIP *, const GRAPH *, DIJK **)
Definition: graph_util.c:1989
stptest_graphTearDown
void stptest_graphTearDown(SCIP *, GRAPH *)
Definition: stptest_graph.c:274
graph_dijkLimited_free
void graph_dijkLimited_free(SCIP *, DIJK **)
Definition: graph_util.c:2143
testSdCliqueStarDeletesEdge
static SCIP_RETCODE testSdCliqueStarDeletesEdge(SCIP *scip)
Definition: stptest_reducesd.c:733
STP_TERM
#define STP_TERM
Definition: graphdefs.h:61
reduce_sdInitBiasedBottleneck
SCIP_RETCODE reduce_sdInitBiasedBottleneck(SCIP *, GRAPH *, SD **)
Definition: reduce_sdutil.c:779
reduce_sdEdgeCliqueStar
SCIP_RETCODE reduce_sdEdgeCliqueStar(SCIP *, int, GRAPH *, int *)
Definition: reduce_sd.c:2934
stptest_reduceSdBiasedBottleneck
SCIP_RETCODE stptest_reduceSdBiasedBottleneck(SCIP *scip)
Definition: stptest_reducesd.c:1650
reduce_sdgraphInitBiasedFromTpaths
SCIP_RETCODE reduce_sdgraphInitBiasedFromTpaths(SCIP *, GRAPH *, const SDPROFIT *, const TPATHS *, SDGRAPH **)
Definition: reduce_sdgraph.c:1836
testSdBiasedBottleneckDeletesEdge
static SCIP_RETCODE testSdBiasedBottleneckDeletesEdge(SCIP *scip)
Definition: stptest_reducesd.c:1170
testNsvImpliedContractsCutDistMiddleEdge
static SCIP_RETCODE testNsvImpliedContractsCutDistMiddleEdge(SCIP *scip)
Definition: stptest_reducesd.c:1433
portab.h
Portable definitions.
reduce_sdGetSdsCliquegraph
SCIP_RETCODE reduce_sdGetSdsCliquegraph(SCIP *, const GRAPH *, int, const int *, DIJK *, SD *, GRAPH *)
Definition: reduce_sd.c:1389
special_distance_storage
Definition: reducedefs.h:122
testSdBiasedBottleneckTermPathDeletesEdge
static SCIP_RETCODE testSdBiasedBottleneckTermPathDeletesEdge(SCIP *scip)
Definition: stptest_reducesd.c:1521
dijkstra_data::edgelimit
int edgelimit
Definition: graphdefs.h:321
stptest.h
includes various testing methods for Steiner tree problems
GRAPH::cost
SCIP_Real * cost
Definition: graphdefs.h:221
testBdkSdMstStarDeletesNodeDeg4
static SCIP_RETCODE testBdkSdMstStarDeletesNodeDeg4(SCIP *scip)
Definition: stptest_reducesd.c:424
stptest_graphSetUp
SCIP_RETCODE stptest_graphSetUp(SCIP *, GRAPH *)
Definition: stptest_graph.c:286
graph_dijkLimited_clean
void graph_dijkLimited_clean(const GRAPH *, DIJK *)
Definition: graph_util.c:2083
special_distance_storage::sdgraph
SDGRAPH * sdgraph
Definition: reducedefs.h:125
SCIP_Real
#define SCIP_Real
Definition: def.h:177
reduce_sdStarBiased
SCIP_RETCODE reduce_sdStarBiased(SCIP *, int, SCIP_Bool, GRAPH *, int *)
Definition: reduce_sd.c:3327
dijkstra_data
Definition: graphdefs.h:311
GRAPH::outbeg
int *RESTRICT outbeg
Definition: graphdefs.h:204
testSdGraphDistsAreValid2
static SCIP_RETCODE testSdGraphDistsAreValid2(SCIP *scip)
Definition: stptest_reducesd.c:187
reduce_sdprofitInit
SCIP_RETCODE reduce_sdprofitInit(SCIP *, const GRAPH *, SDPROFIT **)
Definition: reduce_sdutil.c:1032
testSdStarBiasedDeletesEdge2
static SCIP_RETCODE testSdStarBiasedDeletesEdge2(SCIP *scip)
Definition: stptest_reducesd.c:649
reduce_nsvImplied
SCIP_RETCODE reduce_nsvImplied(SCIP *, const SD *, GRAPH *, int *, SCIP_Real *, int *)
Definition: reduce_alt.c:621
graph_buildCompleteGraph
SCIP_RETCODE graph_buildCompleteGraph(SCIP *, GRAPH **, int)
Definition: graph_base.c:440
nnodes
#define nnodes
Definition: gastrans.c:65
testNsvImpliedContractsEdge2
static SCIP_RETCODE testNsvImpliedContractsEdge2(SCIP *scip)
Definition: stptest_reducesd.c:1342
special_distance_clique
Definition: graphdefs.h:337
graph_init
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
stptest_reduceBdk
SCIP_RETCODE stptest_reduceBdk(SCIP *scip)
Definition: stptest_reducesd.c:1573
reduce.h
includes various reduction methods for Steiner tree problems
graph_tpathsFree
void graph_tpathsFree(SCIP *, TPATHS **)
Definition: graph_tpath.c:2300
testBdkSdMstDeletesNodeDeg3
static SCIP_RETCODE testBdkSdMstDeletesNodeDeg3(SCIP *scip)
Definition: stptest_reducesd.c:566
nodes_to_terminal_paths
Definition: graph_tpath.c:61