1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* TCLIQUE --- Algorithm for Maximum Cliques */
5 /* */
6 /* Copyright (C) 1996-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* TCLIQUE 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 TCLIQUE; see the file COPYING. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file tclique_branch.c
17 * @ingroup OTHER_CFILES
18 * @brief branch and bound part of algorithm for maximum cliques
19 * @author Tobias Achterberg
20 * @author Ralf Borndoerfer
21 * @author Zoltan Kormos
22 * @author Kati Wolter
23 */
24
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26
27 #include <stdio.h>
28 #include <assert.h>
29 #include <stdlib.h>
30 #include <limits.h>
31
32 #include "tclique/tclique.h"
33 #include "tclique/tclique_def.h"
34 #include "tclique/tclique_coloring.h"
35 #include "blockmemshell/memory.h"
36
37
38
39 #define CHUNK_SIZE (64)
40 #define CLIQUEHASH_INITSIZE (1024)
41
42
43
44
45 /***************************
46 * clique hash table methods
47 ***************************/
48
49 typedef struct clique CLIQUE; /**< single element of the clique hash table */
50
51 /** single element of the clique hash table */
52 struct clique
53 {
54 int* nodes; /**< node number of the clique elements */
55 int nnodes; /**< length of the clique */
56 };
57
58 typedef struct cliquehash CLIQUEHASH; /**< hash table for storing cliques */
59
60 /** hash table for storing cliques */
61 struct cliquehash
62 {
63 CLIQUE** cliques; /**< elements of the table */
64 int cliquessize; /**< size of the table */
65 int ncliques; /**< number of cliques stored in the table */
66 };
67
68
69 /** creates a clique */
70 static
createClique(CLIQUE ** clique,int * nodes,int nnodes)71 void createClique(
72 CLIQUE** clique, /**< pointer to the clique */
73 int* nodes, /**< nodes of the clique */
74 int nnodes /**< number of nodes in the clique */
75 )
76 {
77 int i;
78
79 assert(clique != NULL);
80
81 ALLOC_ABORT( BMSallocMemory(clique) );
82 ALLOC_ABORT( BMSallocMemoryArray(&(*clique)->nodes, nnodes) );
83
84 /* sort the nodes into the clique's node array */
85 for( i = 0; i < nnodes; ++i )
86 {
87 int node;
88 int j;
89
90 node = nodes[i];
91 for( j = i; j > 0 && node < (*clique)->nodes[j-1]; --j )
92 (*clique)->nodes[j] = (*clique)->nodes[j-1];
93 (*clique)->nodes[j] = node;
94 }
95 (*clique)->nnodes = nnodes;
96 }
97
98 /** frees a clique */
99 static
freeClique(CLIQUE ** clique)100 void freeClique(
101 CLIQUE** clique /**< pointer to the clique */
102 )
103 {
104 assert(clique != NULL);
105 assert(*clique != NULL);
106
107 BMSfreeMemoryArray(&(*clique)->nodes);
108 BMSfreeMemory(clique);
109 }
110
111 /** checks, whether clique1 is a subset of clique2 and returns the following value:
112 * == 0 if clique1 == clique2, or clique1 is contained in clique2,
113 * < 0 if clique1 < clique2, and clique1 is not contained in clique2,
114 * > 0 if clique1 > clique2, and clique1 is not contained in clique2
115 */
116 static
compSubcliques(CLIQUE * clique1,CLIQUE * clique2)117 int compSubcliques(
118 CLIQUE* clique1, /**< first clique to compare */
119 CLIQUE* clique2 /**< second clique to compare */
120 )
121 {
122 int pos1;
123 int pos2;
124 TCLIQUE_Bool clique2smaller;
125
126 assert(clique1 != NULL);
127 assert(clique2 != NULL);
128
129 pos1 = 0;
130 pos2 = 0;
131 clique2smaller = FALSE;
132 while( pos1 < clique1->nnodes && pos2 < clique2->nnodes )
133 {
134 if( clique1->nodes[pos1] < clique2->nodes[pos2] )
135 {
136 /* clique1 has an element not contained in clique2: clique1 is lex-smaller, if clique2 was not
137 * detected earlier to be lex-smaller
138 */
139 return (clique2smaller ? +1 : -1);
140 }
141 else if( clique1->nodes[pos1] > clique2->nodes[pos2] )
142 {
143 /* clique2 has an element not contained in clique1: clique2 is lex-smaller, but probably clique1 is
144 * contained in clique2
145 */
146 pos2++;
147 clique2smaller = TRUE;
148 }
149 else
150 {
151 pos1++;
152 pos2++;
153 }
154 }
155
156 /* if clique1 has additional elements, it is not contained in clique2 */
157 if( pos1 < clique1->nnodes )
158 return (clique2smaller ? +1 : -1);
159
160 /* clique1 is contained in clique2 */
161 return 0;
162 }
163
164 #ifndef NDEBUG
165 /** performs an integrity check of the clique hash table */
166 static
checkCliquehash(CLIQUEHASH * cliquehash)167 void checkCliquehash(
168 CLIQUEHASH* cliquehash /**< clique hash table */
169 )
170 {
171 int i;
172
173 assert(cliquehash != NULL);
174
175 for( i = 0; i < cliquehash->ncliques-1; ++i )
176 assert(compSubcliques(cliquehash->cliques[i], cliquehash->cliques[i+1]) < 0);
177 }
178 #else
179 #define checkCliquehash(cliquehash) /**/
180 #endif
181
182 /** creates a table for storing cliques */
183 static
createCliquehash(CLIQUEHASH ** cliquehash,int tablesize)184 void createCliquehash(
185 CLIQUEHASH** cliquehash, /**< pointer to store the clique hash table */
186 int tablesize /**< initial size of the clique hash table */
187 )
188 {
189 assert(cliquehash != NULL);
190 assert(tablesize > 0);
191
192 ALLOC_ABORT( BMSallocMemory(cliquehash) );
193 ALLOC_ABORT( BMSallocMemoryArray(&(*cliquehash)->cliques, tablesize) );
194 (*cliquehash)->cliquessize = tablesize;
195 (*cliquehash)->ncliques = 0;
196 }
197
198 /** clears the clique hash table and frees all inserted cliques */
199 static
clearCliquehash(CLIQUEHASH * cliquehash)200 void clearCliquehash(
201 CLIQUEHASH* cliquehash /**< clique hash table */
202 )
203 {
204 int i;
205
206 assert(cliquehash != NULL);
207
208 /* free the cliques in the table */
209 for( i = 0; i < cliquehash->ncliques; ++i )
210 freeClique(&cliquehash->cliques[i]);
211
212 cliquehash->ncliques = 0;
213 }
214
215 /** frees the table for storing cliques and all inserted cliques */
216 static
freeCliquehash(CLIQUEHASH ** cliquehash)217 void freeCliquehash(
218 CLIQUEHASH** cliquehash /**< pointer to the clique hash table */
219 )
220 {
221 assert(cliquehash != NULL);
222 assert(*cliquehash != NULL);
223
224 /* free the cliques in the table */
225 clearCliquehash(*cliquehash);
226
227 /* free the table data structure */
228 BMSfreeMemoryArray(&(*cliquehash)->cliques);
229 BMSfreeMemory(cliquehash);
230 }
231
232 /** ensures, that the clique hash table is able to store at least the given number of cliques */
233 static
ensureCliquehashSize(CLIQUEHASH * cliquehash,int num)234 void ensureCliquehashSize(
235 CLIQUEHASH* cliquehash, /**< clique hash table */
236 int num /**< minimal number of cliques to store */
237 )
238 {
239 assert(cliquehash != NULL);
240
241 if( num > cliquehash->cliquessize )
242 {
243 int newsize;
244
245 newsize = 2*cliquehash->cliquessize;
246 if( num > newsize )
247 newsize = num;
248
249 ALLOC_ABORT( BMSreallocMemoryArray(&cliquehash->cliques, newsize) );
250 cliquehash->cliquessize = newsize;
251 }
252 assert(cliquehash->cliquessize >= num);
253 }
254
255 #ifdef TCLIQUE_DEBUG
256 /** displayes clique hash table */
257 static
printCliquehash(CLIQUEHASH * cliquehash)258 void printCliquehash(
259 CLIQUEHASH* cliquehash /**< clique hash table */
260 )
261 {
262 int i;
263
264 assert(cliquehash != NULL);
265
266 debugMessage("cliquehash (%d cliques):\n", cliquehash->ncliques);
267 for( i = 0; i < cliquehash->ncliques; ++i )
268 {
269 int j;
270
271 debugPrintf("%d:", i);
272 for( j = 0; j < cliquehash->cliques[i]->nnodes; ++j )
273 debugPrintf(" %d", cliquehash->cliques[i]->nodes[j]);
274 debugPrintf("\n");
275 }
276 }
277 #endif
278
279 /** searches the given clique in the clique hash table and returns whether it (or a stronger clique) exists */
280 static
inCliquehash(CLIQUEHASH * cliquehash,CLIQUE * clique,int * insertpos)281 TCLIQUE_Bool inCliquehash(
282 CLIQUEHASH* cliquehash, /**< clique hash table */
283 CLIQUE* clique, /**< clique to search in the table */
284 int* insertpos /**< position where the clique should be inserted in the table */
285 )
286 {
287 int left;
288 int right;
289 int middle;
290 int cmp;
291
292 assert(cliquehash != NULL);
293 assert(cliquehash->cliquessize > 0);
294 assert(clique != NULL);
295 assert(insertpos != NULL);
296
297 /* perform a binary search on the clique hash table */
298 left = 0;
299 right = cliquehash->ncliques-1;
300 while( left <= right )
301 {
302 middle = (left+right)/2;
303 cmp = compSubcliques(clique, cliquehash->cliques[middle]);
304 if( cmp > 0 )
305 left = middle+1;
306 else if( cmp < 0 )
307 right = middle-1;
308 else
309 {
310 *insertpos = middle;
311 return TRUE;
312 }
313 }
314
315 /* we found the correct insertion position for the clique, but it might be contained in a lex-smaller clique */
316 *insertpos = left;
317 for( middle = left-1; middle >= 0; --middle )
318 {
319 cmp = compSubcliques(clique, cliquehash->cliques[middle]);
320 assert(cmp >= 0);
321 if( cmp == 0 )
322 return TRUE;
323 }
324
325 return FALSE;
326 }
327
328 /** inserts clique into clique hash table */
329 static
insertClique(CLIQUEHASH * cliquehash,CLIQUE * clique,int insertpos)330 void insertClique(
331 CLIQUEHASH* cliquehash, /**< clique hash table */
332 CLIQUE* clique, /**< clique to search in the table */
333 int insertpos /**< position to insert clique into table (returned by inCliquehash()) */
334 )
335 {
336 int i;
337
338 assert(cliquehash != NULL);
339 assert(clique != NULL);
340 assert(0 <= insertpos && insertpos <= cliquehash->ncliques);
341
342 /* allocate memory */
343 ensureCliquehashSize(cliquehash, cliquehash->ncliques+1);
344
345 /* insert clique into table */
346 for( i = cliquehash->ncliques; i > insertpos; --i )
347 cliquehash->cliques[i] = cliquehash->cliques[i-1];
348 cliquehash->cliques[insertpos] = clique;
349 cliquehash->ncliques++;
350
351 /* check, whether the clique hash table is still sorted */
352 checkCliquehash(cliquehash);
353
354 debug(printCliquehash(cliquehash));
355 }
356
357
358
359
360 /****************************
361 * clique calculation methods
362 ****************************/
363
364 /** extends given clique by additional zero-weight nodes of the given node set */
365 static
extendCliqueZeroWeight(TCLIQUE_SELECTADJNODES ((* selectadjnodes)),TCLIQUE_GRAPH * tcliquegraph,int * buffer,int * Vzero,int nVzero,int maxnzeroextensions,int * curcliquenodes,int * ncurcliquenodes)366 void extendCliqueZeroWeight(
367 TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
368 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
369 int* buffer, /**< buffer of size nnodes */
370 int* Vzero, /**< zero weighted nodes */
371 int nVzero, /**< number of zero weighted nodes */
372 int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
373 int* curcliquenodes, /**< nodes of the clique */
374 int* ncurcliquenodes /**< pointer to store number of nodes in the clique */
375 )
376 {
377 int i;
378 int* zerocands;
379 int nzerocands;
380 int nzeroextensions;
381
382 assert(selectadjnodes != NULL);
383 assert(buffer != NULL);
384 assert(Vzero != NULL);
385 assert(curcliquenodes != NULL);
386 assert(ncurcliquenodes != NULL);
387
388 debugMessage("extending temporary clique (size %d) with zero-weighted nodes (nVzero=%d)\n", *ncurcliquenodes, nVzero);
389
390 if( maxnzeroextensions == 0 )
391 return;
392
393 /* initialize the zero-weighted candidates for clique extension */
394 zerocands = buffer;
395 BMScopyMemoryArray(zerocands, Vzero, nVzero);
396 nzerocands = nVzero;
397
398 /* for each node in the clique, remove non-adjacent nodes from the zero extension candidates */
399 for( i = 0; i < *ncurcliquenodes && nzerocands > 0; ++i )
400 {
401 nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[i], zerocands, nzerocands, zerocands);
402 }
403
404 /* put zero-weighted candidates into the clique, and remove non-adjacent nodes from the candidate set */
405 nzeroextensions = 0;
406 while( nzerocands > 0 )
407 {
408 /* put first candidate into the clique */
409 curcliquenodes[*ncurcliquenodes] = zerocands[0];
410 (*ncurcliquenodes)++;
411 nzerocands--;
412 zerocands++;
413 nzeroextensions++;
414 if( nzeroextensions >= maxnzeroextensions )
415 break;
416
417 /* remove candidates that are not adjacent to the inserted zero-weighted node */
418 nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[(*ncurcliquenodes)-1], zerocands, nzerocands, zerocands);
419 }
420 }
421
422 /** calls user callback after a new solution was found, that is better than the current incumbent
423 *
424 * The callback decides, whether this solution should be accepted as new incumbent, and whether the solution process
425 * should be stopped.
426 */
427 static
newSolution(TCLIQUE_SELECTADJNODES ((* selectadjnodes)),TCLIQUE_GRAPH * tcliquegraph,TCLIQUE_NEWSOL ((* newsol)),TCLIQUE_DATA * tcliquedata,CLIQUEHASH * cliquehash,int * buffer,int * Vzero,int nVzero,int maxnzeroextensions,int * curcliquenodes,int ncurcliquenodes,TCLIQUE_WEIGHT curcliqueweight,int * maxcliquenodes,int * nmaxcliquenodes,TCLIQUE_WEIGHT * maxcliqueweight,TCLIQUE_Bool * stopsolving)428 void newSolution(
429 TCLIQUE_SELECTADJNODES((*selectadjnodes)), /**< user function to select adjacent edges */
430 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
431 TCLIQUE_NEWSOL((*newsol)), /**< user function to call on every new solution */
432 TCLIQUE_DATA* tcliquedata, /**< user data to pass to user callback function */
433 CLIQUEHASH* cliquehash, /**< clique hash table */
434 int* buffer, /**< buffer of size nnodes */
435 int* Vzero, /**< zero weighted nodes */
436 int nVzero, /**< number of zero weighted nodes */
437 int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
438 int* curcliquenodes, /**< nodes of the new clique */
439 int ncurcliquenodes, /**< number of nodes in the new clique */
440 TCLIQUE_WEIGHT curcliqueweight, /**< weight of the new clique */
441 int* maxcliquenodes, /**< pointer to store nodes of the maximum weight clique */
442 int* nmaxcliquenodes, /**< pointer to store number of nodes in the maximum weight clique */
443 TCLIQUE_WEIGHT* maxcliqueweight, /**< pointer to store weight of the maximum weight clique */
444 TCLIQUE_Bool* stopsolving /**< pointer to store whether the solving should be stopped */
445 )
446 {
447 CLIQUE* clique;
448 int insertpos;
449 TCLIQUE_Bool acceptsol;
450
451 assert(curcliquenodes != NULL);
452 assert(maxcliquenodes != NULL);
453 assert(nmaxcliquenodes != NULL);
454 assert(maxcliqueweight != NULL);
455 assert(curcliqueweight > *maxcliqueweight);
456 assert(stopsolving != NULL);
457 assert(newsol == NULL || cliquehash != NULL);
458
459 acceptsol = TRUE;
460 *stopsolving = FALSE;
461 clique = NULL;
462 insertpos = 0;
463
464 if( newsol != NULL )
465 {
466 /* check whether the clique is already stored in the table */
467 if( cliquehash->ncliques > 0 )
468 {
469 createClique(&clique, curcliquenodes, ncurcliquenodes);
470 acceptsol = !inCliquehash(cliquehash, clique, &insertpos);
471 }
472 }
473
474 /* check, if this is a new clique */
475 if( acceptsol )
476 {
477 /* extend the clique with the zero-weighted nodes */
478 extendCliqueZeroWeight(selectadjnodes, tcliquegraph, buffer, Vzero, nVzero, maxnzeroextensions,
479 curcliquenodes, &ncurcliquenodes);
480
481 if( newsol != NULL )
482 {
483 /* call user callback method */
484 newsol(tcliquedata, curcliquenodes, ncurcliquenodes, curcliqueweight, maxcliqueweight, &acceptsol, stopsolving);
485
486 /* if clique was accepted, clear the clique hash table; otherwise, insert it into the clique hash table, such that
487 * the same or a weaker clique is not presented to the user again
488 */
489 if( acceptsol )
490 clearCliquehash(cliquehash);
491 else
492 {
493 /* if the clique was not yet created, do it now */
494 if( clique == NULL )
495 {
496 assert(insertpos == 0);
497 assert(cliquehash->ncliques == 0);
498 createClique(&clique, curcliquenodes, ncurcliquenodes);
499 }
500
501 /* insert clique into clique hash table */
502 insertClique(cliquehash, clique, insertpos);
503 clique = NULL; /* the clique now belongs to the table */
504 }
505 }
506 }
507
508 /* free the clique, if it was created and not put into the clique hash table */
509 if( clique != NULL )
510 freeClique(&clique);
511
512 if( acceptsol )
513 {
514 /* copy the solution to the incumbent */
515 BMScopyMemoryArray(maxcliquenodes, curcliquenodes, ncurcliquenodes);
516 *nmaxcliquenodes = ncurcliquenodes;
517 if( curcliqueweight > *maxcliqueweight )
518 *maxcliqueweight = curcliqueweight;
519 }
520
521 #ifdef TCLIQUE_DEBUG
522 debugMessage(" -> clique %s (weight %d):", acceptsol ? "accepted" : "rejected", curcliqueweight);
523 {
524 int i;
525 for( i = 0; i < ncurcliquenodes; ++i )
526 debugPrintf(" %d", curcliquenodes[i]);
527 debugPrintf("\n");
528 }
529 #endif
530 }
531
532 /** tries to find a clique, if V has only one or two nodes */
533 static
reduced(TCLIQUE_GETWEIGHTS ((* getweights)),TCLIQUE_ISEDGE ((* isedge)),TCLIQUE_GRAPH * tcliquegraph,int * V,int nV,TCLIQUE_WEIGHT * apbound,int * tmpcliquenodes,int * ntmpcliquenodes,TCLIQUE_WEIGHT * tmpcliqueweight)534 void reduced(
535 TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
536 TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */
537 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
538 int* V, /**< non-zero weighted nodes for branching */
539 int nV, /**< number of non-zero weighted nodes for branching */
540 TCLIQUE_WEIGHT* apbound, /**< apriori bound of nodes for branching */
541 int* tmpcliquenodes, /**< buffer for storing the temporary clique */
542 int* ntmpcliquenodes, /**< pointer to store number of nodes of the temporary clique */
543 TCLIQUE_WEIGHT* tmpcliqueweight /**< pointer to store weight of the temporary clique */
544 )
545 {
546 const TCLIQUE_WEIGHT* weights;
547
548 assert(getweights != NULL);
549 assert(isedge != NULL);
550 assert(tcliquegraph != NULL);
551 assert(V != NULL);
552 assert(0 <= nV && nV <= 2);
553 assert(apbound != NULL);
554 assert(tmpcliquenodes != NULL);
555 assert(ntmpcliquenodes != NULL);
556 assert(tmpcliqueweight != NULL);
557
558 weights = getweights(tcliquegraph);
559 assert(nV == 0 || weights[V[0]] > 0);
560 assert(nV <= 1 || weights[V[1]] > 0);
561
562 if( nV >= 1 )
563 apbound[0] = weights[V[0]];
564 if( nV >= 2 )
565 apbound[1] = weights[V[1]];
566
567 /* check if nodes are adjacent */
568 if( nV >= 2 && isedge(tcliquegraph, V[0], V[1]) )
569 {
570 assert(isedge(tcliquegraph, V[1], V[0]));
571
572 /* put nodes into clique */
573 tmpcliquenodes[0] = V[0];
574 tmpcliquenodes[1] = V[1];
575 *ntmpcliquenodes = 2;
576 *tmpcliqueweight = weights[V[0]] + weights[V[1]];
577 apbound[0] += weights[V[1]];
578 }
579 else if( nV >= 2 && weights[V[1]] > weights[V[0]] )
580 {
581 /* put V[1] into clique */
582 tmpcliquenodes[0] = V[1];
583 *ntmpcliquenodes = 1;
584 *tmpcliqueweight = weights[V[1]];
585 }
586 else if( nV >= 1 )
587 {
588 /* put V[0] into clique */
589 tmpcliquenodes[0] = V[0];
590 *ntmpcliquenodes = 1;
591 *tmpcliqueweight = weights[V[0]];
592 }
593 else
594 {
595 *tmpcliqueweight = 0;
596 *ntmpcliquenodes = 0;
597 }
598 }
599
600 /** calculates upper bound on remaining subgraph, and heuristically generates a clique */
601 static
boundSubgraph(TCLIQUE_GETNNODES ((* getnnodes)),TCLIQUE_GETWEIGHTS ((* getweights)),TCLIQUE_ISEDGE ((* isedge)),TCLIQUE_SELECTADJNODES ((* selectadjnodes)),TCLIQUE_GRAPH * tcliquegraph,BMS_CHKMEM * mem,int * buffer,int * V,int nV,NBC * gsd,TCLIQUE_Bool * iscolored,TCLIQUE_WEIGHT * apbound,int * tmpcliquenodes,int * ntmpcliquenodes,TCLIQUE_WEIGHT * tmpcliqueweight)602 TCLIQUE_WEIGHT boundSubgraph(
603 TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
604 TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
605 TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */
606 TCLIQUE_SELECTADJNODES((*selectadjnodes)), /**< user function to select adjacent edges */
607 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
608 BMS_CHKMEM* mem, /**< block memory */
609 int* buffer, /**< buffer of size nnodes */
610 int* V, /**< non-zero weighted nodes for branching */
611 int nV, /**< number of non-zero weighted nodes for branching */
612 NBC* gsd, /**< neighbour color information of all nodes */
613 TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
614 TCLIQUE_WEIGHT* apbound, /**< apriori bound of nodes for branching */
615 int* tmpcliquenodes, /**< buffer for storing the temporary clique */
616 int* ntmpcliquenodes, /**< pointer to store number of nodes of the temporary clique */
617 TCLIQUE_WEIGHT* tmpcliqueweight /**< pointer to store weight of the temporary clique */
618 )
619 {
620 assert(tmpcliqueweight != NULL);
621
622 /* check if we are in an easy case with at most 2 nodes left */
623 if( nV <= 2 )
624 {
625 /* get 1- or 2-clique and bounds without coloring */
626 reduced(getweights, isedge, tcliquegraph, V, nV, apbound, tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
627 return *tmpcliqueweight;
628 }
629 else
630 {
631 /* color the graph induces by nodes of V to get an upper bound for the remaining subgraph */
632 return tcliqueColoring(getnnodes, getweights, selectadjnodes, tcliquegraph,
633 mem, buffer, V, nV, gsd, iscolored, apbound,
634 tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
635 }
636 }
637
638 /** gets the index of the node of V with the maximum apriori bound; returns -1, if no node exists */
639 static
getMaxApBoundIndex(int nV,TCLIQUE_WEIGHT * apbound)640 int getMaxApBoundIndex(
641 int nV, /**< number of nodes of V */
642 TCLIQUE_WEIGHT* apbound /**< apriori bound of nodes of V */
643 )
644 {
645 TCLIQUE_WEIGHT maxapbound;
646 int maxindex;
647 int i;
648
649 assert(apbound != NULL);
650
651 maxapbound = 0;
652 maxindex = -1;
653
654 for( i = 0 ; i < nV; i++ )
655 {
656 assert(apbound[i] > 0);
657 if( apbound[i] >= maxapbound )
658 {
659 maxapbound = apbound[i];
660 maxindex = i;
661 }
662 }
663
664 return maxindex;
665 }
666
667 /** gets the index of the node of V with the maximum apriori bound, but ignores nodes with weights
668 * larger than the given maximal weight
669 *
670 * Returns -1 if no node with weight smaller or equal than maxweight is found.
671 */
672 static
getMaxApBoundIndexNotMaxWeight(int * V,int nV,const TCLIQUE_WEIGHT * apbound,const TCLIQUE_WEIGHT * weights,TCLIQUE_WEIGHT maxweight)673 int getMaxApBoundIndexNotMaxWeight(
674 int* V, /**< non-zero weighted nodes for branching */
675 int nV, /**< number of non-zero weighted nodes for branching */
676 const TCLIQUE_WEIGHT* apbound, /**< apriori bound of nodes of V */
677 const TCLIQUE_WEIGHT* weights, /**< weights of nodes */
678 TCLIQUE_WEIGHT maxweight /**< maximal weight of node to be candidate for selection */
679 )
680 {
681 TCLIQUE_WEIGHT maxapbound;
682 int maxindex;
683 int i;
684
685 assert(apbound != NULL);
686
687 maxapbound = 0;
688 maxindex = -1;
689
690 for( i = 0 ; i < nV; i++ )
691 {
692 assert(apbound[i] > 0);
693 assert(weights[V[i]] > 0);
694
695 if( apbound[i] >= maxapbound && weights[V[i]] <= maxweight )
696 {
697 maxapbound = apbound[i];
698 maxindex = i;
699 }
700 }
701
702 return maxindex;
703 }
704
705 /** branches the searching tree, branching nodes are selected in decreasing order of their apriori bound,
706 * returns the level to which we should backtrack, or INT_MAX for continuing normally
707 */
708 static
branch(TCLIQUE_GETNNODES ((* getnnodes)),TCLIQUE_GETWEIGHTS ((* getweights)),TCLIQUE_ISEDGE ((* isedge)),TCLIQUE_SELECTADJNODES ((* selectadjnodes)),TCLIQUE_GRAPH * tcliquegraph,TCLIQUE_NEWSOL ((* newsol)),TCLIQUE_DATA * tcliquedata,BMS_CHKMEM * mem,CLIQUEHASH * cliquehash,int * buffer,int level,int * V,int nV,int * Vzero,int nVzero,NBC * gsd,TCLIQUE_Bool * iscolored,int * K,TCLIQUE_WEIGHT weightK,int * maxcliquenodes,int * nmaxcliquenodes,TCLIQUE_WEIGHT * maxcliqueweight,int * curcliquenodes,int * ncurcliquenodes,TCLIQUE_WEIGHT * curcliqueweight,int * tmpcliquenodes,TCLIQUE_WEIGHT maxfirstnodeweight,int * ntreenodes,int maxntreenodes,int backtrackfreq,int maxnzeroextensions,int fixednode,TCLIQUE_STATUS * status)709 int branch(
710 TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
711 TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
712 TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */
713 TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
714 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
715 TCLIQUE_NEWSOL((*newsol)), /**< user function to call on every new solution */
716 TCLIQUE_DATA* tcliquedata, /**< user data to pass to user callback function */
717 BMS_CHKMEM* mem, /**< block memory */
718 CLIQUEHASH* cliquehash, /**< clique hash table */
719 int* buffer, /**< buffer of size nnodes */
720 int level, /**< level of b&b tree */
721 int* V, /**< non-zero weighted nodes for branching */
722 int nV, /**< number of non-zero weighted nodes for branching */
723 int* Vzero, /**< zero weighted nodes */
724 int nVzero, /**< number of zero weighted nodes */
725 NBC* gsd, /**< neighbour color information of all nodes */
726 TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
727 int* K, /**< nodes from the b&b tree */
728 TCLIQUE_WEIGHT weightK, /**< weight of the nodes from b&b tree */
729 int* maxcliquenodes, /**< pointer to store nodes of the maximum weight clique */
730 int* nmaxcliquenodes, /**< pointer to store number of nodes in the maximum weight clique */
731 TCLIQUE_WEIGHT* maxcliqueweight, /**< pointer to store weight of the maximum weight clique */
732 int* curcliquenodes, /**< pointer to store nodes of currenct clique */
733 int* ncurcliquenodes, /**< pointer to store number of nodes in current clique */
734 TCLIQUE_WEIGHT* curcliqueweight, /**< pointer to store weight of current clique */
735 int* tmpcliquenodes, /**< buffer for storing the temporary clique */
736 TCLIQUE_WEIGHT maxfirstnodeweight, /**< maximum weight of branching nodes in level 0; 0 if not used
737 * (for cliques with at least one fractional node) */
738 int* ntreenodes, /**< pointer to store number of nodes of b&b tree */
739 int maxntreenodes, /**< maximal number of nodes of b&b tree */
740 int backtrackfreq, /**< frequency to backtrack to first level of tree (0: no premature backtracking) */
741 int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
742 int fixednode, /**< node that is forced to be in the clique, or -1; must have positive weight */
743 TCLIQUE_STATUS* status /**< pointer to store the status of the solving call */
744 )
745 {
746 TCLIQUE_Bool isleaf;
747 const TCLIQUE_WEIGHT* weights;
748 TCLIQUE_WEIGHT* apbound;
749 TCLIQUE_WEIGHT subgraphweight;
750 TCLIQUE_WEIGHT weightKold;
751 TCLIQUE_WEIGHT tmpcliqueweight;
752 int backtracklevel;
753 int ntmpcliquenodes;
754 int i;
755
756 assert(getnnodes != NULL);
757 assert(getweights != NULL);
758 assert(selectadjnodes != NULL);
759 assert(mem != NULL);
760 assert(V != NULL);
761 assert(gsd != NULL);
762 assert(iscolored != NULL);
763 assert(K != NULL);
764 assert(maxcliqueweight != NULL);
765 assert(curcliquenodes != NULL);
766 assert(ncurcliquenodes != NULL);
767 assert(curcliqueweight != NULL);
768 assert(ntreenodes != NULL);
769 assert(maxfirstnodeweight >= 0);
770 assert(*ntreenodes >= 0);
771 assert(maxntreenodes >= 0);
772 assert(status != NULL);
773
774 /* increase the number of nodes, and stop solving, if the node limit is exceeded */
775 (*ntreenodes)++;
776 #ifdef TCLIQUE_DEBUG
777 debugMessage("(level %d, treenode %d) maxclique = %d, curclique = %d [mem=%" SCIP_LONGINT_FORMAT " (%" SCIP_LONGINT_FORMAT "), cliques=%d]\n",
778 level, *ntreenodes, *maxcliqueweight, *curcliqueweight,
779 BMSgetChunkMemoryUsed(mem), BMSgetMemoryUsed(), cliquehash == NULL ? 0 : cliquehash->ncliques);
780
781 debugMessage(" -> current branching (weight %d):", weightK);
782 for( i = 0; i < level; ++i )
783 debugPrintf(" %d", K[i]);
784 debugPrintf("\n");
785 debugMessage(" -> branching candidates:");
786 for( i = 0; i < nV; ++i )
787 debugPrintf(" %d", V[i]);
788 debugPrintf("\n");
789 #endif
790 if( *ntreenodes > maxntreenodes )
791 {
792 *status = TCLIQUE_NODELIMIT;
793 return TRUE;
794 }
795
796 weights = getweights(tcliquegraph);
797 backtracklevel = INT_MAX;
798 isleaf = TRUE;
799
800 /* allocate temporary memory for a priori bounds */
801 ALLOC_ABORT( BMSallocMemoryArray(&apbound, nV) );
802 BMSclearMemoryArray(apbound, nV);
803
804 /* use coloring relaxation to generate an upper bound for the current subtree and a heuristic solution */
805 subgraphweight = boundSubgraph(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph,
806 mem, buffer, V, nV, gsd, iscolored, apbound,
807 tmpcliquenodes, &ntmpcliquenodes, &tmpcliqueweight);
808
809 #ifndef NDEBUG
810 /* check correctness of V and apbound arrays */
811 for( i = 0; i < nV; ++i )
812 {
813 assert(0 <= V[i] && V[i] < getnnodes(tcliquegraph));
814 assert(i == 0 || V[i-1] < V[i]);
815 assert(apbound[i] >= 0);
816 assert((apbound[i] == 0) == (weights[V[i]] == 0));
817 }
818 #endif
819
820 /* check, whether the heuristic solution is better than the current subtree's solution;
821 * if the user wanted to have a fixed variable inside the clique and we are in level 0, we first have to
822 * fix this variable in this level (the current clique might not contain the fixed node)
823 */
824 if( weightK + tmpcliqueweight > *curcliqueweight && (level > 0 || fixednode == -1) )
825 {
826 /* install the newly generated clique as current clique */
827 for( i = 0; i < level; ++i )
828 curcliquenodes[i] = K[i];
829 for( i = 0; i < ntmpcliquenodes; ++i )
830 curcliquenodes[level+i] = tmpcliquenodes[i];
831 *ncurcliquenodes = level + ntmpcliquenodes;
832 *curcliqueweight = weightK + tmpcliqueweight;
833
834 #ifdef TCLIQUE_DEBUG
835 debugMessage(" -> new current clique with weight %d at node %d in level %d:",
836 *curcliqueweight, *ntreenodes, level);
837 for( i = 0; i < *ncurcliquenodes; ++i )
838 debugPrintf(" %d", curcliquenodes[i]);
839 debugPrintf("\n");
840 #endif
841 }
842
843 /* discard subtree, if the upper bound is not better than the weight of the currently best clique;
844 * if only 2 nodes are left, the maximal weighted clique was already calculated in boundSubgraph() and nothing
845 * more has to be done;
846 * however, if the user wanted to have a fixed node and we are in the first decision level, we have to continue
847 */
848 if( weightK + subgraphweight > *maxcliqueweight && (nV > 2 || (fixednode >= 0 && level == 0)) )
849 {
850 int* Vcurrent;
851 int nVcurrent;
852 int nValive;
853 int branchingnode;
854
855 assert(nV > 0);
856
857 /* process current subtree */
858 level++;
859
860 /* set up data structures */
861 ALLOC_ABORT( BMSallocMemoryArray(&Vcurrent, nV-1) );
862
863 nValive = nV;
864 weightKold = weightK;
865
866 debugMessage("============================ branching level %d ===============================\n", level);
867
868 /* branch on the nodes of V by decreasing order of their apriori bound */
869 while( backtracklevel >= level && nValive > 0 )
870 {
871 int branchidx;
872
873 /* check if we meet the backtracking frequency - in this case abort the search until we have reached first level */
874 if( level > 1 && backtrackfreq > 0 && (*ntreenodes) % backtrackfreq == 0 )
875 {
876 backtracklevel = 1;
877 break;
878 }
879
880 /* get next branching node */
881 if( level == 1 && fixednode >= 0 )
882 {
883 /* select the fixed node as first "branching" candidate */
884 for( branchidx = 0; branchidx < nValive && V[branchidx] != fixednode; branchidx++ )
885 {}
886 assert(branchidx < nValive);
887 assert(V[branchidx] == fixednode);
888 }
889 else if( level == 1 && maxfirstnodeweight > 0 )
890 branchidx = getMaxApBoundIndexNotMaxWeight(V, nValive, apbound, weights, maxfirstnodeweight);
891 else
892 branchidx = getMaxApBoundIndex(nValive, apbound);
893 if( branchidx < 0 )
894 break;
895 assert(0 <= branchidx && branchidx < nValive && nValive <= nV);
896 assert(apbound[branchidx] > 0);
897 assert(weights[V[branchidx]] > 0);
898
899 /* test a priori bound */
900 if( (weightKold + apbound[branchidx]) <= *maxcliqueweight )
901 break;
902
903 debugMessage("%d. branching in level %d (treenode %d): bidx=%d, node %d, weight %d, upperbound: %d+%d = %d, maxclique=%d\n",
904 nV-nValive+1, level, *ntreenodes, branchidx, V[branchidx], weights[V[branchidx]], weightKold,
905 apbound[branchidx], weightKold + apbound[branchidx], *maxcliqueweight);
906
907 /* because we branch on this node, the node is no leaf in the tree */
908 isleaf = FALSE;
909
910 /* update the set of nodes from the b&b tree
911 * K = K & {branchingnode}
912 */
913 branchingnode = V[branchidx];
914 K[level-1] = branchingnode;
915 weightK = weightKold + weights[branchingnode];
916
917 /* update the set of nodes for branching
918 * V = V \ {branchingnode}
919 */
920 nValive--;
921 for( i = branchidx; i < nValive; ++i )
922 {
923 V[i] = V[i+1];
924 apbound[i] = apbound[i+1];
925 }
926
927 /* set the nodes for the next level of b&b tree
928 * Vcurrent = nodes of V, that are adjacent to branchingnode
929 */
930 nVcurrent = selectadjnodes(tcliquegraph, branchingnode, V, nValive, Vcurrent);
931
932 /* process the selected subtree */
933 backtracklevel = branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata, /*lint !e838*/
934 mem, cliquehash, buffer,
935 level, Vcurrent, nVcurrent, Vzero, nVzero, gsd, iscolored, K, weightK,
936 maxcliquenodes, nmaxcliquenodes, maxcliqueweight,
937 curcliquenodes, ncurcliquenodes, curcliqueweight, tmpcliquenodes,
938 maxfirstnodeweight, ntreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, -1, status);
939
940 /* if all other candidates stayed in the candidate list, the current branching was optimal and
941 * there is no need to try the remaining ones
942 */
943 if( nVcurrent == nValive )
944 {
945 debugMessage("branching on node %d was optimal - ignoring remaining candidates\n", branchingnode);
946 nValive = 0;
947 }
948
949 /* if we had a fixed node, ignore all other nodes */
950 if( fixednode >= 0 )
951 nValive = 0;
952 }
953
954 debugMessage("========================== branching level %d end =============================\n\n", level);
955
956 /* free data structures */
957 BMSfreeMemoryArray(&Vcurrent);
958 }
959
960 /* check, whether any branchings have been applied, or if this node is a leaf of the branching tree */
961 if( isleaf )
962 {
963 /* the current clique is the best clique found on the path to this leaf
964 * -> check, whether it is an improvement to the currently best clique
965 */
966 if( *curcliqueweight > *maxcliqueweight )
967 {
968 TCLIQUE_Bool stopsolving;
969
970 debugMessage("found clique of weight %d at node %d in level %d\n", *curcliqueweight, *ntreenodes, level);
971 newSolution(selectadjnodes, tcliquegraph, newsol, tcliquedata, cliquehash, buffer, Vzero, nVzero,
972 maxnzeroextensions, curcliquenodes, *ncurcliquenodes, *curcliqueweight,
973 maxcliquenodes, nmaxcliquenodes, maxcliqueweight, &stopsolving);
974
975 if( stopsolving )
976 {
977 debugMessage(" -> solving terminated by callback method\n");
978 backtracklevel = 0;
979 }
980 }
981
982 /* discard the current clique */
983 *ncurcliquenodes = 0;
984 *curcliqueweight = 0;
985 }
986
987 #ifdef TCLIQUE_DEBUG
988 if( level > backtracklevel )
989 {
990 debugMessage("premature backtracking after %d nodes - level %d\n", *ntreenodes, level);
991 }
992 #endif
993
994 /* free data structures */
995 BMSfreeMemoryArray(&apbound);
996
997 return backtracklevel;
998 }
999
1000 /** finds maximum weight clique */
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)1001 void tcliqueMaxClique(
1002 TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
1003 TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
1004 TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */
1005 TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
1006 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure that is passed to graph callbacks */
1007 TCLIQUE_NEWSOL((*newsol)), /**< user function to call on every new solution */
1008 TCLIQUE_DATA* tcliquedata, /**< user data to pass to new solution callback function */
1009 int* maxcliquenodes, /**< pointer to store nodes of the maximum weight clique */
1010 int* nmaxcliquenodes, /**< pointer to store number of nodes in the maximum weight clique */
1011 TCLIQUE_WEIGHT* maxcliqueweight, /**< pointer to store weight of the maximum weight clique */
1012 TCLIQUE_WEIGHT maxfirstnodeweight, /**< maximum weight of branching nodes in level 0; 0 if not used
1013 * for cliques with at least one fractional node) */
1014 TCLIQUE_WEIGHT minweight, /**< lower bound for weight of generated cliques */
1015 int maxntreenodes, /**< maximal number of nodes of b&b tree */
1016 int backtrackfreq, /**< frequency to backtrack to first level of tree (0: no premature backtracking) */
1017 int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
1018 int fixednode, /**< node that is forced to be in the clique, or -1; must have positive weight */
1019 int* ntreenodes, /**< pointer to store the number of used tree nodes (or NULL) */
1020 TCLIQUE_STATUS* status /**< pointer to store the status of the solving call */
1021 )
1022 {
1023 CLIQUEHASH* cliquehash;
1024 const TCLIQUE_WEIGHT* weights;
1025 int* buffer;
1026 int* K;
1027 int* V;
1028 int* Vzero;
1029 int nnodes;
1030 int nV;
1031 int nVzero;
1032 int i;
1033 BMS_CHKMEM* mem;
1034 NBC* gsd;
1035 TCLIQUE_Bool* iscolored;
1036 int* curcliquenodes;
1037 int ncurcliquenodes;
1038 TCLIQUE_WEIGHT curcliqueweight;
1039 int* tmpcliquenodes;
1040 int nbbtreenodes;
1041 int backtracklevel;
1042
1043 assert(maxcliquenodes != NULL);
1044 assert(nmaxcliquenodes != NULL);
1045 assert(maxcliqueweight != NULL);
1046 assert(maxntreenodes >= 0);
1047 assert(backtrackfreq >= 0);
1048 assert(maxnzeroextensions >= 0);
1049 assert(status != NULL);
1050
1051 *status = TCLIQUE_OPTIMAL;
1052
1053 /* use default graph callbacks, if NULL pointers are given */
1054 if( getnnodes == NULL )
1055 getnnodes = tcliqueGetNNodes;
1056 if( getweights == NULL )
1057 getweights = tcliqueGetWeights;
1058 if( isedge == NULL )
1059 isedge = tcliqueIsEdge;
1060 if( selectadjnodes == NULL )
1061 selectadjnodes = tcliqueSelectAdjnodes;
1062
1063 /* get number of nodes */
1064 nnodes = getnnodes(tcliquegraph);
1065
1066 debugMessage("calculating maximal weighted clique in graph (%d nodes)\n", nnodes);
1067
1068 /* set up data structures */
1069 if( newsol != NULL )
1070 createCliquehash(&cliquehash, CLIQUEHASH_INITSIZE);
1071 else
1072 cliquehash = NULL;
1073 ALLOC_ABORT( BMSallocMemoryArray(&buffer, nnodes) );
1074 ALLOC_ABORT( BMSallocMemoryArray(&K, nnodes) );
1075 ALLOC_ABORT( BMSallocMemoryArray(&V, nnodes) );
1076 ALLOC_ABORT( BMSallocMemoryArray(&Vzero, nnodes) );
1077 ALLOC_ABORT( BMSallocMemoryArray(&gsd, nnodes) );
1078 ALLOC_ABORT( BMSallocMemoryArray(&iscolored, nnodes) );
1079 ALLOC_ABORT( BMSallocMemoryArray(&curcliquenodes, nnodes) );
1080 ALLOC_ABORT( BMSallocMemoryArray(&tmpcliquenodes, nnodes) );
1081
1082 /* set weight and number of nodes of maximum weighted clique */
1083 *nmaxcliquenodes = 0;
1084 *maxcliqueweight = minweight-1;
1085 ncurcliquenodes = 0;
1086 curcliqueweight = 0;
1087 nbbtreenodes = 0;
1088
1089 /* set up V and Vzero */
1090 weights = getweights(tcliquegraph);
1091 assert(weights != NULL);
1092 nV = 0;
1093 nVzero = 0;
1094 for( i = 0 ; i < nnodes; i++ )
1095 {
1096 if( weights[i] == 0 )
1097 {
1098 Vzero[nVzero] = i;
1099 nVzero++;
1100 }
1101 else
1102 {
1103 V[nV] = i;
1104 nV++;
1105 }
1106 }
1107
1108 /* initialize own memory allocator for coloring */
1109 mem = BMScreateChunkMemory(sizeof(LIST_ITV), CHUNK_SIZE, -1);
1110
1111 /* branch to find maximum weight clique */
1112 backtracklevel = branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata, mem,
1113 cliquehash, buffer, 0, V, nV, Vzero, nVzero, gsd, iscolored, K, 0,
1114 maxcliquenodes, nmaxcliquenodes, maxcliqueweight,
1115 curcliquenodes, &ncurcliquenodes, &curcliqueweight, tmpcliquenodes,
1116 maxfirstnodeweight, &nbbtreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, fixednode, status);
1117
1118 if ( ntreenodes != NULL )
1119 *ntreenodes = nbbtreenodes;
1120
1121 if( backtracklevel != INT_MAX && *status == TCLIQUE_OPTIMAL )
1122 *status = TCLIQUE_USERABORT;
1123
1124 /* delete own memory allocator for coloring */
1125 BMSdestroyChunkMemory(&mem);
1126
1127 /* free data structures */
1128 BMSfreeMemoryArray(&tmpcliquenodes);
1129 BMSfreeMemoryArray(&curcliquenodes);
1130 BMSfreeMemoryArray(&iscolored);
1131 BMSfreeMemoryArray(&gsd);
1132 BMSfreeMemoryArray(&Vzero);
1133 BMSfreeMemoryArray(&V);
1134 BMSfreeMemoryArray(&K);
1135 BMSfreeMemoryArray(&buffer);
1136 if( newsol != NULL )
1137 freeCliquehash(&cliquehash);
1138 } /*lint !e438*/
1139