70 assert(iscolored !=
NULL);
72 for( i = 0; i < nV; i++ )
81 weight = weights[V[i]];
84 satdeg = gsd[i].satdeg;
85 if( satdeg > maxsatdeg || (satdeg == maxsatdeg && weight > maxweight) )
93 return maxsatdegindex;
111 assert(getnnodes !=
NULL);
112 assert(getweights !=
NULL);
113 assert(tcliquegraph !=
NULL);
116 weights = getweights(tcliquegraph);
122 for( i = 0 ; i < nV; i++ )
124 assert(0 <= V[i] && V[i] < getnnodes(tcliquegraph));
125 assert(weights[V[i]] > 0);
126 if( weights[V[i]] > maxweight)
129 maxweight = weights[V[i]];
133 assert(maxweightindex >= 0);
135 return maxweightindex;
154 head.next = pgsd->lcitv;
159 while( (pnc !=
NULL) && (pciv !=
NULL) )
161 if( pnc->itv.inf < pciv->itv.inf )
164 nciv->itv = pnc->itv;
171 else if( pnc->itv.inf <= pciv->itv.sup )
173 if( pnc->itv.sup > pciv->itv.sup )
174 pciv->itv.sup = pnc->itv.sup;
187 nciv->itv = pnc->itv;
199 while( (pciv = apciv->next) !=
NULL )
201 if( apciv->itv.sup < (pciv->itv.inf - 1) )
203 pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
210 if( apciv->itv.sup < pciv->itv.sup )
211 apciv->itv.sup = pciv->itv.sup;
212 apciv->next = pciv->next;
221 pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
224 pgsd->lcitv = head.next;
264 int weightcurrentclique;
269 assert(getnnodes !=
NULL);
270 assert(getweights !=
NULL);
271 assert(selectadjnodes !=
NULL);
272 assert(buffer !=
NULL);
275 assert(clique !=
NULL);
276 assert(nclique !=
NULL);
277 assert(weightclique !=
NULL);
279 assert(iscolored !=
NULL);
281 weights = getweights(tcliquegraph);
282 assert(weights !=
NULL);
291 node = V[nodeVindex];
292 assert(0 <= node && node < getnnodes(tcliquegraph));
293 range = weights[node];
299 iscolored[nodeVindex] =
TRUE;
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);
307 apbound[nodeVindex] = range;
308 assert(apbound[nodeVindex] > 0);
311 maxsatdegree = range;
317 nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
318 for( i = 0, adjidx = 0; i < nV && adjidx < nVadj; ++i )
320 assert(V[i] <= Vadj[adjidx]);
321 if( V[i] == Vadj[adjidx] )
324 if( i == nodeVindex )
331 debugMessage(
" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ",
332 i, V[i], weights[V[i]], gsd[i].satdeg);
335 gsd[i].satdeg = range;
339 colorinterval->next =
NULL;
340 colorinterval->itv.inf = 1;
341 colorinterval->itv.sup = range;
344 gsd[i].lcitv = colorinterval;
349 debugPrintf(
"satdegnew=%d, nbc=[%d,%d]\n", gsd[i].satdeg, gsd[i].lcitv->itv.inf, gsd[i].lcitv->itv.sup);
358 currentclique[0] = node;
360 weightcurrentclique = range;
363 for( i = 0 ; i < nV-1; i++ )
365 assert((workclique == clique) != (currentclique == clique));
369 if( nodeVindex == -1 )
372 node = V[nodeVindex];
373 assert(0 <= node && node < getnnodes(tcliquegraph));
374 range = weights[node];
376 iscolored[nodeVindex] =
TRUE;
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);
382 apbound[nodeVindex] = gsd[nodeVindex].satdeg + range;
383 assert(apbound[nodeVindex] > 0);
386 if( maxsatdegree < apbound[nodeVindex] )
387 maxsatdegree = apbound[nodeVindex];
390 if( gsd[nodeVindex].satdeg == 0 )
395 debugMessage(
"current node not adjacend to current clique (weight:%d) -> starting new clique\n",
396 weightcurrentclique);
399 if( weightcurrentclique > *weightclique )
404 assert((workclique == clique) != (currentclique == clique));
406 *weightclique = weightcurrentclique;
407 *nclique = ncurrentclique;
408 workclique = currentclique;
410 assert((workclique == clique) != (currentclique == clique));
412 weightcurrentclique = 0;
419 if( gsd[nodeVindex].satdeg == weightcurrentclique )
421 assert(ncurrentclique < nV);
422 currentclique[ncurrentclique] = node;
424 weightcurrentclique += range;
428 debugMessage(
"current clique (size:%d, weight:%d):", ncurrentclique, weightcurrentclique);
429 for( k = 0; k < ncurrentclique; ++k )
437 debugMessage(
"node satdeg: %d, clique weight: %d -> stop growing clique\n",
438 gsd[nodeVindex].satdeg, weightcurrentclique);
445 if( gsd[nodeVindex].lcitv ==
NULL )
449 colorinterval->next =
NULL;
450 colorinterval->itv.inf = 1;
451 colorinterval->itv.sup = range;
454 pnc->next = colorinterval;
463 lcitv = gsd[nodeVindex].lcitv;
466 if( lcitv->itv.inf != 1 )
469 dif = lcitv->itv.inf - 1 ;
474 colorinterval->next =
NULL;
475 colorinterval->itv.inf = 1;
476 colorinterval->itv.sup = dif;
479 pnc->next = colorinterval;
491 colorinterval->next =
NULL;
492 colorinterval->itv.inf = lcitv->itv.sup+1;
493 if( lcitv->next !=
NULL )
497 min = lcitv->next->itv.inf - lcitv->itv.sup - 1;
503 colorinterval->itv.sup = colorinterval->itv.inf + dif - 1;
506 pnc->next = colorinterval;
515 nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
516 for( j = 0, adjidx = 0; j < nV && adjidx < nVadj; ++j )
518 assert(V[j] <= Vadj[adjidx]);
519 if( V[j] == Vadj[adjidx] )
523 debugMessage(
" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ",
524 j, V[j], weights[V[j]], gsd[j].satdeg);
526 debugPrintf(
"satdegnew=%d, nbc=[%d,%d]\n", gsd[j].satdeg, gsd[j].lcitv->itv.inf, gsd[j].lcitv->itv.sup);
536 while( item !=
NULL )
538 tmpitem = item->next;
545 item = gsd[nodeVindex].lcitv;
546 while( item !=
NULL )
548 tmpitem = item->next;
554 assert((workclique == clique) != (currentclique == clique));
557 if( weightcurrentclique > *weightclique )
562 *weightclique = weightcurrentclique;
563 *nclique = ncurrentclique;
564 workclique = currentclique;
567 assert((workclique == clique) != (currentclique == clique));
570 if( workclique != clique )
572 assert(clique == currentclique);
573 assert(*nclique <= nV);
575 currentclique = workclique;
584 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