Scippy

SCIP

Solving Constraint Integer Programs

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