48#define CHUNK_SIZE (64)
49#define CLIQUEHASH_INITSIZE (1024)
100 for(
j =
i;
j > 0 && node < (*clique)->nodes[
j-1]; --
j )
101 (*clique)->nodes[
j] = (*clique)->nodes[
j-1];
102 (*clique)->nodes[
j] = node;
104 (*clique)->nnodes =
nnodes;
184 for(
i = 0;
i < cliquehash->ncliques-1; ++
i )
188#define checkCliquehash(cliquehash)
204 (*cliquehash)->ncliques = 0;
218 for(
i = 0;
i < cliquehash->ncliques; ++
i )
221 cliquehash->ncliques = 0;
250 if( num > cliquehash->cliquessize )
254 newsize = 2*cliquehash->cliquessize;
259 cliquehash->cliquessize =
newsize;
261 assert(cliquehash->cliquessize >= num);
275 debugMessage(
"cliquehash (%d cliques):\n", cliquehash->ncliques);
276 for(
i = 0;
i < cliquehash->ncliques; ++
i )
281 for(
j = 0;
j < cliquehash->cliques[
i]->nnodes; ++
j )
302 assert(cliquehash->cliquessize > 0);
308 right = cliquehash->ncliques-1;
309 while( left <= right )
356 cliquehash->cliques[
i] = cliquehash->cliques[
i-1];
358 cliquehash->ncliques++;
419 (*ncurcliquenodes)++;
476 if( cliquehash->ncliques > 0 )
506 assert(cliquehash->ncliques == 0);
577 if(
nV >= 2 &&
isedge(tcliquegraph,
V[0],
V[1]) )
588 else if(
nV >= 2 && weights[
V[1]] > weights[
V[0]] )
663 for(
i = 0 ;
i <
nV;
i++ )
699 for(
i = 0 ;
i <
nV;
i++ )
791 for(
i = 0;
i < level; ++
i )
795 for(
i = 0;
i <
nV; ++
i )
820 for(
i = 0;
i <
nV; ++
i )
836 for(
i = 0;
i < level; ++
i )
844 debugMessage(
" -> new current clique with weight %d at node %d in level %d:",
875 debugMessage(
"============================ branching level %d ===============================\n", level);
883 if( level > 1 && backtrackfreq > 0 && (*
ntreenodes) % backtrackfreq == 0 )
912 debugMessage(
"%d. branching in level %d (treenode %d): bidx=%d, node %d, weight %d, upperbound: %d+%d = %d, maxclique=%d\n",
943 mem, cliquehash, buffer,
963 debugMessage(
"========================== branching level %d end =============================\n\n", level);
986 debugMessage(
" -> solving terminated by callback method\n");
1056 assert(backtrackfreq >= 0);
1105 if( weights[
i] == 0 )
1122 cliquehash, buffer, 0,
V,
nV,
Vzero,
nVzero,
gsd,
iscolored,
K, 0,
#define SCIP_LONGINT_FORMAT
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
#define BMSfreeMemory(ptr)
#define BMSreallocMemoryArray(ptr, num)
#define BMSgetChunkMemoryUsed(mem)
struct BMS_ChkMem BMS_CHKMEM
#define BMSgetMemoryUsed()
#define BMSallocMemoryArray(ptr, num)
#define BMSfreeMemoryArray(ptr)
#define BMScopyMemoryArray(ptr, source, num)
#define BMSdestroyChunkMemory(mem)
#define BMScreateChunkMemory(sz, isz, gbf)
#define BMSclearMemoryArray(ptr, num)
#define BMSallocMemory(ptr)
#define TCLIQUE_GETWEIGHTS(x)
#define TCLIQUE_GETNNODES(x)
#define TCLIQUE_ISEDGE(x)
#define TCLIQUE_SELECTADJNODES(x)
enum TCLIQUE_Status TCLIQUE_STATUS
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define TCLIQUE_NEWSOL(x)
static void clearCliquehash(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)
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)
static void freeClique(CLIQUE **clique)
static void extendCliqueZeroWeight(TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int *ncurcliquenodes)
static TCLIQUE_Bool inCliquehash(CLIQUEHASH *cliquehash, CLIQUE *clique, int *insertpos)
#define CLIQUEHASH_INITSIZE
struct cliquehash CLIQUEHASH
static void ensureCliquehashSize(CLIQUEHASH *cliquehash, int num)
static void checkCliquehash(CLIQUEHASH *cliquehash)
static void createClique(CLIQUE **clique, int *nodes, int nnodes)
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 void insertClique(CLIQUEHASH *cliquehash, CLIQUE *clique, int insertpos)
static int getMaxApBoundIndexNotMaxWeight(int *V, int nV, const TCLIQUE_WEIGHT *apbound, const TCLIQUE_WEIGHT *weights, TCLIQUE_WEIGHT maxweight)
static void freeCliquehash(CLIQUEHASH **cliquehash)
static int compSubcliques(CLIQUE *clique1, CLIQUE *clique2)
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 int getMaxApBoundIndex(int nV, TCLIQUE_WEIGHT *apbound)
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)
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)
coloring part of algorithm for maximum cliques
struct _LIST_ITV LIST_ITV