1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file probdata_coloring.c
17 * @brief problem data for vertex coloring algorithm
18 * @author Gerald Gamrath
19 *
20 * This file implements the problem data for the coloring algorithm.
21 *
22 * The problem data contains the original graph, preprocessing information, the preprocessed graph,
23 * the array with the node-constraints, and an array with all stable sets and corresponding
24 * variables.
25 *
26 * The preprocessing deletes nodes that have a lower degree than the size of a maximum clique.
27 * Additionally, it also deletes nodes that have a dominated neighborhood. For further information,
28 * look at the documentation for the method preprocessGraph().
29 *
30 * The deleted nodes and the relation between the nodes of the original graph and the nodes of the
31 * preprocessed graph are stored in order to convert a solution of the preprocessed problem to a
32 * solution for the original graph and vice versa.
33 *
34 * Each variable has a pointer of type SCIP_VARDATA* that is used in this case to store an integer
35 * representing the number of the stable set. With the aid of this, the corresponding stable set can
36 * be found in the array returned by COLORprobGetStableSets(). This array contains all stable sets
37 * and is also used to check whether a stable set found by the pricer is really new. This can be
38 * done by calling COLORprobStableSetIsNew(). All sets are sorted decreasingly with respect to the
39 * indices of the nodes. New candidates should also be sorted that way.
40 */
41
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 #include "probdata_coloring.h"
44
45 #define EVENTHDLR_NAME "probdatavardeleted"
46 #define EVENTHDLR_DESC "event handler for variable deleted event"
47
48 struct SCIP_ProbData
49 {
50 TCLIQUE_GRAPH* graph; /* the preprocessed graph */
51 SCIP_CONS** constraints; /* array of added constraints */
52 int constraintssize; /* allocated size of constraints array */
53
54 /* stable set / variable - information*/
55 int** stablesets; /* array of stable sets */
56 int* stablesetlengths; /* length of the array in stablesets */
57 int maxstablesets; /* length of array stablesets */
58 int nstablesets; /* number of stable sets saved in array stablesets */
59 SCIP_VAR** stablesetvars; /* variables belonging to stable sets */
60
61 /* preprocessing information */
62 TCLIQUE_GRAPH* oldgraph; /* the original graph */
63 int* deletednodes; /* array of nodes which were deleted during preprocessing */
64 int* new2oldnode; /* new2oldnode[i] = j iff node i in the (preprocessed) graph corresponds to node j in the old graph*/
65 };
66
67
68 /*
69 * Local methods
70 */
71
72 /**
73 * Preprocessing of the graph, using 2 methods in order to find redundant nodes
74 * that can be deleted and easily colored later.
75 *
76 * Foundation of these methods is the computation of a maximum clique C with M nodes.
77 * After this computation, the following two steps are repeated until no node was deleted
78 * in the last iteration:
79 *
80 * 1: Low-Degree:
81 * Iterativly delete all nodes v in the graph G with degree d(v) < M ( don't delete nodes of C )
82 *
83 * 2: Dominated Neighbourhood:
84 * If the neighbourhood of one node v is part of the neighbourhood of another node w, v can
85 * be deleted, since it can later get the same color as w.
86 */
87 static
preprocessGraph(SCIP * scip)88 SCIP_RETCODE preprocessGraph(
89 SCIP* scip /**< SCIP data structure */
90 )
91 {
92 SCIP_PROBDATA* probdata; /* the problemdata */
93 SCIP_Bool changed; /* was the graph changed in the last round of preprocessing? */
94 SCIP_Bool dominates; /* is the neighbourhood of one node dominated by the neigbourhood of another one?*/
95 int* maxcliquenodes; /* pointer to store nodes of the maximum weight clique */
96 int nmaxcliquenodes; /* number of nodes in the maximum weight clique */
97 TCLIQUE_WEIGHT maxcliqueweight; /* weight of the maximum weight clique */
98 TCLIQUE_STATUS status; /* status of clique-computation */
99 TCLIQUE_GRAPH* currgraph; /* the current, not preprocessed graph in each step */
100 int currnnodes; /* the current number of nodes in each step */
101 int actnewnode; /* the number of nodes yet marked for beeing in the graph in the next round */
102 int* newnodes; /* the nodes that will be in the graph in the next round */
103 int* degrees; /* the degrees of the nodes */
104 int myround; /* the number of the current round */
105 int ndeletednodes; /* the total number of deleted nodes */
106 int nnodesdeleteddegreethisround; /* the number of nodes deleted due to low degree in the current round */
107 int nnodesdeletedneighbourthisround; /* the number of nodes deleted due to neighborhood in the current round */
108 int* firstedge; /* pointer for the edges in the graph */
109 int* lastedge; /* pointer for the edges in the graph */
110 int i;
111 int j;
112 char opt;
113
114 assert(scip != NULL);
115 probdata = SCIPgetProbData(scip);
116 assert(probdata != NULL);
117
118 printf("\npreprocessing...\n");
119
120 /* copy the old graph */
121 if( !tcliqueCreate(&currgraph) )
122 {
123 SCIPerrorMessage("could not flush the clique graph\n");
124 return SCIP_ERROR;
125 }
126
127 assert(currgraph != NULL);
128
129 if( !tcliqueAddNode(currgraph, tcliqueGetNNodes(probdata->oldgraph)-1, 0) )
130 {
131 SCIPerrorMessage("could not add a node to the clique graph\n");
132 return SCIP_ERROR;
133 }
134
135 for ( i = 0; i < tcliqueGetNNodes(probdata->oldgraph); i++ )
136 {
137 /* get adjacent nodes for node i */
138 firstedge = tcliqueGetFirstAdjedge(probdata->oldgraph, i);
139 lastedge = tcliqueGetLastAdjedge(probdata->oldgraph, i);
140 while ( firstedge <= lastedge )
141 {
142 if ( *firstedge > i )
143 {
144 if( !tcliqueAddEdge(currgraph, i, *firstedge) )
145 {
146 SCIPerrorMessage("could not add an edge to the clique graph\n");
147 return SCIP_ERROR;
148 }
149 }
150 firstedge++;
151 }
152 }
153
154 if( !tcliqueFlush(currgraph) )
155 {
156 SCIPerrorMessage("could not flush the clique graph\n");
157 return SCIP_ERROR;
158 }
159
160 currnnodes = tcliqueGetNNodes(probdata->oldgraph);
161
162 /* get memory for array of deletednodes and new2oldnodes */
163 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->deletednodes), currnnodes) );
164 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->new2oldnode), currnnodes) );
165
166 SCIP_CALL( SCIPallocBufferArray(scip, &newnodes, COLORprobGetOriginalNNodes(scip)) );
167 SCIP_CALL( SCIPallocBufferArray(scip, &maxcliquenodes, COLORprobGetOriginalNNodes(scip)) );
168
169 for ( i = 0; i < currnnodes; i++ )
170 {
171 /* set weights of the nodes to 1 */
172 tcliqueChangeWeight(currgraph, i, 1);
173 /* every node in the graph represents the same node in the original graph */
174 probdata->new2oldnode[i] = i;
175 }
176
177 /* compute maximum clique */
178 tcliqueMaxClique(NULL, NULL, NULL, NULL, currgraph, NULL, NULL, maxcliquenodes,
179 &nmaxcliquenodes, &maxcliqueweight, 0, 0, 50000, 0, INT_MAX, -1, NULL, &status);
180 opt = ( status == TCLIQUE_OPTIMAL ? ' ' : '*' );
181 printf("size of the maximum clique: %d%c \n", nmaxcliquenodes, opt);
182
183 ndeletednodes = 0;
184 nnodesdeleteddegreethisround = 1;
185 nnodesdeletedneighbourthisround = 1;
186 myround = 0;
187
188 /* main loop */
189 while ( (nnodesdeleteddegreethisround > 0) || (nnodesdeletedneighbourthisround > 0) )
190 {
191 myround++;
192 nnodesdeleteddegreethisround = 0;
193 nnodesdeletedneighbourthisround = 0;
194 changed = TRUE;
195
196 /* node degree deletion loop */
197 while ( changed == TRUE )
198 {
199 changed = FALSE;
200 actnewnode = 0;
201 degrees = tcliqueGetDegrees(currgraph);
202 for (i = 0; i < currnnodes; i++)
203 {
204 /* degree is low, node can be deleted */
205 if ( (degrees[i] < nmaxcliquenodes )
206 && (!COLORprobIsNodeInArray(probdata->new2oldnode[i], maxcliquenodes, nmaxcliquenodes)) )
207 {
208 probdata->deletednodes[ndeletednodes] = probdata->new2oldnode[i];
209 changed = TRUE;
210 nnodesdeleteddegreethisround++;
211 ndeletednodes++;
212 }
213 /* node will be in the new graph, because degree is not low enough for deletion or it is in the maxClique */
214 else
215 {
216 newnodes[actnewnode] = probdata->new2oldnode[i];
217 actnewnode++;
218 }
219 }
220
221 /* at least one node was deleted, create new graph (tclique doesn't support deletion of nodes) */
222 if ( changed )
223 {
224 assert(actnewnode+ndeletednodes == COLORprobGetOriginalNNodes(scip));
225 /* create new current graph */
226 tcliqueFree(&currgraph);
227
228 if( !tcliqueCreate(&currgraph) )
229 {
230 SCIPerrorMessage("could not create the clique graph\n");
231 return SCIP_ERROR;
232 }
233
234 assert(currgraph != NULL);
235
236 if( !tcliqueAddNode(currgraph, actnewnode-1, 0) )
237 {
238 SCIPerrorMessage("could not add a node to the clique graph\n");
239 return SCIP_ERROR;
240 }
241
242 for ( i = 0; i < actnewnode; i++ )
243 {
244 /* get adjacent nodes for node newnodes[i] */
245 firstedge = tcliqueGetFirstAdjedge(probdata->oldgraph, newnodes[i]);
246 lastedge = tcliqueGetLastAdjedge(probdata->oldgraph, newnodes[i]);
247 while ( firstedge <= lastedge )
248 {
249 /* try to find a node in newnodes which corresponds
250 to the node in the old graph, that is the end-node of the edge */
251 for ( j = i+1; j < actnewnode; j++ )
252 {
253 if ( *firstedge == newnodes[j] )
254 {
255 if( !tcliqueAddEdge(currgraph, i, j) )
256 {
257 SCIPerrorMessage("could not add an edge to the clique graph\n");
258 return SCIP_ERROR;
259 }
260
261 break;
262 }
263 }
264 firstedge++;
265 }
266 }
267
268 if( !tcliqueFlush(currgraph) )
269 {
270 SCIPerrorMessage("could not flush the clique graph\n");
271 return SCIP_ERROR;
272 }
273
274 /* update currnnodes */
275 currnnodes = tcliqueGetNNodes(currgraph);
276 /* update new2oldnodes */
277 for ( i = 0; i < actnewnode; i++ )
278 {
279 probdata->new2oldnode[i] = newnodes[i];
280 }
281 /* set the corresponding old node to -1 for all nodes not in the current graph (only for bug-finding) */
282 for ( i = actnewnode; i < COLORprobGetOriginalNNodes(scip); i++ )
283 {
284 probdata->new2oldnode[i] = -1;
285 }
286 }
287 } /* end node degree deletion loop */
288
289 /* set changed to TRUE for getting into the while-loop */
290 changed = TRUE;
291 /* loop for finding dominated neighborhoods */
292 while ( changed == TRUE )
293 {
294 changed = FALSE;
295 actnewnode = 0;
296 /* i is the node which is checked for being dominated */
297 for ( i = 0; i < currnnodes; i++ )
298 {
299 assert(!COLORprobIsNodeInArray(probdata->new2oldnode[i], probdata->deletednodes, ndeletednodes));
300
301 /* i must be not in the clique and not yet deleted */
302 if ( (!COLORprobIsNodeInArray(probdata->new2oldnode[i], maxcliquenodes, nmaxcliquenodes)) )
303 {
304 /* j is the node for which is checked whether it dominates i */
305 for ( j = 0; j < currnnodes; j++ )
306 {
307 /* i must be distinct from j, there must be no edge between i and j,
308 j may not have been deleted due to degree in the last round */
309 if ( (j != i) && !tcliqueIsEdge(currgraph, i, j)
310 && (!COLORprobIsNodeInArray(probdata->new2oldnode[j], probdata->deletednodes, ndeletednodes)) )
311 /** @todo only check nodes deleted in the last round */
312 {
313 /* check whether nodes adjacent to i are also adjacent to j <-> j dominates i */
314 dominates = TRUE;
315 /* get adjacent nodes for node i in currgraph */
316 firstedge = tcliqueGetFirstAdjedge(currgraph, i);
317 lastedge = tcliqueGetLastAdjedge(currgraph, i);
318 while ( firstedge <= lastedge )
319 {
320 /* check whether (j,firstedge) is in currgraph, if not, j doesn't dominate i */
321 if ( !tcliqueIsEdge(currgraph, j, *firstedge) )
322 {
323 dominates = FALSE;
324 break;
325 }
326 firstedge++;
327 }
328 if ( dominates )
329 {
330 probdata->deletednodes[ndeletednodes] = probdata->new2oldnode[i];
331 changed = TRUE;
332 ndeletednodes++;
333 nnodesdeletedneighbourthisround++;
334 break; /* for j, because we already now that i is dominated and deleted i */
335 }
336 }
337 } /* end for j */
338
339 /* if i is dominated by no other node and thus not deleted,
340 put it into newnodes, so that it is in the next graph */
341 if ( ndeletednodes == 0 || probdata->deletednodes[ndeletednodes-1] != probdata->new2oldnode[i])
342 {
343 newnodes[actnewnode] = probdata->new2oldnode[i];
344 actnewnode++;
345 }
346 }
347 /* if i is in the maxClique and was thus not deleted,
348 put it into newnodes, so that it is in the next graph */
349 else
350 {
351 newnodes[actnewnode] = probdata->new2oldnode[i];
352 actnewnode++;
353 }
354 } /*end for i */
355
356 /* at least one node was deleted, create new graph (tclique doesn't support deletion of nodes) */
357 if ( changed )
358 {
359 assert(actnewnode+ndeletednodes == COLORprobGetOriginalNNodes(scip));
360 /* create new current graph */
361 tcliqueFree(&currgraph);
362
363 if( !tcliqueCreate(&currgraph) )
364 {
365 SCIPerrorMessage("could not create the clique graph\n");
366 return SCIP_ERROR;
367 }
368
369 assert(currgraph != NULL);
370
371 if( !tcliqueAddNode(currgraph, actnewnode-1, 0) )
372 {
373 SCIPerrorMessage("could not add a node to the clique graph\n");
374 return SCIP_ERROR;
375 }
376
377 for ( i = 0; i < actnewnode; i++ )
378 {
379 /* get adjacent nodes for node newnodes[i] */
380 firstedge = tcliqueGetFirstAdjedge(probdata->oldgraph, newnodes[i]);
381 lastedge = tcliqueGetLastAdjedge(probdata->oldgraph, newnodes[i]);
382 while ( firstedge <= lastedge )
383 {
384 /* try to find a node in newnodes which corresponds
385 to the node in the old graph, that is the end-node of the edge */
386 for ( j = i+1; j < actnewnode; j++ )
387 {
388 if ( *firstedge == newnodes[j] )
389 {
390
391 if( !tcliqueAddEdge(currgraph, i, j) )
392 {
393 SCIPerrorMessage("could not add an edge to the clique graph\n");
394 return SCIP_ERROR;
395 }
396 break;
397 }
398 }
399 firstedge++;
400 }
401 }
402
403 if( !tcliqueFlush(currgraph) )
404 {
405 SCIPerrorMessage("could not flush the clique graph\n");
406 return SCIP_ERROR;
407 }
408
409 /* update currnnodes */
410 currnnodes = tcliqueGetNNodes(currgraph);
411
412 /* update new2oldnodes */
413 for ( i = 0; i < actnewnode; i++ )
414 {
415 probdata->new2oldnode[i] = newnodes[i];
416 }
417
418 /* set the corresponding old node to -1 for all nodes not in the current graph (only for bug-finding) */
419 for ( i = actnewnode; i < COLORprobGetOriginalNNodes(scip); i++ )
420 {
421 probdata->new2oldnode[i] = -1;
422 }
423 }
424 } /* end of loop for finding dominated neighbourhoods */
425
426 printf("Round %d of preprocessing:\n", myround);
427 printf(" deleted low degree vertices: %d\n", nnodesdeleteddegreethisround);
428 printf(" deleted almost cliques: %d\n", nnodesdeletedneighbourthisround);
429
430 }
431
432 for ( i = ndeletednodes; i < COLORprobGetOriginalNNodes(scip); i++ )
433 {
434 probdata->deletednodes[i] = -1;
435 }
436
437 printf("preprocessing overall deleted vertices: %d\n\n", ndeletednodes);
438 /* copy preprocessed graph into problem data */
439 probdata->graph = currgraph;
440
441 SCIPfreeBufferArray(scip, &newnodes);
442 SCIPfreeBufferArray(scip, &maxcliquenodes);
443
444 return SCIP_OKAY;
445 }
446
447
448
449
450 /*
451 * Callback methods of probdata
452 */
453
454 /** transforms the problem */
455 static
SCIP_DECL_PROBTRANS(probtransColoring)456 SCIP_DECL_PROBTRANS(probtransColoring)
457 {
458 int i;
459 int j;
460 int* firstedge;
461 int* lastedge;
462
463 assert(scip != NULL);
464 assert(sourcedata != NULL);
465 assert(targetdata != NULL);
466
467 /* allocate memory */
468 SCIP_CALL( SCIPallocBlockMemory(scip, targetdata) );
469
470 if( !tcliqueCreate(&((*targetdata)->graph)) ) /* create the transformed graph */
471 {
472 SCIPerrorMessage("could not create the clique graph\n");
473 return SCIP_ERROR;
474 }
475
476 (*targetdata)->maxstablesets = sourcedata->maxstablesets; /* copy length of array sets */
477 (*targetdata)->nstablesets = sourcedata->nstablesets; /* copy number of sets saved in array sets */
478 (*targetdata)->oldgraph = sourcedata->oldgraph; /* copy link to original graph */
479
480 /* allocate memory for sets and lenghts of the sets */
481 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesets), sourcedata->maxstablesets) );
482 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesetlengths), sourcedata->maxstablesets) );
483 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesetvars), sourcedata->maxstablesets) );
484 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->deletednodes), tcliqueGetNNodes(sourcedata->oldgraph)) );
485 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->new2oldnode), tcliqueGetNNodes(sourcedata->oldgraph)) );
486
487 for ( i = 0; i < tcliqueGetNNodes(sourcedata->oldgraph); i++ )
488 {
489 (*targetdata)->deletednodes[i] = sourcedata->deletednodes[i];
490 (*targetdata)->new2oldnode[i] = sourcedata->new2oldnode[i];
491 }
492
493 /* copy stablesetlengths and stablesets */
494 for ( i = 0; i < sourcedata->nstablesets; i++ )
495 {
496 assert(sourcedata->stablesetvars[i] != NULL);
497 (*targetdata)->stablesetlengths[i] = sourcedata->stablesetlengths[i];
498 SCIP_CALL( SCIPtransformVar(scip, sourcedata->stablesetvars[i], &((*targetdata)->stablesetvars[i])) );
499 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesets[i]), sourcedata->stablesetlengths[i]) ); /*lint !e866*/
500 for ( j = 0; j <sourcedata->stablesetlengths[i]; j++ )
501 {
502 (*targetdata)->stablesets[i][j] = sourcedata->stablesets[i][j];
503 }
504 }
505
506 /* create array for constraints */
507 (*targetdata)->constraintssize = tcliqueGetNNodes(sourcedata->graph);
508 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*targetdata)->constraints, (*targetdata)->constraintssize) );
509 /* tranform constraints */
510 SCIP_CALL( SCIPtransformConss(scip, tcliqueGetNNodes(sourcedata->graph), sourcedata->constraints,
511 (*targetdata)->constraints) );
512 /* copy the graph */
513 if( !tcliqueAddNode((*targetdata)->graph, tcliqueGetNNodes(sourcedata->graph)-1, 0) )
514 {
515 SCIPerrorMessage("could not add a node to the clique graph\n");
516 return SCIP_ERROR;
517 }
518
519 for ( i = 0; i < tcliqueGetNNodes(sourcedata->graph); i++ )
520 {
521 /* get adjacent nodes for node i */
522 firstedge = tcliqueGetFirstAdjedge(sourcedata->graph, i);
523 lastedge = tcliqueGetLastAdjedge(sourcedata->graph, i);
524 while ( firstedge <= lastedge )
525 {
526 if ( *firstedge > i )
527 {
528 if( !tcliqueAddEdge((*targetdata)->graph, i, *firstedge) )
529 {
530 SCIPerrorMessage("could not add an edge to the clique graph\n");
531 return SCIP_ERROR;
532 }
533 }
534 firstedge++;
535 }
536 }
537
538 if( !tcliqueFlush((*targetdata)->graph) )
539 {
540 SCIPerrorMessage("could not flush the clique graph\n");
541 return SCIP_ERROR;
542 }
543
544 return SCIP_OKAY;
545 }
546
547
548 /** deletes the transformed problem */
549 static
SCIP_DECL_PROBDELTRANS(probdeltransColoring)550 SCIP_DECL_PROBDELTRANS(probdeltransColoring)
551 {
552 int i;
553
554 assert(scip != NULL);
555 assert(probdata != NULL);
556
557 /* release constraints and free array for constraints */
558 for ( i = 0; i < tcliqueGetNNodes((*probdata)->graph); i++)
559 {
560 SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->constraints[i])) );
561 }
562 SCIPfreeBlockMemoryArray(scip, &((*probdata)->constraints), (*probdata)->constraintssize);
563
564 /* free the arrays for the stable sets and release the related variables */
565 for ( i = (*probdata)->nstablesets-1; i >= 0; i-- )
566 {
567 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets[i]), (*probdata)->stablesetlengths[i]); /*lint !e866*/
568 SCIP_CALL( SCIPreleaseVar(scip, &((*probdata)->stablesetvars[i])) );
569 }
570
571 SCIPfreeBlockMemoryArray(scip, &((*probdata)->new2oldnode), tcliqueGetNNodes((*probdata)->oldgraph));
572 SCIPfreeBlockMemoryArray(scip, &((*probdata)->deletednodes), tcliqueGetNNodes((*probdata)->oldgraph));
573 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesetvars), (*probdata)->maxstablesets);
574 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesetlengths), (*probdata)->maxstablesets);
575 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets), (*probdata)->maxstablesets);
576
577 tcliqueFree(&(*probdata)->graph);
578 SCIPfreeBlockMemory(scip, probdata);
579 return SCIP_OKAY;
580 }
581
582 static
SCIP_DECL_PROBDELORIG(probdelorigColoring)583 SCIP_DECL_PROBDELORIG(probdelorigColoring)
584 {
585 int i;
586
587 assert(probdata != NULL);
588 assert(*probdata != NULL);
589
590 SCIPfreeBlockMemoryArray(scip, &((*probdata)->new2oldnode), tcliqueGetNNodes((*probdata)->oldgraph));
591 SCIPfreeBlockMemoryArray(scip, &((*probdata)->deletednodes), tcliqueGetNNodes((*probdata)->oldgraph));
592
593 for ( i = (*probdata)->nstablesets-1; i >= 0; i-- )
594 {
595 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets[i]), (*probdata)->stablesetlengths[i]); /*lint !e866*/
596 SCIP_CALL( SCIPreleaseVar(scip, &((*probdata)->stablesetvars[i])) );
597 }
598 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesetvars), (*probdata)->maxstablesets);
599 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesetlengths), (*probdata)->maxstablesets);
600 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets), (*probdata)->maxstablesets);
601
602 /* release Constraints */
603 for ( i = 0; i < tcliqueGetNNodes((*probdata)->graph); i++ )
604 {
605 SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->constraints[i])) );
606 }
607 SCIPfreeBlockMemoryArray(scip, &((*probdata)->constraints), (*probdata)->constraintssize);
608
609 /* free memory used for graph */
610 tcliqueFree(&((*probdata)->graph));
611 tcliqueFree(&((*probdata)->oldgraph));
612
613 /* free probdata */
614 SCIPfreeBlockMemory(scip, probdata);
615
616 return SCIP_OKAY;
617 }
618
619
620 /*
621 * Callback methods of event handler
622 */
623
624 /** execution method of event handler */
625 static
SCIP_DECL_EVENTEXEC(eventExecProbdatavardeleted)626 SCIP_DECL_EVENTEXEC(eventExecProbdatavardeleted)
627 {
628 SCIP_VAR* var;
629 SCIP_PROBDATA* probdata;
630 int idx;
631
632 assert(SCIPeventGetType(event) == SCIP_EVENTTYPE_VARDELETED);
633 var = SCIPeventGetVar(event);
634 probdata = (SCIP_PROBDATA*) eventdata;
635
636 assert(probdata != NULL);
637 assert(var != NULL);
638
639 /* get index of variable in stablesets array */
640 idx = (int)(size_t) SCIPvarGetData(var);
641
642 SCIPdebugMessage("remove variable %s [%d] from list of stable sets\n", SCIPvarGetName(var), idx);
643
644 assert(probdata->stablesetvars[idx] == var);
645
646 /* remove variable from stablesets array and release it */
647 SCIPfreeBlockMemoryArray(scip, &(probdata->stablesets[idx]), probdata->stablesetlengths[idx]); /*lint !e866*/
648 SCIP_CALL( SCIPreleaseVar(scip, &(probdata->stablesetvars[idx])) );
649
650 /* move all subsequent variables to the front */
651 for( ; idx < probdata->nstablesets - 1; idx++)
652 {
653 probdata->stablesets[idx] = probdata->stablesets[idx + 1];
654 probdata->stablesetlengths[idx] = probdata->stablesetlengths[idx + 1];
655 probdata->stablesetvars[idx] = probdata->stablesetvars[idx + 1];
656 SCIPvarSetData(probdata->stablesetvars[idx], (SCIP_VARDATA*) (size_t) idx); /*lint !e571*/
657 }
658
659 probdata->nstablesets--;
660
661 return SCIP_OKAY;
662 }/*lint !e715*/
663
664
665
666 /*
667 * probdata specific interface methods
668 */
669
670 /** sets up the problem data */
SCIPcreateProbColoring(SCIP * scip,const char * name,int nnodes,int nedges,int ** edges)671 SCIP_RETCODE SCIPcreateProbColoring(
672 SCIP* scip, /**< SCIP data structure */
673 const char* name, /**< problem name */
674 int nnodes, /**< number of nodes */
675 int nedges, /**< number of edges */
676 int** edges /**< array with start- and endpoints of the edges */
677 )
678 {
679 int i;
680 SCIP_PROBDATA* probdata = NULL;
681
682 assert(nnodes > 0); /* at least one node */
683 assert(nedges >= 0); /* no negative number of edges */
684
685 printf("Creating problem: %s \n", name);
686
687 /* allocate memory */
688 SCIP_CALL( SCIPallocBlockMemory(scip, &probdata) );
689
690 /* create graph */
691 if( !tcliqueCreate(&((probdata)->oldgraph)) )
692 {
693 SCIPerrorMessage("could not create the clique graph\n");
694 return SCIP_ERROR;
695 }
696
697 /* add all nodes from 0 to nnodes-1 */
698 if( !tcliqueAddNode((probdata)->oldgraph, nnodes-1, 0) )
699 {
700 SCIPerrorMessage("could not add a node to the clique graph\n");
701 return SCIP_ERROR;
702 }
703
704
705 /* add all edges, first into cache, then flush to add all of them to the graph */
706 for ( i = 0; i < nedges; i++ )
707 {
708 assert((edges[i][0] > 0) && (edges[i][0] <= nnodes));
709 assert((edges[i][1] > 0) && (edges[i][1] <= nnodes));
710
711 if( !tcliqueAddEdge((probdata)->oldgraph, edges[i][0]-1, edges[i][1]-1) )
712 {
713 SCIPerrorMessage("could not add an edge to the clique graph\n");
714 return SCIP_ERROR;
715 }
716 }
717
718 if( !tcliqueFlush((probdata)->oldgraph) )
719 {
720 SCIPerrorMessage("could not flush the clique graph\n");
721 return SCIP_ERROR;
722 }
723
724 /* create constraints */
725 probdata->constraintssize = nnodes;
726 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->constraints), probdata->constraintssize) );
727
728 /* at the beginning memory for 2 sets */
729 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesets), 2) );
730 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesetlengths), 2) );
731 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesetvars), 2) );
732
733 probdata->maxstablesets = 2;
734 probdata->nstablesets = 0;
735
736 /* include variable deleted event handler into SCIP */
737 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, NULL, EVENTHDLR_NAME, EVENTHDLR_DESC,
738 eventExecProbdatavardeleted, NULL) );
739
740 /* create problem in SCIP */
741 SCIP_CALL( SCIPcreateProb(scip, name, probdelorigColoring, probtransColoring, probdeltransColoring,
742 NULL, NULL, NULL, probdata) );
743
744 SCIP_CALL( preprocessGraph(scip) );
745
746 return SCIP_OKAY;
747 }
748
749
750 /* ----------------------------------- external methods -------------------------- */
751
752 /** returns the number of stable sets / variables */
COLORprobGetNStableSets(SCIP * scip)753 int COLORprobGetNStableSets(
754 SCIP* scip /**< SCIP data structure */
755 )
756 {
757 SCIP_PROBDATA* probdata;
758
759 assert(scip != NULL);
760 probdata = SCIPgetProbData(scip);
761 assert(probdata != NULL);
762
763 return probdata->nstablesets;
764 }
765
766
767 /** prints all stable sets to standard output */
COLORprobPrintStableSets(SCIP * scip)768 void COLORprobPrintStableSets(
769 SCIP* scip /**< SCIP data structure */
770 )
771 {
772 SCIP_PROBDATA* probdata;
773 int i;
774 int j;
775
776 assert(scip != NULL);
777 probdata = SCIPgetProbData(scip);
778 assert(probdata != NULL);
779
780 for ( i = 0; i < probdata->nstablesets; i++ )
781 {
782 printf( "Set %d: ", i);
783 for ( j = 0; j < probdata->stablesetlengths[i]; j++ )
784 {
785 printf("%d, ", probdata->stablesets[i][j]+1);
786 }
787 printf("ub = %f", SCIPvarGetUbLocal(probdata->stablesetvars[i]));
788 printf(", inLP = %u", SCIPvarIsInLP(probdata->stablesetvars[i]));
789 printf("\n");
790 }
791 }
792
793
794 /** prints the requested stable set to standard output */
COLORprobPrintStableSet(SCIP * scip,int setnumber)795 void COLORprobPrintStableSet(
796 SCIP* scip, /**< SCIP data structure */
797 int setnumber /**< the number of the requested set */
798 )
799 {
800 SCIP_PROBDATA* probdata;
801 int i;
802 int j;
803
804 assert(scip != NULL);
805 probdata = SCIPgetProbData(scip);
806 assert(probdata != NULL);
807
808 i = setnumber;
809 printf( "Set %d: ", i);
810 for ( j = 0; j < probdata->stablesetlengths[i]; j++ )
811 {
812 printf("%d, ", probdata->stablesets[i][j]+1);
813 }
814 if ( probdata->stablesetvars[i] != NULL )
815 printf("ub = %f", SCIPvarGetUbLocal(probdata->stablesetvars[i]));
816 printf("\n");
817 }
818
819
820
821
822 /** adds a variable that belongs to a given stable set */
COLORprobAddVarForStableSet(SCIP * scip,int setindex,SCIP_VAR * var)823 SCIP_RETCODE COLORprobAddVarForStableSet(
824 SCIP* scip, /**< SCIP data structure */
825 int setindex, /**< index of the stable set */
826 SCIP_VAR* var /**< pointer to the variable */
827 )
828 {
829 SCIP_PROBDATA* probdata;
830
831 assert(scip != NULL);
832 probdata = SCIPgetProbData(scip);
833 assert(probdata != NULL);
834 assert((setindex >= 0) && (setindex < probdata->nstablesets));
835
836 /* catch variable deleted event on the variable to update the stablesetvars array in the problem data */
837 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_VARDELETED, SCIPfindEventhdlr(scip, EVENTHDLR_NAME),
838 (SCIP_EVENTDATA*) probdata, NULL) );
839
840 probdata->stablesetvars[setindex] = var;
841
842 return SCIP_OKAY;
843 }
844
845
846 /** gets the variable belonging to a given stable set */
COLORprobGetVarForStableSet(SCIP * scip,int setindex)847 SCIP_VAR* COLORprobGetVarForStableSet(
848 SCIP* scip, /**< SCIP data structure */
849 int setindex /**< index of the stable set */
850 )
851 {
852 SCIP_PROBDATA* probdata;
853
854 assert(scip != NULL);
855 probdata = SCIPgetProbData(scip);
856 assert(probdata != NULL);
857 assert ( (setindex >= 0) && (setindex < probdata->nstablesets));
858
859 return probdata->stablesetvars[setindex];
860 }
861
862
863 /** checks whether a node is in a given stable set, returns true iff it is */
COLORprobIsNodeInStableSet(SCIP * scip,int setindex,int node)864 SCIP_Bool COLORprobIsNodeInStableSet(
865 SCIP* scip, /**< SCIP data structure */
866 int setindex, /**< index of the stable set */
867 int node /**< number of the node */
868 )
869 {
870 SCIP_PROBDATA* probdata;
871 int l;
872 int u;
873 int m;
874
875 assert(scip != NULL);
876 probdata = SCIPgetProbData(scip);
877 assert(probdata != NULL);
878
879 l = 0;
880 u = probdata->stablesetlengths[setindex]-1;
881 while ( l <= u )
882 {
883 m = (l+u)/2;
884 if ( probdata->stablesets[setindex][m] == node )
885 {
886 return TRUE;
887 }
888 if ( probdata->stablesets[setindex][m] > node )
889 {
890 l = m+1;
891 }
892 if ( probdata->stablesets[setindex][m] < node )
893 {
894 u = m-1;
895 }
896 }
897 return FALSE;
898 }
899
900
901 /** checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way */
COLORprobStableSetsAreEqual(SCIP * scip,int * set1,int nset1nodes,int * set2,int nset2nodes)902 SCIP_Bool COLORprobStableSetsAreEqual(
903 SCIP* scip, /**< SCIP data structure */
904 int* set1, /**< array of nodes in the first set */
905 int nset1nodes, /**< number of nodes in the first set */
906 int* set2, /**< array of nodes in the second set */
907 int nset2nodes /**< number of nodes in the second set */
908 )
909 {
910
911 int i;
912
913 assert(scip != NULL);
914 assert(set1 != NULL && set2 != NULL);
915 assert(nset1nodes > 0 && nset2nodes > 0);
916
917 if ( nset1nodes != nset2nodes )
918 {
919 return FALSE;
920 }
921 for ( i = 0; i < nset1nodes; i++ )
922 {
923 if ( set1[i] != set2[i] )
924 {
925 return FALSE;
926 }
927 }
928 return TRUE;
929
930 }
931
932
933 /** checks whether the given stable set is new returns TRUE if the stable is new, FALSE if it is equal to an already
934 * existing stable set
935 */
COLORprobStableSetIsNew(SCIP * scip,int * stablesetnodes,int nstablesetnodes)936 SCIP_Bool COLORprobStableSetIsNew(
937 SCIP* scip, /**< SCIP data structure */
938 int* stablesetnodes, /**< array of nodes in the stable set */
939 int nstablesetnodes /**< number of nodes in the stable set */
940 )
941 {
942 SCIP_PROBDATA* probdata;
943 int i;
944
945 assert(stablesetnodes != NULL);
946 assert(scip != NULL);
947 probdata = SCIPgetProbData(scip);
948 assert(probdata != NULL);
949
950 /* sort the set */
951 SCIPsortDownInt(stablesetnodes, nstablesetnodes);
952
953 for ( i = 0; i < COLORprobGetNStableSets(scip); i++ )
954 {
955 if ( COLORprobStableSetsAreEqual(scip, stablesetnodes, nstablesetnodes,
956 probdata->stablesets[i],
957 probdata->stablesetlengths[i]) )
958 {
959 return FALSE;
960 }
961 }
962
963 return TRUE;
964 }
965
966 /** adds a new stable set, the set must be sorted in descending order;
967 * @note you need to check whether it is new before adding it
968 */
COLORprobAddNewStableSet(SCIP * scip,int * stablesetnodes,int nstablesetnodes,int * setindex)969 SCIP_RETCODE COLORprobAddNewStableSet(
970 SCIP* scip, /**< SCIP data structure */
971 int* stablesetnodes, /**< array of nodes in the stable set */
972 int nstablesetnodes, /**< number of nodes in the stable set */
973 int* setindex /**< return value: index of the stable set */
974 )
975 {
976 SCIP_PROBDATA* probdata;
977 int newsize;
978 int i;
979
980 assert(stablesetnodes != NULL);
981 assert(scip != NULL);
982 probdata = SCIPgetProbData(scip);
983 assert(probdata != NULL);
984
985 /* the set should be sorted in descending */
986 #ifndef NDEBUG
987 for ( i = 0; i < nstablesetnodes-2; i++ )
988 {
989 assert(stablesetnodes[i]>stablesetnodes[i+1]);
990 }
991 #endif
992
993 /* ensure that array is big enough */
994 if ( (probdata->nstablesets + 1) > probdata->maxstablesets)
995 {
996 newsize = SCIPcalcMemGrowSize(scip, probdata->maxstablesets + 1);
997 assert(newsize > probdata->nstablesets + 1);
998 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesets), probdata->maxstablesets, newsize) );
999 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesetlengths), probdata->maxstablesets, newsize) );
1000 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesetvars), probdata->maxstablesets, newsize) );
1001 SCIPdebugMessage("Set-array resized: %d --> %d\n", probdata->maxstablesets, newsize);
1002 probdata->maxstablesets = newsize;
1003 }
1004
1005 /* allocate memory for the new stable set */
1006 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesets[probdata->nstablesets]), nstablesetnodes) ); /*lint !e866*/
1007 probdata->stablesetlengths[probdata->nstablesets] = nstablesetnodes;
1008 probdata->stablesetvars[probdata->nstablesets] = NULL;
1009 for ( i = 0; i < nstablesetnodes; i++ )
1010 {
1011 assert(stablesetnodes[i] >= 0);
1012 probdata->stablesets[probdata->nstablesets][i] = stablesetnodes[i];
1013 }
1014 *setindex = probdata->nstablesets;
1015
1016 probdata->nstablesets++;
1017
1018 return SCIP_OKAY;
1019 }
1020
1021
1022 /** returns the stable set with the given index */
COLORprobGetStableSet(SCIP * scip,int setindex,int ** stableset,int * nelements)1023 void COLORprobGetStableSet(
1024 SCIP* scip, /**< SCIP data structure */
1025 int setindex, /**< index of the stable set */
1026 int** stableset, /**< return value: pointer to the stable set */
1027 int* nelements /**< return value: number of elements in the stable set */
1028 )
1029 {
1030 SCIP_PROBDATA* probdata;
1031
1032 assert(scip != NULL);
1033 probdata = SCIPgetProbData(scip);
1034 assert(probdata != NULL);
1035
1036 *stableset = probdata->stablesets[setindex];
1037 *nelements = probdata->stablesetlengths[setindex];
1038 }
1039
1040
1041 /** returns all stable sets */
COLORprobGetStableSets(SCIP * scip,int *** stablesets,int ** nelements,int * nstablesets)1042 void COLORprobGetStableSets(
1043 SCIP* scip, /**< SCIP data structure */
1044 int*** stablesets, /**< return value: pointer to the stable sets */
1045 int** nelements, /**< return value: number of elements in the stable sets */
1046 int* nstablesets /**< return value: number of sets */
1047 )
1048 {
1049 SCIP_PROBDATA* probdata;
1050
1051 assert(scip != NULL);
1052 probdata = SCIPgetProbData(scip);
1053 assert(probdata != NULL);
1054
1055 *stablesets = probdata->stablesets;
1056 *nelements = probdata->stablesetlengths;
1057 *nstablesets = probdata->nstablesets;
1058 }
1059
1060
1061 /** returns the number of nodes in the (preprocessed) graph */
COLORprobGetNNodes(SCIP * scip)1062 int COLORprobGetNNodes(
1063 SCIP* scip /**< SCIP data structure */
1064 )
1065 {
1066 SCIP_PROBDATA* probdata;
1067
1068 assert(scip != NULL);
1069 probdata = SCIPgetProbData(scip);
1070 assert(probdata != NULL);
1071
1072 return tcliqueGetNNodes(probdata->graph);
1073 }
1074
1075
1076 /** returns the number of nodes in the original graph */
COLORprobGetOriginalNNodes(SCIP * scip)1077 int COLORprobGetOriginalNNodes(
1078 SCIP* scip /**< SCIP data structure */
1079 )
1080 {
1081 SCIP_PROBDATA* probdata;
1082
1083 assert(scip != NULL);
1084 probdata = SCIPgetProbData(scip);
1085 assert(probdata != NULL);
1086
1087 return tcliqueGetNNodes(probdata->oldgraph);
1088 }
1089
1090
1091 /** returns the (preprocessed) graph */
COLORprobGetGraph(SCIP * scip)1092 TCLIQUE_GRAPH* COLORprobGetGraph(
1093 SCIP* scip /**< SCIP data structure */
1094 )
1095 {
1096
1097 SCIP_PROBDATA* probdata;
1098
1099 assert(scip != NULL);
1100 probdata = SCIPgetProbData(scip);
1101 assert(probdata != NULL);
1102
1103 return probdata->graph;
1104 }
1105
1106
1107 /** returns the original graph */
COLORprobGetOriginalGraph(SCIP * scip)1108 TCLIQUE_GRAPH* COLORprobGetOriginalGraph(
1109 SCIP* scip /**< SCIP data structure */
1110 )
1111 {
1112 SCIP_PROBDATA* probdata;
1113
1114 assert(scip != NULL);
1115 probdata = SCIPgetProbData(scip);
1116 assert(probdata != NULL);
1117
1118 return probdata->oldgraph;
1119 }
1120
1121
1122 /** returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(), filled with -1 at the end */
COLORprobGetDeletedNodes(SCIP * scip)1123 int* COLORprobGetDeletedNodes(
1124 SCIP* scip /**< SCIP data structure */
1125 )
1126 {
1127 SCIP_PROBDATA* probdata;
1128
1129 assert(scip != NULL);
1130 probdata = SCIPgetProbData(scip);
1131 assert(probdata != NULL);
1132
1133 return probdata->deletednodes;
1134 }
1135
1136
1137 /** returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved */
COLORprobGetOriginalNodesForNewNodes(SCIP * scip)1138 int* COLORprobGetOriginalNodesForNewNodes(
1139 SCIP* scip /**< SCIP data structure */
1140 )
1141 {
1142 SCIP_PROBDATA* probdata;
1143
1144 assert(scip != NULL);
1145 probdata = SCIPgetProbData(scip);
1146 assert(probdata != NULL);
1147
1148 return probdata->new2oldnode;
1149 }
1150
1151
1152
1153 /** returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted */
COLORprobGetNewNodeForOriginalNode(SCIP * scip,int node)1154 int COLORprobGetNewNodeForOriginalNode(
1155 SCIP* scip, /**< SCIP data structure */
1156 int node /**< a node in the original graph */
1157 )
1158 {
1159 SCIP_PROBDATA* probdata;
1160 int i;
1161
1162 assert(scip != NULL);
1163 probdata = SCIPgetProbData(scip);
1164
1165 assert(probdata != NULL);
1166 assert(node >= 0 && node < COLORprobGetOriginalNNodes(scip));
1167
1168 for ( i = 0; i < COLORprobGetOriginalNNodes(scip); i++ )
1169 {
1170 if ( probdata->new2oldnode[i] == node )
1171 return i;
1172 if ( probdata->new2oldnode[i] == -1 )
1173 return -1;
1174 }
1175 return -1;
1176
1177 }
1178
1179
1180 /** returns all node-constraints */
COLORprobGetConstraints(SCIP * scip)1181 SCIP_CONS** COLORprobGetConstraints(
1182 SCIP* scip /**< SCIP data structure */
1183 )
1184 {
1185 SCIP_PROBDATA* probdata;
1186
1187 assert(scip != NULL);
1188 probdata = SCIPgetProbData(scip);
1189 assert(probdata != NULL);
1190
1191 return probdata->constraints;
1192 }
1193
1194
1195 /** returns the node-constraint belonging to a given node */
COLORprobGetConstraint(SCIP * scip,int node)1196 SCIP_CONS* COLORprobGetConstraint(
1197 SCIP* scip, /**< SCIP data structure */
1198 int node /**< number of the node, for which this constraint assures coloring */
1199 )
1200 {
1201 SCIP_PROBDATA* probdata;
1202
1203 assert(scip != NULL);
1204 probdata = SCIPgetProbData(scip);
1205 assert(probdata != NULL);
1206 assert(node >= 0 && node < tcliqueGetNNodes(probdata->graph));
1207
1208 return probdata->constraints[node];
1209 }
1210
1211
1212 /** computes the complementary graph for a given graph and stores it in the given pointer */
COLORprobGetComplementaryGraph(SCIP * scip,TCLIQUE_GRAPH * graph,TCLIQUE_GRAPH * cgraph)1213 SCIP_RETCODE COLORprobGetComplementaryGraph(
1214 SCIP* scip, /**< SCIP data structure */
1215 TCLIQUE_GRAPH* graph, /**< the given graph */
1216 TCLIQUE_GRAPH* cgraph /**< the complementary graph is saved in here */
1217 )
1218 {
1219 int nnodes;
1220 int i;
1221 int j;
1222 int* firstedge;
1223 int* lastedge;
1224
1225 assert(scip != NULL);
1226 assert(graph != NULL);
1227 assert(cgraph != NULL);
1228
1229 /* get number of nodes */
1230 nnodes = tcliqueGetNNodes(graph);
1231 assert(nnodes > 0);
1232
1233 /* add all nodes from 0 to nnodes-1 */
1234 if( !tcliqueAddNode(cgraph, nnodes-1, 0) )
1235 {
1236 SCIPerrorMessage("could not add a node to the clique graph\n");
1237 return SCIP_ERROR;
1238 }
1239
1240 /* add edge between i and j iff there is no edge between i and j in old graph */
1241 /* assumption: all edges are undirected, (i,j) exists --> (j,i) exists */
1242 for ( i = 0; i < nnodes; i++ )
1243 {
1244 firstedge = tcliqueGetFirstAdjedge(graph, i);
1245 lastedge = tcliqueGetLastAdjedge(graph, i);
1246 for ( j = 0; j < *firstedge && j < i; j++ )
1247 {
1248 if( !tcliqueAddEdge(cgraph, i, j) )
1249 {
1250 SCIPerrorMessage("could not add an edge to the clique graph\n");
1251 return SCIP_ERROR;
1252 }
1253 }
1254 while ( firstedge < lastedge )
1255 {
1256 for ( j = *firstedge+1; j < *(firstedge+1) && j < i; j++ )
1257 {
1258 if( !tcliqueAddEdge(cgraph, i, j) )
1259 {
1260 SCIPerrorMessage("could not add an edge to the clique graph\n");
1261 return SCIP_ERROR;
1262 }
1263 }
1264 firstedge++;
1265 }
1266 for ( j = (*lastedge)+1; j < COLORprobGetNNodes(scip) && j < i; j++ )
1267 {
1268 if( !tcliqueAddEdge(cgraph, i, j) )
1269 {
1270 SCIPerrorMessage("could not add an edge to the clique graph\n");
1271 return SCIP_ERROR;
1272 }
1273 }
1274 }
1275
1276 if( !tcliqueFlush(cgraph) )
1277 {
1278 SCIPerrorMessage("could not flush the clique graph\n");
1279 return SCIP_ERROR;
1280 }
1281
1282 for ( i = 0; i < COLORprobGetNNodes(scip); i++ )
1283 {
1284 for ( j = i+1; j < COLORprobGetNNodes(scip); j++ )
1285 {
1286 assert((tcliqueIsEdge(graph, i, j) && !tcliqueIsEdge(cgraph, i, j))
1287 || (!tcliqueIsEdge(graph, i, j) && tcliqueIsEdge(cgraph, i, j)));
1288 }
1289 }
1290
1291 return SCIP_OKAY;
1292 }
1293
1294
1295 /** creates all node-constraints and saves them in an array */
COLORprobSetUpArrayOfCons(SCIP * scip)1296 SCIP_RETCODE COLORprobSetUpArrayOfCons(
1297 SCIP* scip /**< SCIP data structure */
1298 )
1299 {
1300 SCIP_CONS** constraints;
1301 int nnodes;
1302 int i;
1303
1304 assert(scip != NULL);
1305
1306 constraints = COLORprobGetConstraints(scip);
1307 assert(constraints != NULL);
1308 nnodes = COLORprobGetNNodes(scip);
1309 for ( i = 0; i < nnodes; i++ )
1310 {
1311 char consname[SCIP_MAXSTRLEN];
1312
1313 /* create the constraint */
1314 sprintf(consname, "Node-Constraint%d", i+1);
1315
1316 SCIP_CALL( SCIPcreateConsSetcover(scip, &constraints[i], consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE) );
1317 SCIP_CALL( SCIPaddCons(scip, constraints[i]) );
1318 }
1319
1320 return SCIP_OKAY;
1321 }
1322
1323
1324 /** checks whether the given node is in the given array */
COLORprobIsNodeInArray(int node,int * arraynodes,int narraynodes)1325 SCIP_Bool COLORprobIsNodeInArray(
1326 int node, /**< the number of the node */
1327 int* arraynodes, /**< the nodes of the maximum stableset */
1328 int narraynodes /**< number of nodes in the maximum stableset */
1329 )
1330 {
1331 int i;
1332
1333 assert(arraynodes != NULL);
1334
1335 for ( i = 0; i < narraynodes; i++ )
1336 {
1337 if ( arraynodes[i] == node )
1338 {
1339 return TRUE;
1340 }
1341 }
1342 return FALSE;
1343 }
1344
1345 /** checks whether the given two given arrays are equal */
COLORprobEqualSortedArrays(int * array1nodes,int narray1nodes,int * array2nodes,int narray2nodes)1346 SCIP_Bool COLORprobEqualSortedArrays(
1347 int* array1nodes, /**< the nodes of the first set */
1348 int narray1nodes, /**< number of nodes in the first set */
1349 int* array2nodes, /**< the nodes of the second set */
1350 int narray2nodes /**< number of nodes in the second set */
1351 )
1352 {
1353 int i;
1354
1355 assert(array1nodes != NULL);
1356 assert(narray1nodes > 0);
1357 assert(array2nodes != NULL);
1358 assert(narray2nodes > 0);
1359
1360 if ( narray1nodes != narray2nodes )
1361 {
1362 return FALSE;
1363 }
1364 for ( i = 0; i < narray1nodes; i++ )
1365 {
1366 if ( array1nodes[i] != array2nodes[i] )
1367 {
1368 return FALSE;
1369 }
1370 }
1371 return TRUE;
1372 }
1373