61 assert(iscolored !=
NULL);
63 for( i = 0; i < nV; i++ )
72 weight = weights[V[i]];
75 satdeg = gsd[i].satdeg;
76 if( satdeg > maxsatdeg || (satdeg == maxsatdeg && weight > maxweight) )
84 return maxsatdegindex;
102 assert(getnnodes !=
NULL);
103 assert(getweights !=
NULL);
104 assert(tcliquegraph !=
NULL);
107 weights = getweights(tcliquegraph);
113 for( i = 0 ; i < nV; i++ )
115 assert(0 <= V[i] && V[i] < getnnodes(tcliquegraph));
116 assert(weights[V[i]] > 0);
117 if( weights[V[i]] > maxweight)
120 maxweight = weights[V[i]];
124 assert(maxweightindex >= 0);
126 return maxweightindex;
145 head.next = pgsd->lcitv;
150 while( (pnc !=
NULL) && (pciv !=
NULL) )
152 if( pnc->itv.inf < pciv->itv.inf )
155 nciv->itv = pnc->itv;
162 else if( pnc->itv.inf <= pciv->itv.sup )
164 if( pnc->itv.sup > pciv->itv.sup )
165 pciv->itv.sup = pnc->itv.sup;
178 nciv->itv = pnc->itv;
190 while( (pciv = apciv->next) !=
NULL )
192 if( apciv->itv.sup < (pciv->itv.inf - 1) )
194 pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
201 if( apciv->itv.sup < pciv->itv.sup )
202 apciv->itv.sup = pciv->itv.sup;
203 apciv->next = pciv->next;
211 pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
214 pgsd->lcitv = head.next;
254 int weightcurrentclique;
259 assert(getnnodes !=
NULL);
260 assert(getweights !=
NULL);
261 assert(selectadjnodes !=
NULL);
262 assert(buffer !=
NULL);
265 assert(clique !=
NULL);
266 assert(nclique !=
NULL);
267 assert(weightclique !=
NULL);
269 assert(iscolored !=
NULL);
271 weights = getweights(tcliquegraph);
272 assert(weights !=
NULL);
281 node = V[nodeVindex];
282 assert(0 <= node && node < getnnodes(tcliquegraph));
283 range = weights[node];
289 iscolored[nodeVindex] =
TRUE;
292 debugMessage(
"---------------coloring-----------------\n");
293 debugMessage(
"1. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d)\n",
294 nodeVindex, node, gsd[nodeVindex].satdeg, range);
297 apbound[nodeVindex] = range;
298 assert(apbound[nodeVindex] > 0);
301 maxsatdegree = range;
307 nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
308 for( i = 0, adjidx = 0; i < nV && adjidx < nVadj; ++i )
310 assert(V[i] <= Vadj[adjidx]);
311 if( V[i] == Vadj[adjidx] )
314 if( i == nodeVindex )
321 debugMessage(
" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ",
322 i, V[i], weights[V[i]], gsd[i].satdeg);
325 gsd[i].satdeg = range;
329 colorinterval->next =
NULL;
330 colorinterval->itv.inf = 1;
331 colorinterval->itv.sup = range;
334 gsd[i].lcitv = colorinterval;
339 debugPrintf(
"satdegnew=%d, nbc=[%d,%d]\n", gsd[i].satdeg, gsd[i].lcitv->itv.inf, gsd[i].lcitv->itv.sup);
348 currentclique[0] = node;
350 weightcurrentclique = range;
353 for( i = 0 ; i < nV-1; i++ )
355 assert((workclique == clique) != (currentclique == clique));
359 if( nodeVindex == -1 )
362 node = V[nodeVindex];
363 assert(0 <= node && node < getnnodes(tcliquegraph));
364 range = weights[node];
366 iscolored[nodeVindex] =
TRUE;
368 debugMessage(
"%d. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d, growclique=%u, weight=%d)\n",
369 i+2, nodeVindex, node, gsd[nodeVindex].satdeg, range, growclique, weightcurrentclique);
372 apbound[nodeVindex] = gsd[nodeVindex].satdeg + range;
373 assert(apbound[nodeVindex] > 0);
376 if( maxsatdegree < apbound[nodeVindex] )
377 maxsatdegree = apbound[nodeVindex];
380 if( gsd[nodeVindex].satdeg == 0 )
385 debugMessage(
"current node not adjacend to current clique (weight:%d) -> starting new clique\n",
386 weightcurrentclique);
389 if( weightcurrentclique > *weightclique )
394 assert((workclique == clique) != (currentclique == clique));
396 *weightclique = weightcurrentclique;
397 *nclique = ncurrentclique;
398 workclique = currentclique;
400 assert((workclique == clique) != (currentclique == clique));
402 weightcurrentclique = 0;
409 if( gsd[nodeVindex].satdeg == weightcurrentclique )
411 assert(ncurrentclique < nV);
412 currentclique[ncurrentclique] = node;
414 weightcurrentclique += range;
418 debugMessage(
"current clique (size:%d, weight:%d):", ncurrentclique, weightcurrentclique);
419 for( k = 0; k < ncurrentclique; ++k )
427 debugMessage(
"node satdeg: %d, clique weight: %d -> stop growing clique\n",
428 gsd[nodeVindex].satdeg, weightcurrentclique);
435 if( gsd[nodeVindex].lcitv ==
NULL )
439 colorinterval->next =
NULL;
440 colorinterval->itv.inf = 1;
441 colorinterval->itv.sup = range;
444 pnc->next = colorinterval;
453 lcitv = gsd[nodeVindex].lcitv;
456 if( lcitv->itv.inf != 1 )
459 dif = lcitv->itv.inf - 1 ;
464 colorinterval->next =
NULL;
465 colorinterval->itv.inf = 1;
466 colorinterval->itv.sup = dif;
469 pnc->next = colorinterval;
481 colorinterval->next =
NULL;
482 colorinterval->itv.inf = lcitv->itv.sup+1;
483 if( lcitv->next !=
NULL )
487 min = lcitv->next->itv.inf - lcitv->itv.sup - 1;
493 colorinterval->itv.sup = colorinterval->itv.inf + dif - 1;
496 pnc->next = colorinterval;
505 nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
506 for( j = 0, adjidx = 0; j < nV && adjidx < nVadj; ++j )
508 assert(V[j] <= Vadj[adjidx]);
509 if( V[j] == Vadj[adjidx] )
513 debugMessage(
" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ",
514 j, V[j], weights[V[j]], gsd[j].satdeg);
516 debugPrintf(
"satdegnew=%d, nbc=[%d,%d]\n", gsd[j].satdeg, gsd[j].lcitv->itv.inf, gsd[j].lcitv->itv.sup);
526 while( item !=
NULL )
528 tmpitem = item->next;
534 item = gsd[nodeVindex].lcitv;
535 while( item !=
NULL )
537 tmpitem = item->next;
542 assert((workclique == clique) != (currentclique == clique));
545 if( weightcurrentclique > *weightclique )
550 *weightclique = weightcurrentclique;
551 *nclique = ncurrentclique;
552 workclique = currentclique;
555 assert((workclique == clique) != (currentclique == clique));
558 if( workclique != clique )
560 assert(clique == currentclique);
561 assert(*nclique <= nV);
563 currentclique = workclique;
572 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