60 assert(iscolored !=
NULL);
62 for( i = 0; i < nV; i++ )
71 weight = weights[V[i]];
74 satdeg = gsd[i].satdeg;
75 if( satdeg > maxsatdeg || (satdeg == maxsatdeg && weight > maxweight) )
83 return maxsatdegindex;
101 assert(getnnodes !=
NULL);
102 assert(getweights !=
NULL);
103 assert(tcliquegraph !=
NULL);
106 weights = getweights(tcliquegraph);
112 for( i = 0 ; i < nV; i++ )
114 assert(0 <= V[i] && V[i] < getnnodes(tcliquegraph));
115 assert(weights[V[i]] > 0);
116 if( weights[V[i]] > maxweight)
119 maxweight = weights[V[i]];
123 assert(maxweightindex >= 0);
125 return maxweightindex;
144 head.next = pgsd->lcitv;
149 while( (pnc !=
NULL) && (pciv !=
NULL) )
151 if( pnc->itv.inf < pciv->itv.inf )
154 nciv->itv = pnc->itv;
161 else if( pnc->itv.inf <= pciv->itv.sup )
163 if( pnc->itv.sup > pciv->itv.sup )
164 pciv->itv.sup = pnc->itv.sup;
177 nciv->itv = pnc->itv;
189 while( (pciv = apciv->next) !=
NULL )
191 if( apciv->itv.sup < (pciv->itv.inf - 1) )
193 pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
200 if( apciv->itv.sup < pciv->itv.sup )
201 apciv->itv.sup = pciv->itv.sup;
202 apciv->next = pciv->next;
210 pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
213 pgsd->lcitv = head.next;
253 int weightcurrentclique;
258 assert(getnnodes !=
NULL);
259 assert(getweights !=
NULL);
260 assert(selectadjnodes !=
NULL);
261 assert(buffer !=
NULL);
264 assert(clique !=
NULL);
265 assert(nclique !=
NULL);
266 assert(weightclique !=
NULL);
268 assert(iscolored !=
NULL);
270 weights = getweights(tcliquegraph);
271 assert(weights !=
NULL);
280 node = V[nodeVindex];
281 assert(0 <= node && node < getnnodes(tcliquegraph));
282 range = weights[node];
288 iscolored[nodeVindex] =
TRUE;
291 debugMessage(
"---------------coloring-----------------\n");
292 debugMessage(
"1. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d)\n",
293 nodeVindex, node, gsd[nodeVindex].satdeg, range);
296 apbound[nodeVindex] = range;
297 assert(apbound[nodeVindex] > 0);
300 maxsatdegree = range;
306 nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
307 for( i = 0, adjidx = 0; i < nV && adjidx < nVadj; ++i )
309 assert(V[i] <= Vadj[adjidx]);
310 if( V[i] == Vadj[adjidx] )
313 if( i == nodeVindex )
320 debugMessage(
" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ",
321 i, V[i], weights[V[i]], gsd[i].satdeg);
324 gsd[i].satdeg = range;
328 colorinterval->next =
NULL;
329 colorinterval->itv.inf = 1;
330 colorinterval->itv.sup = range;
333 gsd[i].lcitv = colorinterval;
338 debugPrintf(
"satdegnew=%d, nbc=[%d,%d]\n", gsd[i].satdeg, gsd[i].lcitv->itv.inf, gsd[i].lcitv->itv.sup);
347 currentclique[0] = node;
349 weightcurrentclique = range;
352 for( i = 0 ; i < nV-1; i++ )
354 assert((workclique == clique) != (currentclique == clique));
358 if( nodeVindex == -1 )
361 node = V[nodeVindex];
362 assert(0 <= node && node < getnnodes(tcliquegraph));
363 range = weights[node];
365 iscolored[nodeVindex] =
TRUE;
367 debugMessage(
"%d. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d, growclique=%u, weight=%d)\n",
368 i+2, nodeVindex, node, gsd[nodeVindex].satdeg, range, growclique, weightcurrentclique);
371 apbound[nodeVindex] = gsd[nodeVindex].satdeg + range;
372 assert(apbound[nodeVindex] > 0);
375 if( maxsatdegree < apbound[nodeVindex] )
376 maxsatdegree = apbound[nodeVindex];
379 if( gsd[nodeVindex].satdeg == 0 )
384 debugMessage(
"current node not adjacend to current clique (weight:%d) -> starting new clique\n",
385 weightcurrentclique);
388 if( weightcurrentclique > *weightclique )
393 assert((workclique == clique) != (currentclique == clique));
395 *weightclique = weightcurrentclique;
396 *nclique = ncurrentclique;
397 workclique = currentclique;
399 assert((workclique == clique) != (currentclique == clique));
401 weightcurrentclique = 0;
408 if( gsd[nodeVindex].satdeg == weightcurrentclique )
410 assert(ncurrentclique < nV);
411 currentclique[ncurrentclique] = node;
413 weightcurrentclique += range;
417 debugMessage(
"current clique (size:%d, weight:%d):", ncurrentclique, weightcurrentclique);
418 for( k = 0; k < ncurrentclique; ++k )
426 debugMessage(
"node satdeg: %d, clique weight: %d -> stop growing clique\n",
427 gsd[nodeVindex].satdeg, weightcurrentclique);
434 if( gsd[nodeVindex].lcitv ==
NULL )
438 colorinterval->next =
NULL;
439 colorinterval->itv.inf = 1;
440 colorinterval->itv.sup = range;
443 pnc->next = colorinterval;
452 lcitv = gsd[nodeVindex].lcitv;
455 if( lcitv->itv.inf != 1 )
458 dif = lcitv->itv.inf - 1 ;
463 colorinterval->next =
NULL;
464 colorinterval->itv.inf = 1;
465 colorinterval->itv.sup = dif;
468 pnc->next = colorinterval;
480 colorinterval->next =
NULL;
481 colorinterval->itv.inf = lcitv->itv.sup+1;
482 if( lcitv->next !=
NULL )
486 min = lcitv->next->itv.inf - lcitv->itv.sup - 1;
492 colorinterval->itv.sup = colorinterval->itv.inf + dif - 1;
495 pnc->next = colorinterval;
504 nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
505 for( j = 0, adjidx = 0; j < nV && adjidx < nVadj; ++j )
507 assert(V[j] <= Vadj[adjidx]);
508 if( V[j] == Vadj[adjidx] )
512 debugMessage(
" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ",
513 j, V[j], weights[V[j]], gsd[j].satdeg);
515 debugPrintf(
"satdegnew=%d, nbc=[%d,%d]\n", gsd[j].satdeg, gsd[j].lcitv->itv.inf, gsd[j].lcitv->itv.sup);
525 while( item !=
NULL )
527 tmpitem = item->next;
533 item = gsd[nodeVindex].lcitv;
534 while( item !=
NULL )
536 tmpitem = item->next;
541 assert((workclique == clique) != (currentclique == clique));
544 if( weightcurrentclique > *weightclique )
549 *weightclique = weightcurrentclique;
550 *nclique = ncurrentclique;
551 workclique = currentclique;
554 assert((workclique == clique) != (currentclique == clique));
557 if( workclique != clique )
559 assert(clique == currentclique);
560 assert(*nclique <= nV);
562 currentclique = workclique;
571 debugMessage(
"------------coloringend-----------------\n");
#define TCLIQUE_GETWEIGHTS(x)
struct BMS_ChkMem BMS_CHKMEM
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define BMSclearChunkMemory(mem)
#define TCLIQUE_SELECTADJNODES(x)
TCLIQUE_WEIGHT tcliqueColoring(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, BMS_CHKMEM *mem, int *buffer, int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, TCLIQUE_WEIGHT *apbound, int *clique, int *nclique, TCLIQUE_WEIGHT *weightclique)
#define BMSallocMemoryArray(ptr, num)
coloring part of algorithm for maximum cliques
#define BMSfreeMemoryArray(ptr)
static int getMaxWeightIndex(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_GRAPH *tcliquegraph, int *V, int nV)
static int getMaxSatdegIndex(int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, const TCLIQUE_WEIGHT *weights)
#define BMScopyMemoryArray(ptr, source, num)
static void updateNeighbor(BMS_CHKMEM *mem, NBC *pgsd, LIST_ITV *pnc)
#define TCLIQUE_GETNNODES(x)
#define BMSallocChunkMemory(mem, ptr)
#define BMSclearMemoryArray(ptr, num)
#define BMSfreeChunkMemory(mem, ptr)
struct _LIST_ITV LIST_ITV
memory allocation routines