Scippy

SCIP

Solving Constraint Integer Programs

stptest_reduceutils.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_reduceutils.c
17  * @brief tests for Steiner tree reductions
18  * @author Daniel Rehfeldt
19  *
20  * This file implements unit tests for Steiner problem reduction utility methods.
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 //#define SCIP_DEBUG
28 
29 #include <stdio.h>
30 #include <assert.h>
31 #include "stptest.h"
32 #include "graph.h"
33 #include "reduce.h"
34 #include "portab.h"
35 
36 
37 /** builds up 3x3 MST */
38 static
39 SCIP_RETCODE dcmstTest1(
40  SCIP* scip /**< SCIP data structure */
41 )
42 {
43  DCMST* dcmst;
44  CSR* csr_base;
45  CSR* csr_extended;
46  SCIP_Real adjcosts[] = { -1.0, -1.0 };
47 
48  SCIP_CALL( reduce_dcmstInit(scip, 3, &dcmst) );
49  SCIP_CALL( graph_csr_alloc(scip, 2, 2, &csr_base) );
50  SCIP_CALL( graph_csr_alloc(scip, 3, 4, &csr_extended) );
51 
52  csr_base->nnodes = 1;
53  csr_base->nedges_max = 0;
54 
55  reduce_dcmstGet1NodeMst(scip, csr_base);
56 
57  csr_extended->nnodes = 2;
58  csr_extended->nedges_max = 2;
59 
60  adjcosts[0] = 2.5;
61 
62  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
63 
64  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 2.5) )
65  {
66  SCIPdebugMessage("wrong MST weight \n");
67 
68  return SCIP_ERROR;
69  }
70 
71  csr_base->nnodes = 2;
72  csr_base->nedges_max = 2;
73 
74  graph_csr_copy(csr_extended, csr_base);
75 
76  csr_extended->nnodes = 3;
77  csr_extended->nedges_max = 4;
78 
79  adjcosts[0] = 1.0;
80  adjcosts[1] = 1.2;
81 
82  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
83 
84  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 2.2) )
85  {
86  SCIPdebugMessage("wrong MST weight \n");
87 
88  return SCIP_ERROR;
89  }
90 
91  adjcosts[0] = 3.0;
92  adjcosts[1] = 3.2;
93 
94  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
95 
96  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 5.5) )
97  {
98  SCIPdebugMessage("wrong MST weight \n");
99 
100  return SCIP_ERROR;
101  }
102 
103  reduce_dcmstFree(scip, &dcmst);
104  graph_csr_free(scip, &csr_base);
105  graph_csr_free(scip, &csr_extended);
106 
107  return SCIP_OKAY;
108 }
109 
110 
111 /** builds up 4x4 MST */
112 static
113 SCIP_RETCODE dcmstTest2(
114  SCIP* scip /**< SCIP data structure */
115 )
116 {
117  DCMST* dcmst;
118  CSR* csr_base;
119  CSR* csr_extended;
120  SCIP_Real adjcosts[] = { -1.0, -1.0, -1.0 };
121 
122  SCIP_CALL( reduce_dcmstInit(scip, 4, &dcmst) );
123  SCIP_CALL( graph_csr_alloc(scip, 3, 4, &csr_base) );
124  SCIP_CALL( graph_csr_alloc(scip, 4, 6, &csr_extended) );
125 
126  csr_base->nnodes = 2;
127  csr_base->nedges_max = 2;
128 
129  reduce_dcmstGet2NodeMst(scip, 1.0, csr_base);
130 
131  csr_extended->nnodes = 3;
132  csr_extended->nedges_max = 4;
133 
134  adjcosts[0] = 1.5;
135  adjcosts[1] = 0.7;
136 
137  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
138 
139  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 1.7) )
140  {
141  SCIPdebugMessage("wrong MST weight \n");
142 
143  return SCIP_ERROR;
144  }
145 
146  csr_base->nnodes = 3;
147  csr_base->nedges_max = 4;
148 
149  graph_csr_copy(csr_extended, csr_base);
150 
151  csr_extended->nnodes = 4;
152  csr_extended->nedges_max = 6;
153 
154  adjcosts[0] = 0.5;
155  adjcosts[1] = 2.7;
156  adjcosts[2] = 2.7;
157 
158  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
159 
160  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 2.2) )
161  {
162  SCIPdebugMessage("wrong MST weight \n");
163 
164  return SCIP_ERROR;
165  }
166 
167 
168  reduce_dcmstFree(scip, &dcmst);
169  graph_csr_free(scip, &csr_base);
170  graph_csr_free(scip, &csr_extended);
171 
172  return SCIP_OKAY;
173 }
174 
175 
176 
177 /** builds up a 4x4 MST */
178 static
179 SCIP_RETCODE dcmstTest2b(
180  SCIP* scip /**< SCIP data structure */
181 )
182 {
183  DCMST* dcmst;
184  CSR* csr_base;
185  CSR* csr_extended;
186  SCIP_Real adjcosts[] = { -1.0, -1.0, -1.0 };
187 
188  SCIP_CALL( reduce_dcmstInit(scip, 4, &dcmst) );
189  SCIP_CALL( graph_csr_alloc(scip, 3, 4, &csr_base) );
190  SCIP_CALL( graph_csr_alloc(scip, 4, 6, &csr_extended) );
191 
192  csr_base->nnodes = 2;
193  csr_base->nedges_max = 2;
194 
195  reduce_dcmstGet2NodeMst(scip, 395.0, csr_base);
196 
197  csr_extended->nnodes = 3;
198  csr_extended->nedges_max = 4;
199 
200  adjcosts[0] = 200.0;
201  adjcosts[1] = 302.0;
202 
203  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
204 
205  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 502.0) )
206  {
207  SCIPdebugMessage("wrong MST weight \n");
208 
209  return SCIP_ERROR;
210  }
211 
212  csr_base->nnodes = 3;
213  csr_base->nedges_max = 4;
214 
215  graph_csr_copy(csr_extended, csr_base);
216 
217  csr_extended->nnodes = 4;
218  csr_extended->nedges_max = 6;
219 
220  adjcosts[0] = 197.0;
221  adjcosts[1] = FARAWAY;
222  adjcosts[2] = 197.0;
223 
224  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
225 
226  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 696.0) )
227  {
228  SCIPdebugMessage("wrong MST weight \n");
229 
230  return SCIP_ERROR;
231  }
232 
233 
234  reduce_dcmstFree(scip, &dcmst);
235  graph_csr_free(scip, &csr_base);
236  graph_csr_free(scip, &csr_extended);
237 
238  return SCIP_OKAY;
239 }
240 
241 
242 /** builds up 6x6 MST */
243 static
244 SCIP_RETCODE dcmstTest3(
245  SCIP* scip /**< SCIP data structure */
246 )
247 {
248  DCMST* dcmst;
249  CSR* csr_base;
250  CSR* csr_extended;
251  SCIP_Real adjcosts[] = { -1.0, -1.0, -1.0, -1.0, -1.0 };
252 
253  SCIP_CALL( reduce_dcmstInit(scip, 6, &dcmst) );
254  SCIP_CALL( graph_csr_alloc(scip, 5, 8, &csr_base) );
255  SCIP_CALL( graph_csr_alloc(scip, 6, 10, &csr_extended) );
256 
257  csr_base->nnodes = 2;
258  csr_base->nedges_max = 2;
259 
260  reduce_dcmstGet2NodeMst(scip, 3.1, csr_base);
261 
262  /* build on 3x3 */
263  csr_extended->nnodes = 3;
264  csr_extended->nedges_max = 4;
265 
266  adjcosts[0] = 1.2;
267  adjcosts[1] = 7.3;
268 
269  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
270 
271  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 4.3) )
272  {
273  SCIPdebugMessage("wrong MST weight \n");
274 
275  return SCIP_ERROR;
276  }
277 
278  /* build on 4x4 */
279  csr_base->nnodes = 3;
280  csr_base->nedges_max = 4;
281 
282  graph_csr_copy(csr_extended, csr_base);
283 
284  csr_extended->nnodes = 4;
285  csr_extended->nedges_max = 6;
286 
287  adjcosts[0] = 1.6;
288  adjcosts[1] = 0.1;
289  adjcosts[2] = 0.3;
290 
291  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
292 
293  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 1.6) )
294  {
295  SCIPdebugMessage("wrong MST weight \n");
296 
297  return SCIP_ERROR;
298  }
299 
300  /* build on 5x5 */
301  csr_base->nnodes = 4;
302  csr_base->nedges_max = 6;
303 
304  graph_csr_copy(csr_extended, csr_base);
305 
306  csr_extended->nnodes = 5;
307  csr_extended->nedges_max = 8;
308 
309  adjcosts[0] = 0.2;
310  adjcosts[1] = 0.01;
311  adjcosts[2] = 2.6;
312  adjcosts[3] = 4.1;
313 
314  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
315 
316  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 0.61) )
317  {
318  SCIPdebugMessage("wrong MST weight \n");
319 
320  return SCIP_ERROR;
321  }
322 
323  /* build on 6x6 */
324  csr_base->nnodes = 5;
325  csr_base->nedges_max = 8;
326 
327  graph_csr_copy(csr_extended, csr_base);
328 
329  csr_extended->nnodes = 6;
330  csr_extended->nedges_max = 10;
331 
332  adjcosts[0] = 0.3;
333  adjcosts[1] = 0.2;
334  adjcosts[2] = 0.6;
335  adjcosts[3] = 4.1;
336  adjcosts[4] = 5.1;
337 
338  reduce_dcmstAddNode(scip, csr_base, adjcosts, dcmst, csr_extended);
339 
340  if( !EQ(reduce_dcmstGetWeight(scip, csr_extended), 0.81) )
341  {
342  SCIPdebugMessage("wrong MST weight \n");
343 
344  return SCIP_ERROR;
345  }
346 
347  reduce_dcmstFree(scip, &dcmst);
348  graph_csr_free(scip, &csr_base);
349  graph_csr_free(scip, &csr_extended);
350 
351  return SCIP_OKAY;
352 }
353 
354 
355 /** STAR of degree 3 should be correctly computed */
356 static
357 SCIP_RETCODE testStar3IsCorrect(
358  SCIP* scip /**< SCIP data structure */
359 )
360 {
361  STAR* star;
362  GRAPH* graph;
363  int nnodes = 4;
364  int nedges = 6;
365  int nstaredges = -1;
366  const int* staredges;
367 
368  SCIP_CALL( reduce_starInit(scip, 3, &star) );
369  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
370 
371  graph_knot_add(graph, STP_TERM);
372  for( int i = 1; i < nnodes; i++ )
373  graph_knot_add(graph, STP_TERM_NONE);
374 
375  graph->source = 0;
376 
377  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
378  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
379  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
380 
381  SCIP_CALL( stptest_graphSetUp(scip, graph) );
382 
383  reduce_starReset(graph, 0, star);
384  staredges = reduce_starGetNext(star, &nstaredges);
385 
386  STPTEST_ASSERT(nstaredges == 3);
387  STPTEST_ASSERT(staredges[0] == 4);
388  STPTEST_ASSERT(staredges[1] == 2);
389  STPTEST_ASSERT(staredges[2] == 0);
390  STPTEST_ASSERT(reduce_starAllAreChecked(star));
391 
392  stptest_graphTearDown(scip, graph);
393  reduce_starFree(scip, &star);
394 
395  return SCIP_OKAY;
396 }
397 
398 
399 /** STAR of degree 4 should be correctly computed */
400 static
401 SCIP_RETCODE testStar4IsCorrect(
402  SCIP* scip /**< SCIP data structure */
403 )
404 {
405  STAR* star;
406  GRAPH* graph;
407  int nnodes = 5;
408  int nedges = 8;
409  int nstaredges = -1;
410  const int* staredges;
411 
412  SCIP_CALL( reduce_starInit(scip, 5, &star) );
413  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
414 
415  graph_knot_add(graph, STP_TERM);
416  for( int i = 1; i < nnodes; i++ )
417  graph_knot_add(graph, STP_TERM_NONE);
418 
419  graph->source = 0;
420 
421  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
422  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
423  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
424  graph_edge_addBi(scip, graph, 0, 4, 1.0); // 6
425 
426 
427  SCIP_CALL( stptest_graphSetUp(scip, graph) );
428 
429  reduce_starReset(graph, 2, star);
430  reduce_starReset(graph, 0, star);
431 
432  /* full star */
433  staredges = reduce_starGetNext(star, &nstaredges);
434  STPTEST_ASSERT(nstaredges == 4);
435  STPTEST_ASSERT(staredges[0] == 6);
436  STPTEST_ASSERT(staredges[1] == 4);
437  STPTEST_ASSERT(staredges[2] == 2);
438  STPTEST_ASSERT(staredges[3] == 0);
439 
440  /* 1st degree 3 star */
441  staredges = reduce_starGetNext(star, &nstaredges);
442  STPTEST_ASSERT(nstaredges == 3);
443  STPTEST_ASSERT(staredges[0] == 6);
444  STPTEST_ASSERT(staredges[1] == 4);
445  STPTEST_ASSERT(staredges[2] == 2);
446 
447  /* 2nd degree 3 star */
448  staredges = reduce_starGetNext(star, &nstaredges);
449  STPTEST_ASSERT(nstaredges == 3);
450  STPTEST_ASSERT(staredges[0] == 6);
451  STPTEST_ASSERT(staredges[1] == 4);
452  STPTEST_ASSERT(staredges[2] == 0);
453 
454  /* 3rd degree 3 star */
455  staredges = reduce_starGetNext(star, &nstaredges);
456  STPTEST_ASSERT(nstaredges == 3);
457  STPTEST_ASSERT(staredges[0] == 6);
458  STPTEST_ASSERT(staredges[1] == 2);
459  STPTEST_ASSERT(staredges[2] == 0);
460 
461  /* 4th degree 3 star */
462  staredges = reduce_starGetNext(star, &nstaredges);
463  STPTEST_ASSERT(nstaredges == 3);
464  STPTEST_ASSERT(staredges[0] == 4);
465  STPTEST_ASSERT(staredges[1] == 2);
466  STPTEST_ASSERT(staredges[2] == 0);
467 
468  STPTEST_ASSERT(reduce_starAllAreChecked(star));
469 
470  stptest_graphTearDown(scip, graph);
471  reduce_starFree(scip, &star);
472 
473  return SCIP_OKAY;
474 }
475 
476 
477 
478 /** STAR of degree 4 edge rule-out should be correctly computed */
479 static
480 SCIP_RETCODE testStar4EdgeIsCorrect(
481  SCIP* scip /**< SCIP data structure */
482 )
483 {
484  STAR* star;
485  GRAPH* graph;
486  const int* promisingedges;
487  int nnodes = 5;
488  int nedges = 8;
489  int nstaredges = -1;
490  int nedgespromising;
491  const int* staredges;
492 
493  SCIP_CALL( reduce_starInit(scip, 5, &star) );
494  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
495 
496  graph_knot_add(graph, STP_TERM);
497  for( int i = 1; i < nnodes; i++ )
498  graph_knot_add(graph, STP_TERM_NONE);
499 
500  graph->source = 0;
501 
502  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
503  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
504  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
505  graph_edge_addBi(scip, graph, 0, 4, 1.0); // 6
506 
507 
508  SCIP_CALL( stptest_graphSetUp(scip, graph) );
509 
510  reduce_starReset(graph, 2, star);
511  reduce_starReset(graph, 0, star);
512 
513  /* full star */
514  staredges = reduce_starGetNext(star, &nstaredges);
515  STPTEST_ASSERT(nstaredges == 4);
516  STPTEST_ASSERT(staredges[0] == 6);
517  STPTEST_ASSERT(staredges[1] == 4);
518  STPTEST_ASSERT(staredges[2] == 2);
519  STPTEST_ASSERT(staredges[3] == 0);
520 
521  /* 1st degree 3 star */
522  staredges = reduce_starGetNext(star, &nstaredges);
523  STPTEST_ASSERT(nstaredges == 3);
524  STPTEST_ASSERT(staredges[0] == 6);
525  STPTEST_ASSERT(staredges[1] == 4);
526  STPTEST_ASSERT(staredges[2] == 2);
527 
528 
529  /* 2nd degree 3 star */
530  staredges = reduce_starGetNext(star, &nstaredges);
531  STPTEST_ASSERT(nstaredges == 3);
532  STPTEST_ASSERT(staredges[0] == 6);
533  STPTEST_ASSERT(staredges[1] == 4);
534  STPTEST_ASSERT(staredges[2] == 0);
535 
536  /* 3rd degree 3 star */
537  staredges = reduce_starGetNext(star, &nstaredges);
538  STPTEST_ASSERT(nstaredges == 3);
539  STPTEST_ASSERT(staredges[0] == 6);
540  STPTEST_ASSERT(staredges[1] == 2);
541  STPTEST_ASSERT(staredges[2] == 0);
542 
543  reduce_starCurrentSetFailed(star);
544 
545  /* 4th degree 3 star */
546  staredges = reduce_starGetNext(star, &nstaredges);
547  STPTEST_ASSERT(nstaredges == 3);
548  STPTEST_ASSERT(staredges[0] == 4);
549  STPTEST_ASSERT(staredges[1] == 2);
550  STPTEST_ASSERT(staredges[2] == 0);
551 
552 
553  STPTEST_ASSERT(reduce_starHasPromisingEdges(star));
554  promisingedges = reduce_starGetRuledOutEdges(star, &nedgespromising);
555  STPTEST_ASSERT(nedgespromising == 1);
556  STPTEST_ASSERT(promisingedges[0] == 4);
557 
558  STPTEST_ASSERT(reduce_starAllAreChecked(star));
559 
560  stptest_graphTearDown(scip, graph);
561  reduce_starFree(scip, &star);
562 
563 
564  return SCIP_OKAY;
565 }
566 
567 
568 /** STAR of degree 5 should be correctly computed */
569 static
570 SCIP_RETCODE testStar5IsCorrect(
571  SCIP* scip /**< SCIP data structure */
572 )
573 {
574  STAR* star;
575  GRAPH* graph;
576  int nnodes = 6;
577  int nedges = 10;
578  int nstaredges = -1;
579  const int* staredges;
580 
581  SCIP_CALL( reduce_starInit(scip, 5, &star) );
582  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
583 
584  graph_knot_add(graph, STP_TERM);
585  for( int i = 1; i < nnodes; i++ )
586  graph_knot_add(graph, STP_TERM_NONE);
587 
588  graph->source = 0;
589 
590  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
591  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
592  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
593  graph_edge_addBi(scip, graph, 0, 4, 1.0); // 6
594  graph_edge_addBi(scip, graph, 0, 5, 1.0); // 8
595 
596  SCIP_CALL( stptest_graphSetUp(scip, graph) );
597 
598  reduce_starReset(graph, 0, star);
599 
600  /* full star */
601  staredges = reduce_starGetNext(star, &nstaredges);
602  STPTEST_ASSERT(nstaredges == 5);
603  STPTEST_ASSERT(staredges[0] == 8);
604  STPTEST_ASSERT(staredges[1] == 6);
605  STPTEST_ASSERT(staredges[2] == 4);
606  STPTEST_ASSERT(staredges[3] == 2);
607  STPTEST_ASSERT(staredges[4] == 0);
608 
609  /* 1st degree 4 star */
610  staredges = reduce_starGetNext(star, &nstaredges);
611  STPTEST_ASSERT(nstaredges == 4);
612  STPTEST_ASSERT(staredges[0] == 8);
613  STPTEST_ASSERT(staredges[1] == 6);
614  STPTEST_ASSERT(staredges[2] == 4);
615  STPTEST_ASSERT(staredges[3] == 2);
616 
617  /* 2nd degree 4 star */
618  staredges = reduce_starGetNext(star, &nstaredges);
619  STPTEST_ASSERT(nstaredges == 4);
620  STPTEST_ASSERT(staredges[0] == 8);
621  STPTEST_ASSERT(staredges[1] == 6);
622  STPTEST_ASSERT(staredges[2] == 4);
623  STPTEST_ASSERT(staredges[3] == 0);
624 
625  /* 3rd degree 4 star */
626  staredges = reduce_starGetNext(star, &nstaredges);
627  STPTEST_ASSERT(nstaredges == 4);
628  STPTEST_ASSERT(staredges[0] == 8);
629  STPTEST_ASSERT(staredges[1] == 6);
630  STPTEST_ASSERT(staredges[2] == 2);
631  STPTEST_ASSERT(staredges[3] == 0);
632 
633  /* 4th degree 4 star */
634  staredges = reduce_starGetNext(star, &nstaredges);
635  STPTEST_ASSERT(nstaredges == 4);
636  STPTEST_ASSERT(staredges[0] == 8);
637  STPTEST_ASSERT(staredges[1] == 4);
638  STPTEST_ASSERT(staredges[2] == 2);
639  STPTEST_ASSERT(staredges[3] == 0);
640 
641  /* 5th degree 4 star */
642  staredges = reduce_starGetNext(star, &nstaredges);
643  STPTEST_ASSERT(nstaredges == 4);
644  STPTEST_ASSERT(staredges[0] == 6);
645  STPTEST_ASSERT(staredges[1] == 4);
646  STPTEST_ASSERT(staredges[2] == 2);
647  STPTEST_ASSERT(staredges[3] == 0);
648 
649 
650  /* 1st degree 3 star */
651  staredges = reduce_starGetNext(star, &nstaredges);
652  STPTEST_ASSERT(nstaredges == 3);
653  STPTEST_ASSERT(staredges[0] == 8);
654  STPTEST_ASSERT(staredges[1] == 6);
655  STPTEST_ASSERT(staredges[2] == 4);
656 
657  /* 2nd degree 3 star */
658  staredges = reduce_starGetNext(star, &nstaredges);
659  STPTEST_ASSERT(nstaredges == 3);
660  STPTEST_ASSERT(staredges[0] == 8);
661  STPTEST_ASSERT(staredges[1] == 6);
662  STPTEST_ASSERT(staredges[2] == 2);
663 
664  /* 3rd degree 3 star */
665  staredges = reduce_starGetNext(star, &nstaredges);
666  STPTEST_ASSERT(nstaredges == 3);
667  STPTEST_ASSERT(staredges[0] == 8);
668  STPTEST_ASSERT(staredges[1] == 6);
669  STPTEST_ASSERT(staredges[2] == 0);
670 
671  /* 4th degree 3 star */
672  staredges = reduce_starGetNext(star, &nstaredges);
673  STPTEST_ASSERT(nstaredges == 3);
674  STPTEST_ASSERT(staredges[0] == 8);
675  STPTEST_ASSERT(staredges[1] == 4);
676  STPTEST_ASSERT(staredges[2] == 2);
677 
678  /* 5th degree 3 star */
679  staredges = reduce_starGetNext(star, &nstaredges);
680  STPTEST_ASSERT(nstaredges == 3);
681  STPTEST_ASSERT(staredges[0] == 8);
682  STPTEST_ASSERT(staredges[1] == 4);
683  STPTEST_ASSERT(staredges[2] == 0);
684 
685  /* 6th degree 3 star */
686  staredges = reduce_starGetNext(star, &nstaredges);
687  STPTEST_ASSERT(nstaredges == 3);
688  STPTEST_ASSERT(staredges[0] == 8);
689  STPTEST_ASSERT(staredges[1] == 2);
690  STPTEST_ASSERT(staredges[2] == 0);
691 
692  /* 7th degree 3 star */
693  staredges = reduce_starGetNext(star, &nstaredges);
694  STPTEST_ASSERT(nstaredges == 3);
695  STPTEST_ASSERT(staredges[0] == 6);
696  STPTEST_ASSERT(staredges[1] == 4);
697  STPTEST_ASSERT(staredges[2] == 2);
698 
699  /* 8th degree 3 star */
700  staredges = reduce_starGetNext(star, &nstaredges);
701  STPTEST_ASSERT(nstaredges == 3);
702  STPTEST_ASSERT(staredges[0] == 6);
703  STPTEST_ASSERT(staredges[1] == 4);
704  STPTEST_ASSERT(staredges[2] == 0);
705 
706  /* 9th degree 3 star */
707  staredges = reduce_starGetNext(star, &nstaredges);
708  STPTEST_ASSERT(nstaredges == 3);
709  STPTEST_ASSERT(staredges[0] == 6);
710  STPTEST_ASSERT(staredges[1] == 2);
711  STPTEST_ASSERT(staredges[2] == 0);
712 
713  /* 10th degree 3 star */
714  staredges = reduce_starGetNext(star, &nstaredges);
715  STPTEST_ASSERT(nstaredges == 3);
716  STPTEST_ASSERT(staredges[0] == 4);
717  STPTEST_ASSERT(staredges[1] == 2);
718  STPTEST_ASSERT(staredges[2] == 0);
719 
720  STPTEST_ASSERT(reduce_starAllAreChecked(star));
721 
722  stptest_graphTearDown(scip, graph);
723  reduce_starFree(scip, &star);
724 
725  return SCIP_OKAY;
726 }
727 
728 
729 /** tests that BLC works for a degree 3 star */
730 static
731 SCIP_RETCODE testBLCworksFor3Star(
732  SCIP* scip /**< SCIP data structure */
733 )
734 {
735  BLCTREE* blctree;
736  GRAPH* graph;
737  int nnodes = 4;
738  int nedges = 10;
739  int mstedges[3];
740  SCIP_Real bottlenecks[3];
741 
742  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
743 
744  graph_knot_add(graph, STP_TERM);
745  for( int i = 1; i < nnodes; i++ )
746  graph_knot_add(graph, STP_TERM_NONE);
747 
748  graph->source = 0;
749 
750  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
751  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
752  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
753  graph_edge_addBi(scip, graph, 1, 2, 2.0); // 6
754  graph_edge_addBi(scip, graph, 2, 3, 3.0); // 8
755 
756  SCIP_CALL( stptest_graphSetUp(scip, graph) );
757  SCIP_CALL( reduce_blctreeInit(scip, graph, &blctree) );
758 
759  reduce_blctreeGetMstEdges(graph, blctree, mstedges);
760  reduce_blctreeGetMstBottlenecks(graph, blctree, bottlenecks);
761 
762  for( int i = 0; i < 3; i++ )
763  {
764  const int edge = mstedges[i];
765  assert(0 <= edge && edge < nedges);
766 
767  if( (edge / 2) * 2 == 0 )
768  {
769  STPTEST_ASSERT(EQ(bottlenecks[i], 2.0));
770  }
771  else if( (edge / 2) * 2 == 2 )
772  {
773  STPTEST_ASSERT(EQ(bottlenecks[i], 2.0));
774  }
775  else
776  {
777  STPTEST_ASSERT((edge / 2) * 2 == 4);
778  STPTEST_ASSERT(EQ(bottlenecks[i], 3.0));
779  }
780  }
781 
782  stptest_graphTearDown(scip, graph);
783  reduce_blctreeFree(scip, &blctree);
784 
785  return SCIP_OKAY;
786 }
787 
788 
789 
790 /** tests that BLC works for a degree 3 star even after edges have been deleted */
791 static
792 SCIP_RETCODE testBLCworksFor3StarAfterReduction(
793  SCIP* scip /**< SCIP data structure */
794 )
795 {
796  BLCTREE* blctree;
797  GRAPH* graph;
798  int nnodes = 4;
799  int nedges = 12;
800  int mstedges[3];
801  SCIP_Real bottlenecks[3];
802 
803  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
804 
805  graph_knot_add(graph, STP_TERM);
806  for( int i = 1; i < nnodes; i++ )
807  graph_knot_add(graph, STP_TERM_NONE);
808 
809  graph->source = 0;
810 
811  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
812  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2
813  graph_edge_addBi(scip, graph, 0, 3, 1.0); // 4
814  graph_edge_addBi(scip, graph, 1, 2, 2.0); // 6
815  graph_edge_addBi(scip, graph, 2, 3, 3.0);
816  graph_edge_addBi(scip, graph, 1, 3, 1.5); // 10
817 
818  SCIP_CALL( stptest_graphSetUp(scip, graph) );
819 
820  graph_edge_del(scip, graph, 6, TRUE);
821  graph_edge_del(scip, graph, 10, TRUE);
822 
823  SCIP_CALL( reduce_blctreeInit(scip, graph, &blctree) );
824  reduce_blctreeGetMstEdges(graph, blctree, mstedges);
825  reduce_blctreeGetMstBottlenecks(graph, blctree, bottlenecks);
826 
827  for( int i = 0; i < 3; i++ )
828  {
829  const int edge = mstedges[i];
830  assert(0 <= edge && edge < nedges);
831 
832  if( (edge / 2) * 2 == 0 )
833  {
834  STPTEST_ASSERT(EQ(bottlenecks[i], FARAWAY));
835  }
836  else if( (edge / 2) * 2 == 2 )
837  {
838  STPTEST_ASSERT(EQ(bottlenecks[i], 3.0));
839  }
840  else
841  {
842  STPTEST_ASSERT((edge / 2) * 2 == 4);
843  STPTEST_ASSERT(EQ(bottlenecks[i], 3.0));
844  }
845  }
846 
847  stptest_graphTearDown(scip, graph);
848  reduce_blctreeFree(scip, &blctree);
849 
850  return SCIP_OKAY;
851 }
852 
853 /** tests that BLC works for a tree with five nodes */
854 static
855 SCIP_RETCODE testBLCworksFor5Tree(
856  SCIP* scip /**< SCIP data structure */
857 )
858 {
859  BLCTREE* blctree;
860  GRAPH* graph;
861  int nnodes = 5;
862  int nedges = 16;
863  int mstedges[4];
864  SCIP_Real bottlenecks[4];
865 
866  SCIP_CALL( graph_init(scip, &graph, nnodes, nedges, 1) );
867 
868  graph_knot_add(graph, STP_TERM);
869  for( int i = 1; i < nnodes; i++ )
870  graph_knot_add(graph, STP_TERM_NONE);
871 
872  graph->source = 0;
873  graph_knot_chg(graph, 3, STP_TERM);
874 
875  /* the MST edges */
876  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0
877  graph_edge_addBi(scip, graph, 0, 2, 1.1); // 2
878  graph_edge_addBi(scip, graph, 2, 3, 1.2); // 4
879  graph_edge_addBi(scip, graph, 2, 4, 1.3); // 6
880 
881  /* additional edges */
882  graph_edge_addBi(scip, graph, 0, 4, 1.4);
883  graph_edge_addBi(scip, graph, 1, 2, 1.5);
884  graph_edge_addBi(scip, graph, 3, 4, 1.6);
885  graph_edge_addBi(scip, graph, 1, 3, 1.7);
886 
887  SCIP_CALL( stptest_graphSetUp(scip, graph) );
888  SCIP_CALL( reduce_blctreeInit(scip, graph, &blctree) );
889 
890  reduce_blctreeGetMstEdges(graph, blctree, mstedges);
891  reduce_blctreeGetMstBottlenecks(graph, blctree, bottlenecks);
892 
893  for( int i = 0; i < 4; i++ )
894  {
895  const int edge = mstedges[i];
896  assert(0 <= edge && edge < nedges);
897 
898  if( (edge / 2) * 2 == 0 )
899  {
900  STPTEST_ASSERT(EQ(bottlenecks[i], 1.5));
901  }
902  else if( (edge / 2) * 2 == 2 )
903  {
904  STPTEST_ASSERT(EQ(bottlenecks[i], 1.4));
905  }
906  else if( (edge / 2) * 2 == 4 )
907  {
908  STPTEST_ASSERT(EQ(bottlenecks[i], 1.6));
909  }
910  else
911  {
912  STPTEST_ASSERT((edge / 2) * 2 == 6);
913  STPTEST_ASSERT(EQ(bottlenecks[i], 1.4));
914  }
915  }
916 
917  stptest_graphTearDown(scip, graph);
918  reduce_blctreeFree(scip, &blctree);
919 
920  return SCIP_OKAY;
921 }
922 
923 
924 /** tests DCMST */
925 SCIP_RETCODE stptest_dcmst(
926  SCIP* scip /**< SCIP data structure */
927 )
928 {
929  SCIP_CALL( dcmstTest1(scip) );
930  SCIP_CALL( dcmstTest2(scip) );
931  SCIP_CALL( dcmstTest2b(scip) );
932  SCIP_CALL( dcmstTest3(scip) );
933 
934  printf("dcmst test: all ok \n");
935 
936  return SCIP_OKAY;
937 }
938 
939 
940 /** tests STAR methods */
941 SCIP_RETCODE stptest_reduceStar(
942  SCIP* scip /**< SCIP data structure */
943 )
944 {
945  SCIP_CALL( testStar3IsCorrect(scip) );
946  SCIP_CALL( testStar4IsCorrect(scip) );
947  SCIP_CALL( testStar4EdgeIsCorrect(scip) );
948  SCIP_CALL( testStar5IsCorrect(scip) );
949 
950  printf("reduce star test: all ok \n");
951 
952  return SCIP_OKAY;
953 }
954 
955 
956 /** tests bottleneck tree methods */
957 SCIP_RETCODE stptest_reduceBLCtree(
958  SCIP* scip /**< SCIP data structure */
959 )
960 {
961  SCIP_CALL( testBLCworksFor3Star(scip) );
962  SCIP_CALL( testBLCworksFor3StarAfterReduction(scip) );
963  SCIP_CALL( testBLCworksFor5Tree(scip) );
964 
965  printf("reduce BLC tree test: all ok \n");
966 
967  return SCIP_OKAY;
968 }
graph_csr_copy
void graph_csr_copy(const CSR *, CSR *)
Definition: graph_util.c:1483
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
STPTEST_ASSERT
#define STPTEST_ASSERT(cond)
Definition: stptest.h:63
graph_edge_del
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
testBLCworksFor3StarAfterReduction
static SCIP_RETCODE testBLCworksFor3StarAfterReduction(SCIP *scip)
Definition: stptest_reduceutils.c:792
GRAPH::source
int source
Definition: graphdefs.h:195
reduce_blctreeGetMstEdges
void reduce_blctreeGetMstEdges(const GRAPH *, const BLCTREE *, int *)
Definition: reduce_util.c:1230
graph_edge_addBi
void graph_edge_addBi(SCIP *, GRAPH *, int, int, double)
reduce_starAllAreChecked
SCIP_Bool reduce_starAllAreChecked(const STAR *)
Definition: reduce_util.c:2002
stptest_reduceBLCtree
SCIP_RETCODE stptest_reduceBLCtree(SCIP *scip)
Definition: stptest_reduceutils.c:957
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
testStar4EdgeIsCorrect
static SCIP_RETCODE testStar4EdgeIsCorrect(SCIP *scip)
Definition: stptest_reduceutils.c:480
reduce_dcmstInit
SCIP_RETCODE reduce_dcmstInit(SCIP *, int, DCMST **)
Definition: reduce_util.c:1385
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:87
reduce_starGetRuledOutEdges
const int * reduce_starGetRuledOutEdges(STAR *, int *)
Definition: reduce_util.c:1918
FARAWAY
#define FARAWAY
Definition: graphdefs.h:89
reduce_starHasPromisingEdges
SCIP_Bool reduce_starHasPromisingEdges(const STAR *)
Definition: reduce_util.c:1990
testStar4IsCorrect
static SCIP_RETCODE testStar4IsCorrect(SCIP *scip)
Definition: stptest_reduceutils.c:401
reduce_starInit
SCIP_RETCODE reduce_starInit(SCIP *, int, STAR **)
Definition: reduce_util.c:1725
testStar5IsCorrect
static SCIP_RETCODE testStar5IsCorrect(SCIP *scip)
Definition: stptest_reduceutils.c:570
reduce_blctreeInit
SCIP_RETCODE reduce_blctreeInit(SCIP *, GRAPH *, BLCTREE **)
Definition: reduce_util.c:1168
STP_TERM_NONE
#define STP_TERM_NONE
Definition: graphdefs.h:62
testBLCworksFor3Star
static SCIP_RETCODE testBLCworksFor3Star(SCIP *scip)
Definition: stptest_reduceutils.c:731
reduce_dcmstAddNode
void reduce_dcmstAddNode(SCIP *, const CSR *, const SCIP_Real *, DCMST *, CSR *)
Definition: reduce_util.c:1411
dcmstTest2
static SCIP_RETCODE dcmstTest2(SCIP *scip)
Definition: stptest_reduceutils.c:113
reduce_dcmstGet2NodeMst
void reduce_dcmstGet2NodeMst(SCIP *, SCIP_Real, CSR *)
Definition: reduce_util.c:1498
stptest_reduceStar
SCIP_RETCODE stptest_reduceStar(SCIP *scip)
Definition: stptest_reduceutils.c:941
reduce_starFree
void reduce_starFree(SCIP *, STAR **)
Definition: reduce_util.c:1758
reduce_dcmstGet1NodeMst
void reduce_dcmstGet1NodeMst(SCIP *, CSR *)
Definition: reduce_util.c:1479
csr_storage::nedges_max
int nedges_max
Definition: graphdefs.h:144
reduce_dcmstGetWeight
SCIP_Real reduce_dcmstGetWeight(SCIP *, const CSR *)
Definition: reduce_util.c:1573
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
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
graph_csr_alloc
SCIP_RETCODE graph_csr_alloc(SCIP *, int, int, CSR **)
Definition: graph_util.c:1231
testStar3IsCorrect
static SCIP_RETCODE testStar3IsCorrect(SCIP *scip)
Definition: stptest_reduceutils.c:357
SCIP_ERROR
Definition: type_retcode.h:34
stptest_graphTearDown
void stptest_graphTearDown(SCIP *, GRAPH *)
Definition: stptest_graph.c:274
reduce_starGetNext
const int * reduce_starGetNext(STAR *, int *)
Definition: reduce_util.c:1863
dcmstTest1
static SCIP_RETCODE dcmstTest1(SCIP *scip)
Definition: stptest_reduceutils.c:39
testBLCworksFor5Tree
static SCIP_RETCODE testBLCworksFor5Tree(SCIP *scip)
Definition: stptest_reduceutils.c:855
dcmstTest3
static SCIP_RETCODE dcmstTest3(SCIP *scip)
Definition: stptest_reduceutils.c:244
dcmstTest2b
static SCIP_RETCODE dcmstTest2b(SCIP *scip)
Definition: stptest_reduceutils.c:179
STP_TERM
#define STP_TERM
Definition: graphdefs.h:61
reduce_starReset
void reduce_starReset(const GRAPH *, int, STAR *)
Definition: reduce_util.c:1781
reduce_starCurrentSetFailed
void reduce_starCurrentSetFailed(STAR *)
Definition: reduce_util.c:1960
stptest_dcmst
SCIP_RETCODE stptest_dcmst(SCIP *scip)
Definition: stptest_reduceutils.c:925
csr_storage
Definition: graphdefs.h:138
portab.h
Portable definitions.
bottleneck_link_cut_tree
Definition: reduce_util.c:84
reduce_dcmstFree
void reduce_dcmstFree(SCIP *, DCMST **)
Definition: reduce_util.c:1634
stptest.h
includes various testing methods for Steiner tree problems
dynamic_complete_minimum_spanning_tree
Definition: reduce_util.c:43
stptest_graphSetUp
SCIP_RETCODE stptest_graphSetUp(SCIP *, GRAPH *)
Definition: stptest_graph.c:286
graph_csr_free
void graph_csr_free(SCIP *, CSR **)
Definition: graph_util.c:1554
SCIP_Real
#define SCIP_Real
Definition: def.h:177
nnodes
#define nnodes
Definition: gastrans.c:65
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
reduce_blctreeFree
void reduce_blctreeFree(SCIP *, BLCTREE **)
Definition: reduce_util.c:1201
reduce.h
includes various reduction methods for Steiner tree problems
reduce_blctreeGetMstBottlenecks
void reduce_blctreeGetMstBottlenecks(const GRAPH *, const BLCTREE *, SCIP_Real *)
Definition: reduce_util.c:1349
csr_storage::nnodes
int nnodes
Definition: graphdefs.h:145