38 #define CHUNK_SIZE (64) 39 #define CLIQUEHASH_INITSIZE (1024) 78 assert(clique !=
NULL);
84 for( i = 0; i <
nnodes; ++i )
90 for( j = i; j > 0 && node < (*clique)->nodes[j-1]; --j )
91 (*clique)->nodes[j] = (*clique)->nodes[j-1];
92 (*clique)->nodes[j] = node;
94 (*clique)->nnodes =
nnodes;
103 assert(clique !=
NULL);
104 assert(*clique !=
NULL);
125 assert(clique1 !=
NULL);
126 assert(clique2 !=
NULL);
130 clique2smaller =
FALSE;
131 while( pos1 < clique1->
nnodes && pos2 < clique2->
nnodes )
133 if( clique1->nodes[pos1] < clique2->nodes[pos2] )
138 return (clique2smaller ? +1 : -1);
140 else if( clique1->nodes[pos1] > clique2->nodes[pos2] )
146 clique2smaller =
TRUE;
156 if( pos1 < clique1->nnodes )
157 return (clique2smaller ? +1 : -1);
172 assert(cliquehash !=
NULL);
174 for( i = 0; i < cliquehash->ncliques-1; ++i )
175 assert(
compSubcliques(cliquehash->cliques[i], cliquehash->cliques[i+1]) < 0);
178 #define checkCliquehash(cliquehash) 188 assert(cliquehash !=
NULL);
189 assert(tablesize > 0);
193 (*cliquehash)->cliquessize = tablesize;
194 (*cliquehash)->ncliques = 0;
205 assert(cliquehash !=
NULL);
208 for( i = 0; i < cliquehash->ncliques; ++i )
211 cliquehash->ncliques = 0;
220 assert(cliquehash !=
NULL);
221 assert(*cliquehash !=
NULL);
238 assert(cliquehash !=
NULL);
240 if( num > cliquehash->cliquessize )
244 newsize = 2*cliquehash->cliquessize;
249 cliquehash->cliquessize = newsize;
251 assert(cliquehash->cliquessize >= num);
257 void printCliquehash(
263 assert(cliquehash !=
NULL);
265 debugMessage(
"cliquehash (%d cliques):\n", cliquehash->ncliques);
266 for( i = 0; i < cliquehash->ncliques; ++i )
271 for( j = 0; j < cliquehash->cliques[i]->nnodes; ++j )
272 debugPrintf(
" %d", cliquehash->cliques[i]->nodes[j]);
291 assert(cliquehash !=
NULL);
292 assert(cliquehash->cliquessize > 0);
293 assert(clique !=
NULL);
294 assert(insertpos !=
NULL);
298 right = cliquehash->ncliques-1;
299 while( left <= right )
301 middle = (left+right)/2;
316 for( middle = left-1; middle >= 0; --middle )
337 assert(cliquehash !=
NULL);
338 assert(clique !=
NULL);
339 assert(0 <= insertpos && insertpos <= cliquehash->ncliques);
345 for( i = cliquehash->ncliques; i > insertpos; --i )
346 cliquehash->cliques[i] = cliquehash->cliques[i-1];
347 cliquehash->cliques[insertpos] = clique;
348 cliquehash->ncliques++;
353 debug(printCliquehash(cliquehash));
371 int maxnzeroextensions,
381 assert(selectadjnodes !=
NULL);
382 assert(buffer !=
NULL);
383 assert(Vzero !=
NULL);
384 assert(curcliquenodes !=
NULL);
385 assert(ncurcliquenodes !=
NULL);
387 debugMessage(
"extending temporary clique (size %d) with zero-weighted nodes (nVzero=%d)\n", *ncurcliquenodes, nVzero);
389 if( maxnzeroextensions == 0 )
398 for( i = 0; i < *ncurcliquenodes && nzerocands > 0; ++i )
400 nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[i], zerocands, nzerocands, zerocands);
405 while( nzerocands > 0 )
408 curcliquenodes[*ncurcliquenodes] = zerocands[0];
409 (*ncurcliquenodes)++;
413 if( nzeroextensions >= maxnzeroextensions )
417 nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[(*ncurcliquenodes)-1], zerocands, nzerocands, zerocands);
436 int maxnzeroextensions,
441 int* nmaxcliquenodes,
450 assert(curcliquenodes !=
NULL);
451 assert(maxcliquenodes !=
NULL);
452 assert(nmaxcliquenodes !=
NULL);
453 assert(maxcliqueweight !=
NULL);
454 assert(curcliqueweight > *maxcliqueweight);
455 assert(stopsolving !=
NULL);
456 assert(newsol ==
NULL || cliquehash !=
NULL);
459 *stopsolving =
FALSE;
466 if( cliquehash->ncliques > 0 )
469 acceptsol = !
inCliquehash(cliquehash, clique, &insertpos);
478 curcliquenodes, &ncurcliquenodes);
483 newsol(tcliquedata, curcliquenodes, ncurcliquenodes, curcliqueweight, maxcliqueweight, &acceptsol, stopsolving);
495 assert(insertpos == 0);
496 assert(cliquehash->ncliques == 0);
515 *nmaxcliquenodes = ncurcliquenodes;
516 if( curcliqueweight > *maxcliqueweight )
517 *maxcliqueweight = curcliqueweight;
521 debugMessage(
" -> clique %s (weight %d):", acceptsol ?
"accepted" :
"rejected", curcliqueweight);
524 for( i = 0; i < ncurcliquenodes; ++i )
541 int* ntmpcliquenodes,
547 assert(getweights !=
NULL);
548 assert(isedge !=
NULL);
549 assert(tcliquegraph !=
NULL);
551 assert(0 <= nV && nV <= 2);
552 assert(apbound !=
NULL);
553 assert(tmpcliquenodes !=
NULL);
554 assert(ntmpcliquenodes !=
NULL);
555 assert(tmpcliqueweight !=
NULL);
557 weights = getweights(tcliquegraph);
558 assert(nV == 0 || weights[V[0]] > 0);
559 assert(nV <= 1 || weights[V[1]] > 0);
562 apbound[0] = weights[V[0]];
564 apbound[1] = weights[V[1]];
567 if( nV >= 2 && isedge(tcliquegraph, V[0], V[1]) )
569 assert(isedge(tcliquegraph, V[1], V[0]));
572 tmpcliquenodes[0] = V[0];
573 tmpcliquenodes[1] = V[1];
574 *ntmpcliquenodes = 2;
575 *tmpcliqueweight = weights[V[0]] + weights[V[1]];
576 apbound[0] += weights[V[1]];
578 else if( nV >= 2 && weights[V[1]] > weights[V[0]] )
581 tmpcliquenodes[0] = V[1];
582 *ntmpcliquenodes = 1;
583 *tmpcliqueweight = weights[V[1]];
588 tmpcliquenodes[0] = V[0];
589 *ntmpcliquenodes = 1;
590 *tmpcliqueweight = weights[V[0]];
594 *tmpcliqueweight = 0;
595 *ntmpcliquenodes = 0;
615 int* ntmpcliquenodes,
619 assert(tmpcliqueweight !=
NULL);
625 reduced(getweights, isedge, tcliquegraph, V, nV, apbound, tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
626 return *tmpcliqueweight;
631 return tcliqueColoring(getnnodes, getweights, selectadjnodes, tcliquegraph,
632 mem, buffer, V, nV, gsd, iscolored, apbound,
633 tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
648 assert(apbound !=
NULL);
653 for( i = 0 ; i < nV; i++ )
655 assert(apbound[i] > 0);
656 if( apbound[i] >= maxapbound )
658 maxapbound = apbound[i];
684 assert(apbound !=
NULL);
689 for( i = 0 ; i < nV; i++ )
691 assert(apbound[i] > 0);
692 assert(weights[V[i]] > 0);
694 if( apbound[i] >= maxapbound && weights[V[i]] <= maxweight )
696 maxapbound = apbound[i];
729 int* nmaxcliquenodes,
732 int* ncurcliquenodes,
740 int maxnzeroextensions,
755 assert(getnnodes !=
NULL);
756 assert(getweights !=
NULL);
757 assert(selectadjnodes !=
NULL);
761 assert(iscolored !=
NULL);
763 assert(maxcliqueweight !=
NULL);
764 assert(curcliquenodes !=
NULL);
765 assert(ncurcliquenodes !=
NULL);
766 assert(curcliqueweight !=
NULL);
767 assert(ntreenodes !=
NULL);
768 assert(maxfirstnodeweight >= 0);
769 assert(*ntreenodes >= 0);
770 assert(maxntreenodes >= 0);
771 assert(status !=
NULL);
776 debugMessage(
"(level %d, treenode %d) maxclique = %d, curclique = %d [mem=%" SCIP_LONGINT_FORMAT
" (%" SCIP_LONGINT_FORMAT
"), cliques=%d]\n",
777 level, *ntreenodes, *maxcliqueweight, *curcliqueweight,
780 debugMessage(
" -> current branching (weight %d):", weightK);
781 for( i = 0; i < level; ++i )
785 for( i = 0; i < nV; ++i )
789 if( *ntreenodes > maxntreenodes )
795 weights = getweights(tcliquegraph);
796 backtracklevel = INT_MAX;
804 subgraphweight =
boundSubgraph(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph,
805 mem, buffer, V, nV, gsd, iscolored, apbound,
806 tmpcliquenodes, &ntmpcliquenodes, &tmpcliqueweight);
810 for( i = 0; i < nV; ++i )
812 assert(0 <= V[i] && V[i] < getnnodes(tcliquegraph));
813 assert(i == 0 || V[i-1] < V[i]);
814 assert(apbound[i] >= 0);
815 assert((apbound[i] == 0) == (weights[V[i]] == 0));
823 if( weightK + tmpcliqueweight > *curcliqueweight && (level > 0 || fixednode == -1) )
826 for( i = 0; i < level; ++i )
827 curcliquenodes[i] = K[i];
828 for( i = 0; i < ntmpcliquenodes; ++i )
829 curcliquenodes[level+i] = tmpcliquenodes[i];
830 *ncurcliquenodes = level + ntmpcliquenodes;
831 *curcliqueweight = weightK + tmpcliqueweight;
834 debugMessage(
" -> new current clique with weight %d at node %d in level %d:",
835 *curcliqueweight, *ntreenodes, level);
836 for( i = 0; i < *ncurcliquenodes; ++i )
847 if( weightK + subgraphweight > *maxcliqueweight && (nV > 2 || (fixednode >= 0 && level == 0)) )
863 weightKold = weightK;
865 debugMessage(
"============================ branching level %d ===============================\n", level);
868 while( backtracklevel >= level && nValive > 0 )
873 if( level > 1 && backtrackfreq > 0 && (*ntreenodes) % backtrackfreq == 0 )
880 if( level == 1 && fixednode >= 0 )
883 for( branchidx = 0; branchidx < nValive && V[branchidx] != fixednode; branchidx++ )
885 assert(branchidx < nValive);
886 assert(V[branchidx] == fixednode);
888 else if( level == 1 && maxfirstnodeweight > 0 )
894 assert(0 <= branchidx && branchidx < nValive && nValive <= nV);
895 assert(apbound[branchidx] > 0);
896 assert(weights[V[branchidx]] > 0);
899 if( (weightKold + apbound[branchidx]) <= *maxcliqueweight )
902 debugMessage(
"%d. branching in level %d (treenode %d): bidx=%d, node %d, weight %d, upperbound: %d+%d = %d, maxclique=%d\n",
903 nV-nValive+1, level, *ntreenodes, branchidx, V[branchidx], weights[V[branchidx]], weightKold,
904 apbound[branchidx], weightKold + apbound[branchidx], *maxcliqueweight);
912 branchingnode = V[branchidx];
913 K[level-1] = branchingnode;
914 weightK = weightKold + weights[branchingnode];
920 for( i = branchidx; i < nValive; ++i )
923 apbound[i] = apbound[i+1];
929 nVcurrent = selectadjnodes(tcliquegraph, branchingnode, V, nValive, Vcurrent);
932 backtracklevel =
branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata,
933 mem, cliquehash, buffer,
934 level, Vcurrent, nVcurrent, Vzero, nVzero, gsd, iscolored, K, weightK,
935 maxcliquenodes, nmaxcliquenodes, maxcliqueweight,
936 curcliquenodes, ncurcliquenodes, curcliqueweight, tmpcliquenodes,
937 maxfirstnodeweight, ntreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, -1, status);
942 if( nVcurrent == nValive )
944 debugMessage(
"branching on node %d was optimal - ignoring remaining candidates\n", branchingnode);
953 debugMessage(
"========================== branching level %d end =============================\n\n", level);
965 if( *curcliqueweight > *maxcliqueweight )
969 debugMessage(
"found clique of weight %d at node %d in level %d\n", *curcliqueweight, *ntreenodes, level);
970 newSolution(selectadjnodes, tcliquegraph, newsol, tcliquedata, cliquehash, buffer, Vzero, nVzero,
971 maxnzeroextensions, curcliquenodes, *ncurcliquenodes, *curcliqueweight,
972 maxcliquenodes, nmaxcliquenodes, maxcliqueweight, &stopsolving);
976 debugMessage(
" -> solving terminated by callback method\n");
982 *ncurcliquenodes = 0;
983 *curcliqueweight = 0;
987 if( level > backtracklevel )
989 debugMessage(
"premature backtracking after %d nodes - level %d\n", *ntreenodes, level);
996 return backtracklevel;
1008 int* maxcliquenodes,
1009 int* nmaxcliquenodes,
1016 int maxnzeroextensions,
1035 int* curcliquenodes;
1036 int ncurcliquenodes;
1038 int* tmpcliquenodes;
1042 assert(maxcliquenodes !=
NULL);
1043 assert(nmaxcliquenodes !=
NULL);
1044 assert(maxcliqueweight !=
NULL);
1045 assert(maxntreenodes >= 0);
1046 assert(backtrackfreq >= 0);
1047 assert(maxnzeroextensions >= 0);
1048 assert(status !=
NULL);
1053 if( getnnodes ==
NULL )
1054 getnnodes = tcliqueGetNNodes;
1055 if( getweights ==
NULL )
1056 getweights = tcliqueGetWeights;
1057 if( isedge ==
NULL )
1058 isedge = tcliqueIsEdge;
1059 if( selectadjnodes ==
NULL )
1060 selectadjnodes = tcliqueSelectAdjnodes;
1063 nnodes = getnnodes(tcliquegraph);
1065 debugMessage(
"calculating maximal weighted clique in graph (%d nodes)\n", nnodes);
1068 if( newsol !=
NULL )
1082 *nmaxcliquenodes = 0;
1083 *maxcliqueweight = minweight-1;
1084 ncurcliquenodes = 0;
1085 curcliqueweight = 0;
1089 weights = getweights(tcliquegraph);
1090 assert(weights !=
NULL);
1093 for( i = 0 ; i <
nnodes; i++ )
1095 if( weights[i] == 0 )
1111 backtracklevel =
branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata, mem,
1112 cliquehash, buffer, 0, V, nV, Vzero, nVzero, gsd, iscolored, K, 0,
1113 maxcliquenodes, nmaxcliquenodes, maxcliqueweight,
1114 curcliquenodes, &ncurcliquenodes, &curcliqueweight, tmpcliquenodes,
1115 maxfirstnodeweight, &nbbtreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, fixednode, status);
1117 if ( ntreenodes !=
NULL )
1118 *ntreenodes = nbbtreenodes;
1135 if( newsol !=
NULL )
#define TCLIQUE_GETWEIGHTS(x)
static void checkCliquehash(CLIQUEHASH *cliquehash)
static void newSolution(TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, CLIQUEHASH *cliquehash, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int ncurcliquenodes, TCLIQUE_WEIGHT curcliqueweight, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_Bool *stopsolving)
enum TCLIQUE_Status TCLIQUE_STATUS
struct cliquehash CLIQUEHASH
struct BMS_ChkMem BMS_CHKMEM
struct TCLIQUE_Graph TCLIQUE_GRAPH
static void clearCliquehash(CLIQUEHASH *cliquehash)
static void freeCliquehash(CLIQUEHASH **cliquehash)
static void freeClique(CLIQUE **clique)
#define TCLIQUE_SELECTADJNODES(x)
static void extendCliqueZeroWeight(TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int *ncurcliquenodes)
static int getMaxApBoundIndexNotMaxWeight(int *V, int nV, const TCLIQUE_WEIGHT *apbound, const TCLIQUE_WEIGHT *weights, TCLIQUE_WEIGHT maxweight)
#define CLIQUEHASH_INITSIZE
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)
static TCLIQUE_WEIGHT boundSubgraph(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, BMS_CHKMEM *mem, int *buffer, int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, TCLIQUE_WEIGHT *apbound, int *tmpcliquenodes, int *ntmpcliquenodes, TCLIQUE_WEIGHT *tmpcliqueweight)
static void ensureCliquehashSize(CLIQUEHASH *cliquehash, int num)
static void insertClique(CLIQUEHASH *cliquehash, CLIQUE *clique, int insertpos)
#define BMSallocMemoryArray(ptr, num)
#define BMSgetChunkMemoryUsed(mem)
#define BMSfreeMemory(ptr)
coloring part of algorithm for maximum cliques
#define BMSfreeMemoryArray(ptr)
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
static TCLIQUE_Bool inCliquehash(CLIQUEHASH *cliquehash, CLIQUE *clique, int *insertpos)
#define TCLIQUE_ISEDGE(x)
#define BMScopyMemoryArray(ptr, source, num)
#define BMScreateChunkMemory(sz, isz, gbf)
static void createCliquehash(CLIQUEHASH **cliquehash, int tablesize)
static void reduced(TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_GRAPH *tcliquegraph, int *V, int nV, TCLIQUE_WEIGHT *apbound, int *tmpcliquenodes, int *ntmpcliquenodes, TCLIQUE_WEIGHT *tmpcliqueweight)
static int compSubcliques(CLIQUE *clique1, CLIQUE *clique2)
#define BMSallocMemory(ptr)
#define BMSreallocMemoryArray(ptr, num)
static int getMaxApBoundIndex(int nV, TCLIQUE_WEIGHT *apbound)
#define TCLIQUE_GETNNODES(x)
static int branch(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, BMS_CHKMEM *mem, CLIQUEHASH *cliquehash, int *buffer, int level, int *V, int nV, int *Vzero, int nVzero, NBC *gsd, TCLIQUE_Bool *iscolored, int *K, TCLIQUE_WEIGHT weightK, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, int *curcliquenodes, int *ncurcliquenodes, TCLIQUE_WEIGHT *curcliqueweight, int *tmpcliquenodes, TCLIQUE_WEIGHT maxfirstnodeweight, int *ntreenodes, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, TCLIQUE_STATUS *status)
#define BMSgetMemoryUsed()
#define BMSclearMemoryArray(ptr, num)
static void createClique(CLIQUE **clique, int *nodes, int nnodes)
#define BMSdestroyChunkMemory(mem)
struct _LIST_ITV LIST_ITV
#define TCLIQUE_NEWSOL(x)
memory allocation routines