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