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_coloring.c 26 * @ingroup OTHER_CFILES 27 * @brief coloring 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 40 #include "tclique/tclique.h" 41 #include "tclique/tclique_def.h" 42 #include "tclique/tclique_coloring.h" 43 #include "blockmemshell/memory.h" 44 45 46 47 /** gets index of the uncolored node in a given array of nodes in V with maximum satdeg; 48 * in case of a tie choose node with maximum weight; 49 * if no uncolored node is found, -1 is returned 50 */ 51 static 52 int getMaxSatdegIndex( 53 int* V, /**< non-zero weighted nodes for branching */ 54 int nV, /**< number of non-zero weighted nodes for branching */ 55 NBC* gsd, /**< neighbor color information of all nodes */ 56 TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */ 57 const TCLIQUE_WEIGHT* weights /**< weight of nodes in grpah */ 58 ) 59 { 60 TCLIQUE_WEIGHT maxweight; 61 int maxsatdeg; 62 int maxsatdegindex; 63 int i; 64 65 maxweight = -1; 66 maxsatdeg = -1; 67 maxsatdegindex = -1; 68 69 assert(gsd != NULL); 70 assert(iscolored != NULL); 71 72 for( i = 0; i < nV; i++ ) 73 { 74 TCLIQUE_WEIGHT weight; 75 int satdeg; 76 77 /* check only uncolored nodes */ 78 if( iscolored[i] ) 79 continue; 80 81 weight = weights[V[i]]; 82 assert(weight > 0); 83 84 satdeg = gsd[i].satdeg; 85 if( satdeg > maxsatdeg || (satdeg == maxsatdeg && weight > maxweight) ) 86 { 87 maxsatdeg = satdeg; 88 maxweight = weight; 89 maxsatdegindex = i; 90 } 91 } 92 93 return maxsatdegindex; 94 } 95 96 /** gets index of the node in a given set of nodes with maximum weight */ 97 static 98 int getMaxWeightIndex( 99 TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */ 100 TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */ 101 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */ 102 int* V, /**< non-zero weighted nodes for branching */ 103 int nV /**< number of non-zero weighted nodes for branching */ 104 ) 105 { 106 const TCLIQUE_WEIGHT* weights; 107 TCLIQUE_WEIGHT maxweight; 108 int maxweightindex; 109 int i; 110 111 assert(getnnodes != NULL); 112 assert(getweights != NULL); 113 assert(tcliquegraph != NULL); 114 assert(nV > 0); 115 116 weights = getweights(tcliquegraph); 117 118 maxweightindex = -1; 119 maxweight = 0; 120 121 /* try to improve maxweight */ 122 for( i = 0 ; i < nV; i++ ) 123 { 124 assert(0 <= V[i] && V[i] < getnnodes(tcliquegraph)); 125 assert(weights[V[i]] > 0); 126 if( weights[V[i]] > maxweight) 127 { 128 /* node has larger weight */ 129 maxweight = weights[V[i]]; 130 maxweightindex = i; 131 } 132 } 133 assert(maxweightindex >= 0); 134 135 return maxweightindex; 136 } 137 138 /** updates the neighbor colors information of a node: updates the list of neighbor color intervals 139 * by making the union of the existing list and the given list of color intervals, and updates the saturation degree 140 */ 141 static 142 void updateNeighbor( 143 BMS_CHKMEM* mem, /**< block memory */ 144 NBC* pgsd, /**< pointer to neighbor color information of node to update */ 145 LIST_ITV* pnc /**< pointer to given list of color intervals */ 146 ) 147 { 148 LIST_ITV head; 149 LIST_ITV* apciv; 150 LIST_ITV* pciv; 151 LIST_ITV* nciv; 152 153 /* save the pointer to the first element of the list */ 154 head.next = pgsd->lcitv; 155 apciv = &head; 156 pciv = apciv->next; 157 158 /* construct the union of the two intervals */ 159 while( (pnc != NULL) && (pciv != NULL) ) 160 { 161 if( pnc->itv.inf < pciv->itv.inf ) 162 { 163 ALLOC_ABORT( BMSallocChunkMemory(mem, &nciv) ); 164 nciv->itv = pnc->itv; 165 nciv->next = pciv; 166 apciv->next = nciv; 167 apciv = nciv; 168 169 pnc = pnc->next; 170 } 171 else if( pnc->itv.inf <= pciv->itv.sup ) 172 { 173 if( pnc->itv.sup > pciv->itv.sup ) 174 pciv->itv.sup = pnc->itv.sup; 175 pnc = pnc->next; 176 } 177 else 178 { 179 apciv = pciv; 180 pciv = pciv->next; 181 } 182 } 183 184 while( pnc != NULL ) 185 { 186 ALLOC_ABORT( BMSallocChunkMemory(mem, &nciv) ); 187 nciv->itv = pnc->itv; 188 nciv->next = NULL; 189 190 apciv->next = nciv; 191 apciv = nciv; 192 193 pnc = pnc->next; 194 } 195 196 /* try to reduce the number of intervals */ 197 pgsd->satdeg = 0; 198 apciv = head.next; 199 while( (pciv = apciv->next) != NULL ) /*lint !e838*/ 200 { 201 if( apciv->itv.sup < (pciv->itv.inf - 1) ) 202 { 203 pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1; 204 apciv = apciv->next; 205 } 206 else 207 { 208 LIST_ITV* tmp; 209 210 if( apciv->itv.sup < pciv->itv.sup ) 211 apciv->itv.sup = pciv->itv.sup; 212 apciv->next = pciv->next; 213 214 /* free data structure for created colorinterval */ 215 tmp = pciv->next; 216 /* coverity[double_free] */ 217 BMSfreeChunkMemory(mem, &pciv); 218 pciv = tmp; 219 } 220 } 221 pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1; 222 223 /* updates the pointer to the first element of the list */ 224 pgsd->lcitv = head.next; 225 } 226 227 /** colors the positive weighted nodes of a given set of nodes V with the lowest possible number of colors and 228 * finds a clique in the graph induced by V, an upper bound and an apriori bound for further branching steps 229 */ 230 TCLIQUE_WEIGHT tcliqueColoring( 231 TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */ 232 TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */ 233 TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */ 234 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */ 235 BMS_CHKMEM* mem, /**< block memory */ 236 int* buffer, /**< buffer of size nnodes */ 237 int* V, /**< non-zero weighted nodes for branching */ 238 int nV, /**< number of non-zero weighted nodes for branching */ 239 NBC* gsd, /**< neighbor color information of all nodes */ 240 TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */ 241 TCLIQUE_WEIGHT* apbound, /**< pointer to store apriori bound of nodes for branching */ 242 int* clique, /**< buffer for storing the clique */ 243 int* nclique, /**< pointer to store number of nodes in the clique */ 244 TCLIQUE_WEIGHT* weightclique /**< pointer to store the weight of the clique */ 245 ) 246 { 247 const TCLIQUE_WEIGHT* weights; 248 TCLIQUE_WEIGHT maxsatdegree; 249 TCLIQUE_WEIGHT range; 250 TCLIQUE_Bool growclique; 251 int node; 252 int nodeVindex; 253 int i; 254 int j; 255 LIST_ITV* colorinterval; 256 LIST_ITV nwcitv; 257 LIST_ITV* pnc; 258 LIST_ITV* lcitv; 259 LIST_ITV* item; 260 LIST_ITV* tmpitem; 261 int* workclique; 262 int* currentclique; 263 int ncurrentclique; 264 int weightcurrentclique; 265 int* Vadj; 266 int nVadj; 267 int adjidx; 268 269 assert(getnnodes != NULL); 270 assert(getweights != NULL); 271 assert(selectadjnodes != NULL); 272 assert(buffer != NULL); 273 assert(V != NULL); 274 assert(nV > 0); 275 assert(clique != NULL); 276 assert(nclique != NULL); 277 assert(weightclique != NULL); 278 assert(gsd != NULL); 279 assert(iscolored != NULL); 280 281 weights = getweights(tcliquegraph); 282 assert(weights != NULL); 283 284 /* initialize maximum weight clique found so far */ 285 growclique = TRUE; 286 *nclique = 0; 287 *weightclique = 0; 288 289 /* get node of V with maximum weight */ 290 nodeVindex = getMaxWeightIndex(getnnodes, getweights, tcliquegraph, V, nV); 291 node = V[nodeVindex]; 292 assert(0 <= node && node < getnnodes(tcliquegraph)); 293 range = weights[node]; 294 assert(range > 0); 295 296 /* set up data structures for coloring */ 297 BMSclearMemoryArray(iscolored, nV); /* new-memory */ 298 BMSclearMemoryArray(gsd, nV); /* new-memory */ 299 iscolored[nodeVindex] = TRUE; 300 301 /* color the first node */ 302 debugMessage("---------------coloring-----------------\n"); 303 debugMessage("1. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d)\n", 304 nodeVindex, node, gsd[nodeVindex].satdeg, range); 305 306 /* set apriori bound: apbound(v_i) = satdeg(v_i) + weight(v_i) */ 307 apbound[nodeVindex] = range; 308 assert(apbound[nodeVindex] > 0); 309 310 /* update maximum saturation degree: maxsatdeg = max { satdeg(v_i) + weight(v_i) | v_i in V } */ 311 maxsatdegree = range; 312 313 debugMessage("-> updated neighbors:\n"); 314 315 /* set neighbor color of the adjacent nodes of node */ 316 Vadj = buffer; 317 nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj); 318 for( i = 0, adjidx = 0; i < nV && adjidx < nVadj; ++i ) 319 { 320 assert(V[i] <= Vadj[adjidx]); /* Vadj is a subset of V */ 321 if( V[i] == Vadj[adjidx] ) 322 { 323 /* node is adjacent to itself, but we do not need to color it again */ 324 if( i == nodeVindex ) 325 { 326 /* go to the next node in Vadj */ 327 adjidx++; 328 continue; 329 } 330 331 debugMessage(" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ", 332 i, V[i], weights[V[i]], gsd[i].satdeg); 333 334 /* sets satdeg for adjacent node */ 335 gsd[i].satdeg = range; 336 337 /* creates new color interval [1,range] */ 338 ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) ); 339 colorinterval->next = NULL; 340 colorinterval->itv.inf = 1; 341 colorinterval->itv.sup = range; 342 343 /* colorinterval is the first added element of the list of neighborcolors of the adjacent node */ 344 gsd[i].lcitv = colorinterval; 345 346 /* go to the next node in Vadj */ 347 adjidx++; 348 349 debugPrintf("satdegnew=%d, nbc=[%d,%d]\n", gsd[i].satdeg, gsd[i].lcitv->itv.inf, gsd[i].lcitv->itv.sup); 350 } 351 } 352 353 /* set up data structures for the current clique */ 354 ALLOC_ABORT( BMSallocMemoryArray(¤tclique, nV) ); 355 workclique = clique; 356 357 /* add node to the current clique */ 358 currentclique[0] = node; 359 ncurrentclique = 1; 360 weightcurrentclique = range; 361 362 /* color all other nodes of V */ 363 for( i = 0 ; i < nV-1; i++ ) 364 { 365 assert((workclique == clique) != (currentclique == clique)); 366 367 /* selects the next uncolored node to color */ 368 nodeVindex = getMaxSatdegIndex(V, nV, gsd, iscolored, weights); 369 if( nodeVindex == -1 ) /* no uncolored nodes left */ 370 break; 371 372 node = V[nodeVindex]; 373 assert(0 <= node && node < getnnodes(tcliquegraph)); 374 range = weights[node]; 375 assert(range > 0); 376 iscolored[nodeVindex] = TRUE; 377 378 debugMessage("%d. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d, growclique=%u, weight=%d)\n", 379 i+2, nodeVindex, node, gsd[nodeVindex].satdeg, range, growclique, weightcurrentclique); 380 381 /* set apriori bound: apbound(v_i) = satdeg(v_i) + weight(v_i) */ 382 apbound[nodeVindex] = gsd[nodeVindex].satdeg + range; 383 assert(apbound[nodeVindex] > 0); 384 385 /* update maximum saturation degree: maxsatdeg = max { satdeg(v_i) + weight(v_i) | v_i in V } */ 386 if( maxsatdegree < apbound[nodeVindex] ) 387 maxsatdegree = apbound[nodeVindex]; 388 389 /* update clique */ 390 if( gsd[nodeVindex].satdeg == 0 ) 391 { 392 /* current node is not adjacent to nodes of current clique, 393 * i.e. current clique can not be increased 394 */ 395 debugMessage("current node not adjacend to current clique (weight:%d) -> starting new clique\n", 396 weightcurrentclique); 397 398 /* check, if weight of current clique is larger than weight of maximum weight clique found so far */ 399 if( weightcurrentclique > *weightclique ) 400 { 401 int* tmp; 402 403 /* update maximum weight clique found so far */ 404 assert((workclique == clique) != (currentclique == clique)); 405 tmp = workclique; 406 *weightclique = weightcurrentclique; 407 *nclique = ncurrentclique; 408 workclique = currentclique; 409 currentclique = tmp; 410 assert((workclique == clique) != (currentclique == clique)); 411 } 412 weightcurrentclique = 0; 413 ncurrentclique = 0; 414 growclique = TRUE; 415 } 416 if( growclique ) 417 { 418 /* check, if the current node is still adjacent to all nodes in the clique */ 419 if( gsd[nodeVindex].satdeg == weightcurrentclique ) 420 { 421 assert(ncurrentclique < nV); 422 currentclique[ncurrentclique] = node; 423 ncurrentclique++; 424 weightcurrentclique += range; 425 #ifdef TCLIQUE_DEBUG 426 { 427 int k; 428 debugMessage("current clique (size:%d, weight:%d):", ncurrentclique, weightcurrentclique); 429 for( k = 0; k < ncurrentclique; ++k ) 430 debugPrintf(" %d", currentclique[k]); 431 debugPrintf("\n"); 432 } 433 #endif 434 } 435 else 436 { 437 debugMessage("node satdeg: %d, clique weight: %d -> stop growing clique\n", 438 gsd[nodeVindex].satdeg, weightcurrentclique); 439 growclique = FALSE; 440 } 441 } 442 443 /* search for fitting color intervals for current node */ 444 pnc = &nwcitv; 445 if( gsd[nodeVindex].lcitv == NULL ) 446 { 447 /* current node has no colored neighbors yet: create new color interval [1,range] */ 448 ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) ); 449 colorinterval->next = NULL; 450 colorinterval->itv.inf = 1; 451 colorinterval->itv.sup = range; 452 453 /* add the new colorinterval [1, range] to the list of chosen colorintervals for node */ 454 pnc->next = colorinterval; 455 } 456 else 457 { 458 int tocolor; 459 int dif; 460 461 /* current node has colored neighbors */ 462 tocolor = range; 463 lcitv = gsd[nodeVindex].lcitv; 464 465 /* check, if first neighbor color interval [inf, sup] has inf > 1 */ 466 if( lcitv->itv.inf != 1 ) 467 { 468 /* create new interval [1, min{range, inf}] */ 469 dif = lcitv->itv.inf - 1 ; 470 if( dif > tocolor ) 471 dif = tocolor; 472 473 ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) ); 474 colorinterval->next = NULL; 475 colorinterval->itv.inf = 1; 476 colorinterval->itv.sup = dif; 477 478 tocolor -= dif; 479 pnc->next = colorinterval; 480 pnc = colorinterval; 481 } 482 483 /* as long as node is not colored with all colors, create new color interval by filling 484 * the gaps in the existing neighbor color intervals of the neighbors of node 485 */ 486 while( tocolor > 0 ) 487 { 488 dif = tocolor; 489 490 ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) ); 491 colorinterval->next = NULL; 492 colorinterval->itv.inf = lcitv->itv.sup+1; 493 if( lcitv->next != NULL ) 494 { 495 int min; 496 497 min = lcitv->next->itv.inf - lcitv->itv.sup - 1; 498 499 if( dif > min ) 500 dif = min; 501 lcitv = lcitv->next; 502 } 503 colorinterval->itv.sup = colorinterval->itv.inf + dif - 1; 504 505 tocolor -= dif; 506 pnc->next = colorinterval; 507 pnc = colorinterval; 508 } 509 } 510 511 debugMessage("-> updated neighbors:\n"); 512 513 /* update saturation degree and neighbor colorintervals of all neighbors of node */ 514 Vadj = buffer; 515 nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj); 516 for( j = 0, adjidx = 0; j < nV && adjidx < nVadj; ++j ) 517 { 518 assert(V[j] <= Vadj[adjidx]); /* Vadj is a subset of V */ 519 if( V[j] == Vadj[adjidx] ) 520 { 521 if( !iscolored[j] ) 522 { 523 debugMessage(" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ", 524 j, V[j], weights[V[j]], gsd[j].satdeg); 525 updateNeighbor(mem, &gsd[j], nwcitv.next); 526 debugPrintf("satdegnew=%d, nbc=[%d,%d]\n", gsd[j].satdeg, gsd[j].lcitv->itv.inf, gsd[j].lcitv->itv.sup); 527 } 528 529 /* go to the next node in Vadj */ 530 adjidx++; 531 } 532 } 533 534 /* free data structure of created colorintervals */ 535 item = nwcitv.next; 536 while( item != NULL ) 537 { 538 tmpitem = item->next; 539 /* coverity[double_free] */ 540 BMSfreeChunkMemory(mem, &item); 541 item = tmpitem; 542 } 543 544 /* free data structure of neighbor colorinterval of node just colored */ 545 item = gsd[nodeVindex].lcitv; 546 while( item != NULL ) 547 { 548 tmpitem = item->next; 549 /* coverity[double_free] */ 550 BMSfreeChunkMemory(mem, &item); 551 item = tmpitem; 552 } 553 } 554 assert((workclique == clique) != (currentclique == clique)); 555 556 /* update maximum weight clique found so far */ 557 if( weightcurrentclique > *weightclique ) 558 { 559 int* tmp; 560 561 tmp = workclique; 562 *weightclique = weightcurrentclique; 563 *nclique = ncurrentclique; 564 workclique = currentclique; 565 currentclique = tmp; 566 } 567 assert((workclique == clique) != (currentclique == clique)); 568 569 /* move the found clique to the provided clique pointer, if it is not the memory array */ 570 if( workclique != clique ) 571 { 572 assert(clique == currentclique); 573 assert(*nclique <= nV); 574 BMScopyMemoryArray(clique, workclique, *nclique); 575 currentclique = workclique; 576 } 577 578 /* free data structures */ 579 BMSfreeMemoryArray(¤tclique); 580 581 /* clear chunk memory */ 582 BMSclearChunkMemory(mem); 583 584 debugMessage("------------coloringend-----------------\n"); 585 586 return maxsatdegree; 587 } 588