SCIP

Solving Constraint Integer Programs

stptest_graph.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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file stptest_graph.c
17  * @brief tests for Steiner tree problem methods
18  * @author Daniel Rehfeldt
19  *
20  * This file implements tests for Steiner problems.
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 #include "scip/scip.h"
29 #include "stptest.h"
30 #include "graph.h"
31 #include "portab.h"
32
33
34 /** are the CSRs equal? */
35 static
37  const CSR* csr1, /**< csr */
38  const CSR* csr2 /**< csr */
39  )
40 {
41  if( csr1->nedges_max != csr2->nedges_max )
42  {
43  SCIPdebugMessage("wrong edge count \n");
44  return FALSE;
45  }
46
47  if( csr1->nnodes != csr2->nnodes )
48  {
49  SCIPdebugMessage("wrong node count \n");
50  return FALSE;
51  }
52
53  for( int i = 0; i <= csr1->nnodes; ++i )
54  {
55  if( csr1->start[i] != csr2->start[i] )
56  {
57  SCIPdebugMessage("wrong start array \n");
58  return FALSE;
59  }
60  }
61
62  for( int i = 0; i < csr1->nedges_max; ++i )
63  {
64  if( !EQ(csr1->cost[i], csr2->cost[i]) )
65  {
66  SCIPdebugMessage("wrong cost array \n");
67  return FALSE;
68  }
69
71  {
73  return FALSE;
74  }
75  }
76
77  return TRUE;
78 }
79
80
81 /** simple pseudo random fill of CSRs */
82 static
84  int seed, /**< seed */
85  CSR* csrd /**< csr */
86  )
87 {
88  int* start_csr;
90  SCIP_Real* cost_csr;
91  const int nnodes = csrd->nnodes;
92  const int nedges = csrd->nedges_max;
93
94  assert(nnodes >= 1 && nedges >= 1);
95  assert(seed >= 0);
96
97  start_csr = csrd->start;
99  cost_csr = csrd->cost;
100
101  start_csr[0] = 0;
102
103  for( int i = 1; i <= nnodes; i++ )
104  {
105  start_csr[i] = start_csr[i - 1] + (i + seed) % 8;
106  }
107
108  for( int i = 0; i < nedges; i++ )
109  {
110  head_csr[i] = (i + seed) % 7;
111  cost_csr[i] = (SCIP_Real)((i + seed) % 12) + 0.5 ;
112  }
113 }
114
115
116 /** first test: Simple additions and deletions */
117 static
119  SCIP* scip /**< SCIP data structure */
120  )
121 {
122  const int nnodes1 = 5;
123  const int nedges1 = 12;
124  const int nnodes2 = 9;
125  const int nedges2 = 24;
126
127  CSRDEPO* depo;
128  CSR csr;
129
130  SCIP_CALL( graph_csrdepo_init(scip, 8, 1000, &depo) );
131
134  graph_csrdepo_getEmptyTop(depo, &csr);
135
136  if( csr.nedges_max != nedges1 || csr.nnodes != nnodes1 )
137  {
138  SCIPdebugMessage("wrong number of nodes/edges (%d, %d) stored! \n", csr.nnodes, csr.nedges_max);
139  return SCIP_ERROR;
140  }
141
142  csrdepoFillRandom(5522, &csr);
144
147  graph_csrdepo_getEmptyTop(depo, &csr);
148
149  if( csr.nedges_max != nedges2 || csr.nnodes != nnodes2 )
150  {
151  SCIPdebugMessage("wrong number of nodes/edges (%d, %d) stored! \n", csr.nnodes, csr.nedges_max);
152  return SCIP_ERROR;
153  }
154
155  /* remove both */
158
159  if( !graph_csrdepo_isEmpty(depo) )
160  {
161  SCIPdebugMessage("depo is not empty! \n");
162  return SCIP_ERROR;
163  }
164
165  graph_csrdepo_free(scip, &depo);
166
167  return SCIP_OKAY;
168 }
169
170
171 /** second test: Make sure that the CSRs are stored correctly */
172 static
174  SCIP* scip /**< SCIP data structure */
175  )
176 {
177  const int nnodes0 = 5;
178  const int nedges0 = 12;
179  const int nnodes1 = 10;
180  const int nedges1 = 24;
181  const int nnodes2 = 15;
182  const int nedges2 = 28;
183
184  CSRDEPO* depo;
185  CSR csr_in;
186  CSR csr_out;
187  CSR* csr0;
188  CSR* csr1;
189  CSR* csr2;
190
191  SCIP_CALL( graph_csrdepo_init(scip, 8, 1000, &depo) );
192
195  graph_csrdepo_getEmptyTop(depo, &csr_in);
196
197  SCIP_CALL( graph_csr_alloc(scip, nnodes0, nedges0, &csr0) );
198  csrdepoFillRandom(55, &csr_in);
199  csrdepoFillRandom(55, csr0);
200
202
205  graph_csrdepo_getEmptyTop(depo, &csr_in);
206  csrdepoFillRandom(200, &csr_in);
207
209
212  graph_csrdepo_getEmptyTop(depo, &csr_in);
213
214  SCIP_CALL( graph_csr_alloc(scip, nnodes1, nedges1, &csr1) );
215  csrdepoFillRandom(551, &csr_in);
216  csrdepoFillRandom(551, csr1);
217
219
222  graph_csrdepo_getEmptyTop(depo, &csr_in);
223
224  SCIP_CALL( graph_csr_alloc(scip, nnodes2, nedges2, &csr2) );
225  csrdepoFillRandom(44, &csr_in);
226  csrdepoFillRandom(44, csr2);
227
229
230  /* now check: */
231
232  graph_csrdepo_getCSR(depo, 0, &csr_out);
233
234  if( !csrdepoCSRsAreEqual(&csr_out, csr0) )
235  {
236  SCIPdebugMessage("CSRs 0 not equal! \n");
237  return SCIP_ERROR;
238  }
239
240  graph_csrdepo_getCSR(depo, 2, &csr_out);
241
242  if( !csrdepoCSRsAreEqual(&csr_out, csr2) )
243  {
244  SCIPdebugMessage("CSRs 2 not equal! \n");
245  return SCIP_ERROR;
246  }
247
249
250  graph_csrdepo_getCSR(depo, 1, &csr_out);
251
252  if( !csrdepoCSRsAreEqual(&csr_out, csr1) )
253  {
254  SCIPdebugMessage("CSRs 1 not equal! \n");
255  return SCIP_ERROR;
256  }
257
258  /* remove all */
261
262  assert(graph_csrdepo_isEmpty(depo));
263
264  /* clean-up*/
265  graph_csrdepo_free(scip, &depo);
266  graph_csr_free(scip, &csr2);
267  graph_csr_free(scip, &csr1);
268  graph_csr_free(scip, &csr0);
269
270  return SCIP_OKAY;
271 }
272
273 /** frees, etc. */
275  SCIP* scip, /**< SCIP data structure */
276  GRAPH* graph /**< the graph */
277 )
278 {
279  graph_path_exit(scip, graph);
280  graph_free(scip, &graph, TRUE);
281  assert(graph == NULL);
282 }
283
284
285 /** sets up graph */
287  SCIP* scip, /**< SCIP data structure */
288  GRAPH* graph /**< the graph */
289  )
290 {
291  SCIP_CALL( graph_initHistory(scip, graph) );
292  SCIP_CALL( graph_path_init(scip, graph) );
293
294  graph_mark(graph);
295
296  return SCIP_OKAY;
297 }
298
299
300 /** sets up graph for (undirected) PC */
302  SCIP* scip, /**< SCIP data structure */
303  GRAPH* graph, /**< the graph */
304  int* nnodes_new, /**< to store new number of nodes (if != NULL) */
305  int* nedges_new /**< to store new number of edge (if != NULL) */
306  )
307 {
308  SCIP_CALL( stptest_graphSetUpPcExtended(scip, graph, nnodes_new, nedges_new) );
309
310  graph_pc_2org(scip, graph);
311
312  return SCIP_OKAY;
313 }
314
315
316 /** sets up graph for rooted PC */
318  SCIP* scip, /**< SCIP data structure */
319  GRAPH* graph, /**< the graph */
320  int* nnodes_new, /**< to store new number of nodes (if != NULL) */
321  int* nedges_new /**< to store new number of edge (if != NULL) */
322  )
323 {
324  SCIP_CALL( stptest_graphSetUpRpcExtended(scip, graph, nnodes_new, nedges_new) );
325
326  graph_pc_2org(scip, graph);
327
328  assert(graph_pc_isRootedPcMw(graph));
329
330  return SCIP_OKAY;
331 }
332
333
334 /** sets up graph for RMW */
336  SCIP* scip, /**< SCIP data structure */
337  GRAPH* graph, /**< the graph */
338  int* nnodes_new, /**< to store new number of nodes (if != NULL) */
339  int* nedges_new /**< to store new number of edge (if != NULL) */
340  )
341 {
342  SCIP_CALL( stptest_graphSetUpRmwExtended(scip, graph, nnodes_new, nedges_new) );
343
344  graph_pc_2org(scip, graph);
345
346  return SCIP_OKAY;
347 }
348
349
350 /** sets up graph for RMW */
352  SCIP* scip, /**< SCIP data structure */
353  GRAPH* graph, /**< the graph */
354  int* nnodes_new, /**< to store new number of nodes (if != NULL) */
355  int* nedges_new /**< to store new number of edge (if != NULL) */
356  )
357 {
358  graph->stp_type = STP_RMWCSP;
359
360  SCIP_CALL( graph_transRmw(scip, graph) );
361
362  stptest_graphSetUp(scip, graph);
363
364  if( nnodes_new )
365  *nnodes_new = graph->knots;
366
367  if( nedges_new )
368  *nedges_new = graph->edges;
369
370  return SCIP_OKAY;
371 }
372
373
374 /** sets up graph for (undirected) PC */
376  SCIP* scip, /**< SCIP data structure */
377  GRAPH* graph, /**< the graph */
378  int* nnodes_new, /**< to store new number of nodes (if != NULL) */
379  int* nedges_new /**< to store new number of edge (if != NULL) */
380  )
381 {
382  graph->stp_type = STP_PCSPG;
383
384  SCIP_CALL( graph_transPc(scip, graph) );
385
386  stptest_graphSetUp(scip, graph);
387
388  if( nnodes_new )
389  *nnodes_new = graph->knots;
390
391  if( nedges_new )
392  *nedges_new = graph->edges;
393
394  return SCIP_OKAY;
395 }
396
397
398
399 /** sets up graph for RPC */
401  SCIP* scip, /**< SCIP data structure */
402  GRAPH* graph, /**< the graph */
403  int* nnodes_new, /**< to store new number of nodes (if != NULL) */
404  int* nedges_new /**< to store new number of edge (if != NULL) */
405  )
406 {
407  graph->stp_type = STP_RPCSPG;
408
409  SCIP_CALL( graph_transRpc(scip, graph) );
410
411  stptest_graphSetUp(scip, graph);
412
413  if( nnodes_new )
414  *nnodes_new = graph->knots;
415
416  if( nedges_new )
417  *nedges_new = graph->edges;
418
419  return SCIP_OKAY;
420 }
421
422 /** tests CSR depository */
424  SCIP* scip /**< SCIP data structure */
425 )
426 {
427  assert(scip);
428
429  SCIP_CALL( csrdepoTest1(scip) );
430  SCIP_CALL( csrdepoTest2(scip) );
431
432  printf("csrdepo test: all ok \n");
433
434  return SCIP_OKAY;
435 }
Definition: graphdefs.h:141
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
static void csrdepoFillRandom(int seed, CSR *csrd)
Definition: stptest_graph.c:83
SCIP_RETCODE stptest_graphSetUpPcOrg(SCIP *scip, GRAPH *graph, int *nnodes_new, int *nedges_new)
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
void stptest_graphTearDown(SCIP *scip, GRAPH *graph)
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
void graph_pc_2org(SCIP *, GRAPH *)
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
#define FALSE
Definition: def.h:87
SCIP_Real * cost
Definition: graphdefs.h:142
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
#define SCIPdebugMessage
Definition: pub_message.h:87
int * start
Definition: graphdefs.h:140
SCIP_RETCODE stptest_graphSetUpRpcExtended(SCIP *scip, GRAPH *graph, int *nnodes_new, int *nedges_new)
static SCIP_Bool csrdepoCSRsAreEqual(const CSR *csr1, const CSR *csr2)
Definition: stptest_graph.c:36
SCIP_Bool graph_csrdepo_isEmpty(const CSRDEPO *)
Definition: graph_util.c:851
static SCIP_RETCODE csrdepoTest1(SCIP *scip)
int stp_type
Definition: graphdefs.h:264
SCIP_RETCODE stptest_graphSetUpRmwOrg(SCIP *scip, GRAPH *graph, int *nnodes_new, int *nedges_new)
SCIP_RETCODE graph_transPc(SCIP *, GRAPH *)
Definition: graph_trans.c:154
SCIP_RETCODE stptest_graphSetUpRpcOrg(SCIP *scip, GRAPH *graph, int *nnodes_new, int *nedges_new)
SCIP_RETCODE stptest_graphSetUp(SCIP *scip, GRAPH *graph)
SCIP_RETCODE graph_initHistory(SCIP *, GRAPH *)
Definition: graph_base.c:695
int nedges_max
Definition: graphdefs.h:144
void graph_csrdepo_free(SCIP *, CSRDEPO **)
Definition: graph_util.c:637
void graph_csrdepo_getEmptyTop(const CSRDEPO *, CSR *)
Definition: graph_util.c:874
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_RMWCSP
Definition: graphdefs.h:54
SCIP_RETCODE stptest_csrdepo(SCIP *scip)
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE graph_csr_alloc(SCIP *, int, int, CSR **)
Definition: graph_util.c:1231
Definition: graph_util.c:800
#define STP_PCSPG
Definition: graphdefs.h:44
#define SCIP_Bool
Definition: def.h:84
void graph_csrdepo_removeTop(CSRDEPO *)
Definition: graph_util.c:753
SCIP_RETCODE graph_csrdepo_init(SCIP *, int, int, CSRDEPO **)
Definition: graph_util.c:590
SCIP_RETCODE stptest_graphSetUpPcExtended(SCIP *scip, GRAPH *graph, int *nnodes_new, int *nedges_new)
SCIP_RETCODE graph_transRpc(SCIP *, GRAPH *)
Definition: graph_trans.c:373
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
Portable definitions.
static SCIP_RETCODE csrdepoTest2(SCIP *scip)
void graph_csrdepo_emptyTopSetMarked(CSRDEPO *)
Definition: graph_util.c:890
includes various testing methods for Steiner tree problems
void graph_csr_free(SCIP *, CSR **)
Definition: graph_util.c:1554
#define SCIP_Real
Definition: def.h:177
int edges
Definition: graphdefs.h:219
#define nnodes
Definition: gastrans.c:65
SCIP_RETCODE stptest_graphSetUpRmwExtended(SCIP *scip, GRAPH *graph, int *nnodes_new, int *nedges_new)
SCIP_RETCODE graph_transRmw(SCIP *, GRAPH *)
Definition: graph_trans.c:687
#define STP_RPCSPG
Definition: graphdefs.h:45
SCIP callable library.
void graph_csrdepo_getCSR(const CSRDEPO *, int, CSR *)
Definition: graph_util.c:667