Scippy

SCIP

Solving Constraint Integer Programs

stptest_pcreduce.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_pcreduce.c
17  * @brief tests for Steiner tree reductions
18  * @author Daniel Rehfeldt
19  *
20  * This file implements unit tests for Steiner problem PC/MW reductions.
21  *
22  * A list of all interface methods can be found in stptest.h.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 //#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 "heur_local.h"
35 #include "heur_tm.h"
36 #include "portab.h"
37 
38 
39 static
40 SCIP_RETCODE checkSdWalk(
41  SCIP* scip, /**< SCIP data structure */
42  SCIP_Bool extended, /**< graph in extended state? */
43  GRAPH** g, /**< graph data structure */
44  int* nelims /**< pointer to number of eliminations */
45 )
46 {
47  DHEAP* dheap;
48  int nnodes;
49  int nedges;
50  int* nodearr_int1;
51  int* nodearr_int2;
52  int* vbase;
53  int* state;
54  int* heap;
55  SCIP_Real* edgearrreal1;
56 
57  SCIP_Real* nodearrreal1;
58  SCIP_Bool* isterm;
59  STP_Bool* nodearrchar;
60  GRAPH* graph = *g;
61 
62  /* build PC graph */
63  SCIP_CALL( graph_transPc(scip, graph) );
64 
65  nnodes = graph->knots;
66  nedges = graph->edges;
67 
68  SCIP_CALL( graph_initHistory(scip, graph) );
69  SCIP_CALL( graph_path_init(scip, graph) );
70 
71  graph_mark(graph);
72 
73  graph_pc_2org(scip, graph);
74 
75  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
76  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal1, nedges) );
77  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal1, nnodes) );
78  SCIP_CALL( SCIPallocBufferArray(scip, &nodearr_int1, nnodes) );
79  SCIP_CALL( SCIPallocBufferArray(scip, &nodearr_int2, nnodes) );
80  SCIP_CALL( SCIPallocBufferArray(scip, &isterm, nnodes) );
81 
82  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 4 * nnodes) );
83  SCIP_CALL( SCIPallocBufferArray(scip, &state, 4 * nnodes) );
84  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, 4 * nnodes) );
85 
86  graph_heap_create(scip, nnodes, NULL, NULL, &dheap);
87 
88  graph_getIsTermArray(graph, isterm);
89 
90  /* actual test */
91 
92  if( extended )
93  {
94  SCIP_CALL( reduce_sdWalkExt(scip, 200, TRUE, graph, nodearrreal1, heap, state, vbase, nodearrchar, nelims) );
95  }
96  else
97  {
98  SCIP_CALL( reduce_sdWalkTriangle(scip, 5, TRUE, graph, nodearr_int1, nodearrreal1, heap, nodearrchar, dheap, nelims));
99  }
100 
101  /* clean up */
102 
103  graph_heap_free(scip, TRUE, TRUE, &dheap);
104  graph_path_exit(scip, graph);
105  graph_free(scip, g, TRUE);
106 
107  SCIPfreeBufferArray(scip, &nodearrchar);
108  SCIPfreeBufferArray(scip, &state);
109  SCIPfreeBufferArray(scip, &vbase);
110 
111  SCIPfreeBufferArray(scip, &isterm);
112  SCIPfreeBufferArray(scip, &nodearr_int2);
113  SCIPfreeBufferArray(scip, &nodearr_int1);
114  SCIPfreeBufferArray(scip, &nodearrreal1);
115  SCIPfreeBufferArray(scip, &edgearrreal1);
116  SCIPfreeBufferArray(scip, &heap);
117 
118  return SCIP_OKAY;
119 }
120 
121 
122 
123 
124 
125 /** tests chain2 RMW test */
126 static
127 SCIP_RETCODE testRmwChain2DeletesNode(
128  SCIP* scip /**< SCIP data structure */
129 )
130 {
131  GRAPH* graph;
132  const int nnodes_org = 6;
133  const int nedges_org = 12;
134  int nelims = 0;
135  int nnodes;
136  PATH* pathtail;
137  int* heap;
138  int* statetail;
139  int* statehead;
140 
141  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
142 
143  for( int i = 0; i < nnodes_org; i++ )
144  graph_knot_add(graph, STP_TERM_NONE);
145 
146  graph_knot_chg(graph, 5, STP_TERM);
147  graph->source = 5;
148 
149  graph_edge_addBi(scip, graph, 0, 1, 0.0); // 0,1
150  graph_edge_addBi(scip, graph, 0, 2, 0.0); // 2,3
151  graph_edge_addBi(scip, graph, 1, 3, 0.0);
152  graph_edge_addBi(scip, graph, 2, 4, 0.0);
153  graph_edge_addBi(scip, graph, 3, 5, 0.0);
154  graph_edge_addBi(scip, graph, 4, 5, 0.0);
155 
156 
157  graph_pc_initPrizes(scip, graph, nnodes_org);
158  graph->prize[0] = -1.5;
159  graph->prize[1] = -12.5;
160  graph->prize[2] = -11.5;
161  graph->prize[3] = -1.5;
162  graph->prize[4] = -1.5;
163  graph->prize[5] = FARAWAY;
164 
165  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, &nnodes, NULL) );
166 
167  SCIP_CALL( SCIPallocMemoryArray(scip, &pathtail, nnodes) );
168  SCIP_CALL( SCIPallocMemoryArray(scip, &heap, nnodes) );
169  SCIP_CALL( SCIPallocMemoryArray(scip, &statetail, nnodes) );
170  SCIP_CALL( SCIPallocMemoryArray(scip, &statehead, nnodes) );
171 
172  SCIP_CALL( reduce_chain2(scip, graph, pathtail, heap, statetail, statehead, &nelims, 10) );
173 
174  STPTEST_ASSERT(graph->grad[0] == 0);
175 
176  for( int i = 1; i < nnodes_org; i++ )
177  STPTEST_ASSERT(graph->grad[i] != 0);
178 
179  stptest_graphTearDown(scip, graph);
180 
181  SCIPfreeMemoryArray(scip, &pathtail);
182  SCIPfreeMemoryArray(scip, &heap);
183  SCIPfreeMemoryArray(scip, &statetail);
184  SCIPfreeMemoryArray(scip, &statehead);
185 
186  return SCIP_OKAY;
187 }
188 
189 
190 
191 /** tests NPV RMW test */
192 static
193 SCIP_RETCODE testRmwNpv3DeletesNode(
194  SCIP* scip /**< SCIP data structure */
195 )
196 {
197  GRAPH* graph;
198  const int nnodes_org = 7;
199  const int nedges_org = 18;
200  int nelims = 0;
201  int nnodes;
202  PATH* pathtail;
203  int* heap;
204  int* statetail;
205  int* statehead;
206 
207  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
208 
209  for( int i = 0; i < nnodes_org; i++ )
210  graph_knot_add(graph, STP_TERM_NONE);
211 
212  graph_knot_chg(graph, 3, STP_TERM);
213  graph->source = 3;
214 
215  // star
216  graph_edge_addBi(scip, graph, 0, 1, 0.0); // 0,1
217  graph_edge_addBi(scip, graph, 0, 2, 0.0); // 2,3
218  graph_edge_addBi(scip, graph, 0, 3, 0.0);
219 
220  // cycle
221  graph_edge_addBi(scip, graph, 1, 4, 0.0);
222  graph_edge_addBi(scip, graph, 1, 6, 0.0);
223  graph_edge_addBi(scip, graph, 2, 4, 0.0);
224  graph_edge_addBi(scip, graph, 2, 5, 0.0);
225  graph_edge_addBi(scip, graph, 3, 5, 0.0);
226  graph_edge_addBi(scip, graph, 3, 6, 0.0);
227 
228 
229  graph_pc_initPrizes(scip, graph, nnodes_org);
230  graph->prize[0] = -1.0;
231  graph->prize[1] = -12.5;
232  graph->prize[2] = -11.5;
233  graph->prize[3] = FARAWAY;
234  graph->prize[4] = -1.5;
235  graph->prize[5] = -0.6;
236  graph->prize[6] = -0.4;
237 
238  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, &nnodes, NULL) );
239 
240  SCIP_CALL( SCIPallocMemoryArray(scip, &pathtail, nnodes) );
241  SCIP_CALL( SCIPallocMemoryArray(scip, &heap, nnodes) );
242  SCIP_CALL( SCIPallocMemoryArray(scip, &statetail, nnodes) );
243  SCIP_CALL( SCIPallocMemoryArray(scip, &statehead, nnodes) );
244 
245  SCIP_CALL( reduce_npv(scip, graph, pathtail, heap, statetail, statehead, &nelims, 10) );
246 
247  STPTEST_ASSERT(graph->grad[0] == 0);
248 
249 
250  stptest_graphTearDown(scip, graph);
251 
252  SCIPfreeMemoryArray(scip, &pathtail);
253  SCIPfreeMemoryArray(scip, &heap);
254  SCIPfreeMemoryArray(scip, &statetail);
255  SCIPfreeMemoryArray(scip, &statehead);
256 
257  return SCIP_OKAY;
258 }
259 
260 
261 /** tests ANS RMW test */
262 static
263 SCIP_RETCODE testRmwAnsDeletesOneNode(
264  SCIP* scip /**< SCIP data structure */
265 )
266 {
267  GRAPH* graph;
268  const int nnodes_org = 5;
269  const int nedges_org = 12;
270  int nelims = 0;
271 
272  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
273 
274  for( int i = 0; i < nnodes_org; i++ )
275  graph_knot_add(graph, STP_TERM_NONE);
276 
277  graph_knot_chg(graph, 3, STP_TERM);
278  graph->source = 3;
279 
280  graph_knot_chg(graph, 4, STP_TERM);
281 
282  graph_edge_addBi(scip, graph, 0, 1, 0.0); // 0,1
283  graph_edge_addBi(scip, graph, 0, 2, 0.0); // 2,3
284  graph_edge_addBi(scip, graph, 0, 3, 0.0);
285  graph_edge_addBi(scip, graph, 1, 2, 0.0);
286  graph_edge_addBi(scip, graph, 1, 3, 0.0);
287  graph_edge_addBi(scip, graph, 2, 4, 0.0);
288 
289  graph_pc_initPrizes(scip, graph, nnodes_org);
290  graph->prize[0] = -1.0;
291  graph->prize[1] = -1.0;
292  graph->prize[2] = -0.5;
293  graph->prize[3] = FARAWAY;
294  graph->prize[4] = 2.0;
295 
296  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, NULL, NULL) );
297 
298  SCIP_CALL( reduce_ans(scip, graph, &nelims) );
299 
300  STPTEST_ASSERT(graph->grad[1] == 0);
301  STPTEST_ASSERT(graph->grad[0] != 0);
302  STPTEST_ASSERT(graph->grad[2] != 0);
303  STPTEST_ASSERT(graph->grad[3] != 0);
304  STPTEST_ASSERT(graph->grad[4] != 0);
305 
306 
307  stptest_graphTearDown(scip, graph);
308 
309  return SCIP_OKAY;
310 }
311 
312 
313 
314 /** test ANS RMW test */
315 static
316 SCIP_RETCODE testRmwAnsDeletesOneEdge(
317  SCIP* scip /**< SCIP data structure */
318 )
319 {
320  GRAPH* graph;
321  const int nnodes_org = 7;
322  const int nedges_org = 20;
323  int nelims = 0;
324 
325  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
326 
327  for( int i = 0; i < nnodes_org; i++ )
328  graph_knot_add(graph, STP_TERM_NONE);
329 
330  graph_knot_chg(graph, 4, STP_TERM);
331  graph->source = 4;
332 
333  graph_knot_chg(graph, 6, STP_TERM);
334 
335  graph_edge_addBi(scip, graph, 1, 5, 0.0); // edge to be deleted
336  graph_edge_addBi(scip, graph, 0, 1, 0.0);
337  graph_edge_addBi(scip, graph, 0, 2, 0.0);
338  graph_edge_addBi(scip, graph, 0, 3, 0.0);
339  graph_edge_addBi(scip, graph, 0, 6, 0.0);
340  graph_edge_addBi(scip, graph, 1, 2, 0.0);
341  graph_edge_addBi(scip, graph, 1, 3, 0.0);
342  graph_edge_addBi(scip, graph, 2, 4, 0.0);
343  graph_edge_addBi(scip, graph, 3, 4, 0.0);
344  graph_edge_addBi(scip, graph, 3, 5, 0.0);
345 
346  graph_pc_initPrizes(scip, graph, nnodes_org);
347  graph->prize[0] = -1.0;
348  graph->prize[1] = -0.6;
349  graph->prize[2] = -0.5;
350  graph->prize[3] = -2.0;
351  graph->prize[4] = FARAWAY;
352  graph->prize[5] = -0.4;
353  graph->prize[6] = 0.4;
354 
355  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, NULL, NULL) );
356 
357  SCIP_CALL( reduce_ans(scip, graph, &nelims) );
358 
359  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
360 
361  for( int i = 0; i < nnodes_org; i++ )
362  STPTEST_ASSERT(graph->grad[i] != 0);
363 
364  stptest_graphTearDown(scip, graph);
365 
366  return SCIP_OKAY;
367 }
368 
369 
370 
371 /** test ANS RMW test */
372 static
373 SCIP_RETCODE testRmwAnsDeletesTwoNodes(
374  SCIP* scip /**< SCIP data structure */
375 )
376 {
377  GRAPH* graph;
378  const int nnodes_org = 7;
379  const int nedges_org = 20;
380  int nelims = 0;
381 
382  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
383 
384  for( int i = 0; i < nnodes_org; i++ )
385  graph_knot_add(graph, STP_TERM_NONE);
386 
387  graph_knot_chg(graph, 4, STP_TERM);
388  graph->source = 4;
389 
390  graph_knot_chg(graph, 6, STP_TERM);
391 
392  graph_edge_addBi(scip, graph, 1, 5, 0.0); // edge to be deleted
393  graph_edge_addBi(scip, graph, 0, 1, 0.0);
394  graph_edge_addBi(scip, graph, 0, 2, 0.0);
395  graph_edge_addBi(scip, graph, 0, 3, 0.0);
396  graph_edge_addBi(scip, graph, 0, 6, 0.0);
397  graph_edge_addBi(scip, graph, 1, 2, 0.0);
398  graph_edge_addBi(scip, graph, 1, 3, 0.0);
399  graph_edge_addBi(scip, graph, 2, 4, 0.0);
400  graph_edge_addBi(scip, graph, 3, 4, 0.0);
401  graph_edge_addBi(scip, graph, 3, 5, 0.0);
402 
403  graph_pc_initPrizes(scip, graph, nnodes_org);
404  graph->prize[0] = -1.0;
405  graph->prize[1] = -1.1;
406  graph->prize[2] = -0.5;
407  graph->prize[3] = -2.0;
408  graph->prize[4] = FARAWAY;
409  graph->prize[5] = -1.0;
410  graph->prize[6] = 0.4;
411 
412  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, NULL, NULL) );
413 
414  SCIP_CALL( reduce_ans(scip, graph, &nelims) );
415 
416  STPTEST_ASSERT(graph->grad[1] == 0);
417  STPTEST_ASSERT(graph->grad[5] == 0);
418 
419  stptest_graphTearDown(scip, graph);
420 
421  return SCIP_OKAY;
422 }
423 
424 
425 /** test simple RMW test */
426 static
427 SCIP_RETCODE testRmwTerminalContraction(
428  SCIP* scip /**< SCIP data structure */
429 )
430 {
431  GRAPH* graph;
432  SCIP_Real offset = 0.0;
433  const int nnodes_org = 4;
434  const int nedges_org = 10;
435  int nelims = 0;
436 
437  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
438 
439  for( int i = 0; i < nnodes_org; i++ )
440  graph_knot_add(graph, STP_TERM_NONE);
441 
442  graph_knot_chg(graph, 0, STP_TERM);
443  graph_knot_chg(graph, 3, STP_TERM);
444  graph->source = 0;
445 
446  graph_edge_addBi(scip, graph, 3, 1, 0.0); // 0,1
447  graph_edge_addBi(scip, graph, 3, 2, 0.0); // 2,3
448  graph_edge_addBi(scip, graph, 0, 3, 0.0);
449  graph_edge_addBi(scip, graph, 1, 2, 0.0);
450  graph_edge_addBi(scip, graph, 2, 3, 0.0);
451 
452  graph_pc_initPrizes(scip, graph, nnodes_org);
453  graph->prize[0] = FARAWAY;
454  graph->prize[1] = -1.0;
455  graph->prize[2] = -5.0;
456  graph->prize[3] = 2.0;
457 
458  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, NULL, NULL) );
459 
460  SCIP_CALL( reduce_simple_mw(scip, graph, NULL, &offset, &nelims) );
461 
462  STPTEST_ASSERT(graph->grad[3] == 0);
463 
464  stptest_graphTearDown(scip, graph);
465 
466  return SCIP_OKAY;
467 }
468 
469 
470 /** test simple RMW test */
471 static
472 SCIP_RETCODE testRmwTerminalDeg1Contraction1(
473  SCIP* scip /**< SCIP data structure */
474 )
475 {
476  GRAPH* graph;
477  SCIP_Real offset = 0.0;
478  const int nnodes_org = 3;
479  const int nedges_org = 4;
480  int nelims = 0;
481 
482  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
483 
484  for( int i = 0; i < nnodes_org; i++ )
485  graph_knot_add(graph, STP_TERM_NONE);
486 
487  graph_knot_chg(graph, 1, STP_TERM);
488  graph_knot_chg(graph, 2, STP_TERM);
489 
490  graph_edge_addBi(scip, graph, 0, 1, 0.0);
491  graph_edge_addBi(scip, graph, 0, 2, 0.0);
492  graph->source = 2;
493 
494  graph_pc_initPrizes(scip, graph, nnodes_org);
495  graph->prize[0] = -1.0;
496  graph->prize[1] = 1.5;
497  graph->prize[2] = FARAWAY;
498 
499  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, NULL, NULL) );
500 
501  SCIP_CALL( reduce_simple_mw(scip, graph, NULL, &offset, &nelims) );
502 
503  STPTEST_ASSERT(graph->grad[graph->source] == 0);
504 
505  stptest_graphTearDown(scip, graph);
506 
507  return SCIP_OKAY;
508 }
509 
510 /** test simple RMW test */
511 static
512 SCIP_RETCODE testRmwTerminalDeg1Contraction2(
513  SCIP* scip /**< SCIP data structure */
514 )
515 {
516  GRAPH* graph;
517  SCIP_Real offset = 0.0;
518  const int nnodes_org = 3;
519  const int nedges_org = 4;
520  int nelims = 0;
521 
522  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
523 
524  for( int i = 0; i < nnodes_org; i++ )
525  graph_knot_add(graph, STP_TERM_NONE);
526 
527  graph_knot_chg(graph, 1, STP_TERM);
528  graph_knot_chg(graph, 2, STP_TERM);
529 
530  graph_edge_addBi(scip, graph, 0, 1, 0.0);
531  graph_edge_addBi(scip, graph, 0, 2, 0.0);
532  graph->source = 2;
533 
534  graph_pc_initPrizes(scip, graph, nnodes_org);
535  graph->prize[0] = -1.0;
536  graph->prize[1] = 0.5;
537  graph->prize[2] = FARAWAY;
538 
539  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, NULL, NULL) );
540 
541  SCIP_CALL( reduce_simple_mw(scip, graph, NULL, &offset, &nelims) );
542 
543  STPTEST_ASSERT(EQ(offset, 0.5));
544  STPTEST_ASSERT(graph->grad[graph->source] == 0);
545 
546  stptest_graphTearDown(scip, graph);
547 
548  return SCIP_OKAY;
549 }
550 
551 
552 /** test simple RMW test */
553 static
554 SCIP_RETCODE testRmwTerminalDeg1Contraction3(
555  SCIP* scip /**< SCIP data structure */
556 )
557 {
558  GRAPH* graph;
559  SCIP_Real offset = 0.0;
560  const int nnodes_org = 3;
561  const int nedges_org = 4;
562  int nelims = 0;
563 
564  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
565 
566  for( int i = 0; i < nnodes_org; i++ )
567  graph_knot_add(graph, STP_TERM_NONE);
568 
569  graph_knot_chg(graph, 1, STP_TERM);
570  graph_knot_chg(graph, 2, STP_TERM);
571 
572  graph_edge_addBi(scip, graph, 0, 1, 0.0);
573  graph_edge_addBi(scip, graph, 0, 2, 0.0);
574  graph->source = 2;
575 
576  graph_pc_initPrizes(scip, graph, nnodes_org);
577  graph->prize[0] = -1.0;
578  graph->prize[1] = FARAWAY;
579  graph->prize[2] = FARAWAY;
580 
581  SCIP_CALL( stptest_graphSetUpRmwOrg(scip, graph, NULL, NULL) );
582 
583  SCIP_CALL( reduce_simple_mw(scip, graph, NULL, &offset, &nelims) );
584 
585  STPTEST_ASSERT(EQ(offset, 1.0));
586  STPTEST_ASSERT(graph->grad[graph->source] == 0);
587 
588  stptest_graphTearDown(scip, graph);
589 
590  return SCIP_OKAY;
591 }
592 
593 
594 static
595 SCIP_RETCODE testSdPcKillsEdge1(
596  SCIP* scip /**< SCIP data structure */
597 )
598 {
599  GRAPH* graph;
600  int nelims;
601  const int nnodes = 3;
602  const int nedges = 3;
603 
604  assert(scip);
605 
606  SCIP_CALL( graph_init(scip, &graph, nnodes, 2 * nedges, 1) );
607 
608  /* build graph */
609  graph_knot_add(graph, 0);
610  for( int i = 1; i < nnodes; i++ )
611  graph_knot_add(graph, -1);
612 
613  graph->source = 0;
614 
615  graph_edge_add(scip, graph, 0, 1, 1.0, 1.0);
616  graph_edge_add(scip, graph, 0, 2, 1.0, 1.0);
617  graph_edge_add(scip, graph, 1, 2, 1.0, 1.0);
618 
619  SCIP_CALL( graph_pc_initPrizes(scip, graph, nnodes) );
620 
621  for( int i = 0; i < nnodes; i++ )
622  graph->prize[i] = 0.0;
623 
624  graph->prize[0] = 1.0;
625 
626  nelims = 0;
627 
628  SCIP_CALL( checkSdWalk(scip, FALSE, &graph, &nelims) );
629 
630  STPTEST_ASSERT(nelims == 1);
631  assert(graph == NULL);
632 
633  return SCIP_OKAY;
634 }
635 
636 static
637 SCIP_RETCODE testSdPcKillsEdge2(
638  SCIP* scip /**< SCIP data structure */
639 )
640 {
641  GRAPH* graph;
642  int nelims;
643  const int nnodes = 4;
644  const int nedges = 4;
645 
646  assert(scip);
647 
648  SCIP_CALL( graph_init(scip, &graph, nnodes, 2 * nedges, 1) );
649 
650  for( int i = 0; i < nnodes; i++ )
651  graph_knot_add(graph, -1);
652 
653  graph->source = 3;
654 
655  graph_edge_add(scip, graph, 0, 1, 1.0, 1.0);
656  graph_edge_add(scip, graph, 0, 3, 2.0, 2.0); /* edge to be deleted */
657  graph_edge_add(scip, graph, 1, 2, 1.0, 1.0);
658  graph_edge_add(scip, graph, 2, 3, 1.0, 1.0);
659 
660  SCIP_CALL( graph_pc_initPrizes(scip, graph, nnodes) );
661 
662  for( int i = 0; i < nnodes; i++ )
663  graph->prize[i] = 0.0;
664 
665  graph->prize[3] = 1.0;
666  graph->prize[2] = 1.0;
667 
668  graph_knot_chg(graph, 3, 0);
669  graph_knot_chg(graph, 2, 0);
670 
671  nelims = 0;
672 
673  SCIP_CALL( checkSdWalk(scip, FALSE, &graph, &nelims) );
674 
675  STPTEST_ASSERT(nelims == 1);
676 
677  assert(graph == NULL);
678 
679  return SCIP_OKAY;
680 }
681 
682 
683 static
684 SCIP_RETCODE testSdPcKillsTwoEdges(
685  SCIP* scip /**< SCIP data structure */
686 )
687 {
688  GRAPH* graph;
689  int nelims;
690  const int nnodes = 5;
691  const int nedges = 6;
692 
693  assert(scip);
694 
695  SCIP_CALL( graph_init(scip, &graph, nnodes, 2 * nedges, 1) );
696 
697  for( int i = 0; i < nnodes; i++ )
698  graph_knot_add(graph, -1);
699 
700  graph->source = 3;
701 
702  /* square */
703  graph_edge_add(scip, graph, 0, 1, 1.0, 1.0);
704  graph_edge_add(scip, graph, 0, 3, 3.0, 3.0); /* edge to be deleted */
705  graph_edge_add(scip, graph, 1, 2, 1.1, 1.1);
706  graph_edge_add(scip, graph, 2, 3, 1.0, 1.0);
707 
708  /* lower hat */
709  graph_edge_add(scip, graph, 0, 4, 0.5, 0.5);
710  graph_edge_add(scip, graph, 1, 4, 0.5, 0.5);
711 
712  SCIP_CALL( graph_pc_initPrizes(scip, graph, nnodes) );
713 
714  for( int i = 0; i < nnodes; i++ )
715  graph->prize[i] = 0.0;
716 
717  graph->prize[3] = 1.0;
718  graph->prize[2] = 1.0;
719  graph->prize[1] = 0.1;
720 
721 
722  graph_knot_chg(graph, 3, 0);
723  graph_knot_chg(graph, 2, 0);
724  graph_knot_chg(graph, 1, 0);
725 
726  nelims = 0;
727 
728  SCIP_CALL( checkSdWalk(scip, FALSE, &graph, &nelims) );
729 
730  STPTEST_ASSERT(nelims == 2);
731 
732  assert(graph == NULL);
733 
734  return SCIP_OKAY;
735 }
736 
737 
738 /** tests that SD star PC test kills an edge */
739 static
740 SCIP_RETCODE testSdStarPcKillsEdge(
741  SCIP* scip /**< SCIP data structure */
742 )
743 {
744  DIJK* dijkdata;
745  GRAPH* graph;
746  int* star_base;
747  const int nnodes_org = 4;
748  const int nedges_org = 8;
749  int nnodes = -1;
750  int nedges = -1;
751  int nelims = 0;
752 
753  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
754 
755  for( int i = 0; i < nnodes_org - 1; i++ )
756  graph_knot_add(graph, STP_TERM_NONE);
757 
758  graph_knot_add(graph, STP_TERM); // 3
759  graph->source = 3;
760 
761  graph_edge_addBi(scip, graph, 0, 1, 2.0); // 0,1
762  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2,3
763  graph_edge_addBi(scip, graph, 1, 3, 1.0);
764  graph_edge_addBi(scip, graph, 2, 3, 1.0);
765 
766  graph_pc_initPrizes(scip, graph, nnodes_org);
767  graph->prize[0] = 0.0;
768  graph->prize[1] = 0.0;
769  graph->prize[2] = 0.0;
770  graph->prize[3] = 1.1; /* the pseudo root */
771 
772  SCIP_CALL( stptest_graphSetUpPcOrg(scip, graph, &nnodes, &nedges) );
773  SCIP_CALL( graph_dijkLimited_init(scip, graph, &dijkdata) );
774  SCIP_CALL( SCIPallocMemoryArray(scip, &star_base, nnodes) );
775 
776  /* actual test: edge 0 should have been deleted */
777  SCIP_CALL( reduce_sdStarPc2(scip, nedges, TRUE, graph, dijkdata->node_distance, star_base, dijkdata->visitlist, dijkdata->node_visited, dijkdata->dheap, &nelims) );
778 
779  STPTEST_ASSERT(nelims == 1);
780  STPTEST_ASSERT(graph->oeat[0] == EAT_FREE);
781  for( int e = 2; e < nedges; e++ )
782  STPTEST_ASSERT(graph->oeat[e] != EAT_FREE);
783 
784  SCIPfreeMemoryArray(scip, &star_base);
785  graph_dijkLimited_free(scip, &dijkdata);
786  stptest_graphTearDown(scip, graph);
787 
788  return SCIP_OKAY;
789 }
790 
791 
792 /** tests PCMW special distance methods */
793 SCIP_RETCODE stptest_pcreduce(
794  SCIP* scip /**< SCIP data structure */
795 )
796 {
797 
798  SCIP_CALL( testRmwNpv3DeletesNode(scip) );
799 
800  SCIP_CALL( testRmwChain2DeletesNode(scip) );
801  SCIP_CALL( testRmwTerminalDeg1Contraction2(scip) );
802  SCIP_CALL( testRmwAnsDeletesTwoNodes(scip) );
803  SCIP_CALL( testRmwAnsDeletesOneEdge(scip) );
804  SCIP_CALL( testRmwAnsDeletesOneNode(scip) );
805  SCIP_CALL( testRmwTerminalDeg1Contraction3(scip) );
806  SCIP_CALL( testRmwTerminalDeg1Contraction1(scip) );
807  SCIP_CALL( testRmwTerminalContraction(scip) );
808 
809 
810  SCIP_CALL( testSdStarPcKillsEdge(scip) );
811  SCIP_CALL( testSdPcKillsEdge1(scip) );
812  SCIP_CALL( testSdPcKillsEdge2(scip) );
813  SCIP_CALL( testSdPcKillsTwoEdges(scip) );
814 
815  printf("PC/MW reduction test: all ok \n");
816 
817  return SCIP_OKAY;
818 }
reduce_ans
SCIP_RETCODE reduce_ans(SCIP *, GRAPH *, int *)
Definition: reduce_alt.c:1470
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
dijkstra_data::visitlist
int * visitlist
Definition: graphdefs.h:314
testRmwTerminalDeg1Contraction2
static SCIP_RETCODE testRmwTerminalDeg1Contraction2(SCIP *scip)
Definition: stptest_pcreduce.c:512
STPTEST_ASSERT
#define STPTEST_ASSERT(cond)
Definition: stptest.h:63
GRAPH::source
int source
Definition: graphdefs.h:195
reduce_sdWalkTriangle
SCIP_RETCODE reduce_sdWalkTriangle(SCIP *, int, SCIP_Bool, GRAPH *, int *, SCIP_Real *, int *, STP_Bool *, DHEAP *, int *)
Definition: reduce_sd.c:3006
SCIPfreeMemoryArray
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
graph_edge_addBi
void graph_edge_addBi(SCIP *, GRAPH *, int, int, double)
graph_getIsTermArray
void graph_getIsTermArray(const GRAPH *, SCIP_Bool *)
Definition: graph_base.c:540
SCIPallocMemoryArray
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
graph_mark
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
dijkstra_heap
Definition: graphdefs.h:301
graph_free
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
graph_pc_2org
void graph_pc_2org(SCIP *, GRAPH *)
Definition: graph_pcbase.c:1976
graph_path_init
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
EAT_FREE
#define EAT_FREE
Definition: graphdefs.h:57
FALSE
#define FALSE
Definition: def.h:87
TRUE
#define TRUE
Definition: def.h:86
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
graph.h
includes various files containing graph methods used for Steiner tree problems
shortest_path
Definition: graphdefs.h:284
stptest_graphSetUpRmwOrg
SCIP_RETCODE stptest_graphSetUpRmwOrg(SCIP *, GRAPH *, int *, int *)
Definition: stptest_graph.c:335
stptest_graphSetUpPcOrg
SCIP_RETCODE stptest_graphSetUpPcOrg(SCIP *, GRAPH *, int *, int *)
Definition: stptest_graph.c:301
FARAWAY
#define FARAWAY
Definition: graphdefs.h:89
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
reduce_npv
SCIP_RETCODE reduce_npv(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2067
dijkstra_data::node_distance
SCIP_Real * node_distance
Definition: graphdefs.h:316
STP_TERM_NONE
#define STP_TERM_NONE
Definition: graphdefs.h:62
graph_pc_initPrizes
SCIP_RETCODE graph_pc_initPrizes(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:741
GRAPH::oeat
int *RESTRICT oeat
Definition: graphdefs.h:231
testRmwTerminalDeg1Contraction3
static SCIP_RETCODE testRmwTerminalDeg1Contraction3(SCIP *scip)
Definition: stptest_pcreduce.c:554
testRmwTerminalDeg1Contraction1
static SCIP_RETCODE testRmwTerminalDeg1Contraction1(SCIP *scip)
Definition: stptest_pcreduce.c:472
testRmwAnsDeletesTwoNodes
static SCIP_RETCODE testRmwAnsDeletesTwoNodes(SCIP *scip)
Definition: stptest_pcreduce.c:373
testRmwAnsDeletesOneNode
static SCIP_RETCODE testRmwAnsDeletesOneNode(SCIP *scip)
Definition: stptest_pcreduce.c:263
reduce_chain2
SCIP_RETCODE reduce_chain2(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2445
dijkstra_data::dheap
DHEAP * dheap
Definition: graphdefs.h:315
graph_transPc
SCIP_RETCODE graph_transPc(SCIP *, GRAPH *)
Definition: graph_trans.c:154
GRAPH::prize
SCIP_Real * prize
Definition: graphdefs.h:210
graph_initHistory
SCIP_RETCODE graph_initHistory(SCIP *, GRAPH *)
Definition: graph_base.c:695
graph_edge_add
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
GRAPH::grad
int *RESTRICT grad
Definition: graphdefs.h:201
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
NULL
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_OKAY
Definition: type_retcode.h:33
EQ
#define EQ(a, b)
Definition: portab.h:79
testRmwChain2DeletesNode
static SCIP_RETCODE testRmwChain2DeletesNode(SCIP *scip)
Definition: stptest_pcreduce.c:127
GRAPH::knots
int knots
Definition: graphdefs.h:190
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:384
stptest_pcreduce
SCIP_RETCODE stptest_pcreduce(SCIP *scip)
Definition: stptest_pcreduce.c:793
heur_local.h
Improvement heuristic for Steiner problems.
STP_Bool
unsigned char STP_Bool
Definition: portab.h:34
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
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
graph_heap_free
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
graph_dijkLimited_free
void graph_dijkLimited_free(SCIP *, DIJK **)
Definition: graph_util.c:2143
SCIP_Bool
#define SCIP_Bool
Definition: def.h:84
testSdStarPcKillsEdge
static SCIP_RETCODE testSdStarPcKillsEdge(SCIP *scip)
Definition: stptest_pcreduce.c:740
checkSdWalk
static SCIP_RETCODE checkSdWalk(SCIP *scip, SCIP_Bool extended, GRAPH **g, int *nelims)
Definition: stptest_pcreduce.c:40
testSdPcKillsEdge1
static SCIP_RETCODE testSdPcKillsEdge1(SCIP *scip)
Definition: stptest_pcreduce.c:595
STP_TERM
#define STP_TERM
Definition: graphdefs.h:61
graph_path_exit
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
portab.h
Portable definitions.
testRmwNpv3DeletesNode
static SCIP_RETCODE testRmwNpv3DeletesNode(SCIP *scip)
Definition: stptest_pcreduce.c:193
stptest.h
includes various testing methods for Steiner tree problems
graph_heap_create
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
reduce_simple_mw
SCIP_RETCODE reduce_simple_mw(SCIP *, GRAPH *, int *, SCIP_Real *, int *)
Definition: reduce_pcsimple.c:1107
testSdPcKillsTwoEdges
static SCIP_RETCODE testSdPcKillsTwoEdges(SCIP *scip)
Definition: stptest_pcreduce.c:684
SCIP_Real
#define SCIP_Real
Definition: def.h:177
dijkstra_data
Definition: graphdefs.h:311
testSdPcKillsEdge2
static SCIP_RETCODE testSdPcKillsEdge2(SCIP *scip)
Definition: stptest_pcreduce.c:637
reduce_sdStarPc2
SCIP_RETCODE reduce_sdStarPc2(SCIP *, int, SCIP_Bool, GRAPH *, SCIP_Real *, int *, int *, STP_Bool *, DHEAP *, int *)
Definition: reduce_sd.c:3389
heur_tm.h
shortest paths based primal heuristics for Steiner problems
testRmwAnsDeletesOneEdge
static SCIP_RETCODE testRmwAnsDeletesOneEdge(SCIP *scip)
Definition: stptest_pcreduce.c:316
reduce_sdWalkExt
SCIP_RETCODE reduce_sdWalkExt(SCIP *, int, SCIP_Bool, GRAPH *, SCIP_Real *, int *, int *, int *, STP_Bool *, int *)
Definition: reduce_sd.c:3822
GRAPH::edges
int edges
Definition: graphdefs.h:219
dijkstra_data::node_visited
STP_Bool * node_visited
Definition: graphdefs.h:317
nnodes
#define nnodes
Definition: gastrans.c:65
graph_init
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
testRmwTerminalContraction
static SCIP_RETCODE testRmwTerminalContraction(SCIP *scip)
Definition: stptest_pcreduce.c:427
reduce.h
includes various reduction methods for Steiner tree problems