Scippy

SCIP

Solving Constraint Integer Programs

tclique_branch.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* TCLIQUE --- Algorithm for Maximum Cliques */
5 /* */
6 /* Copyright (C) 1996-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* TCLIQUE is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with TCLIQUE; see the file COPYING. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file tclique_branch.c
17  * @ingroup OTHER_CFILES
18  * @brief branch and bound part of algorithm for maximum cliques
19  * @author Tobias Achterberg
20  * @author Ralf Borndoerfer
21  * @author Zoltan Kormos
22  * @author Kati Wolter
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #include <stdio.h>
28 #include <assert.h>
29 #include <stdlib.h>
30 #include <limits.h>
31 
32 #include "tclique/tclique.h"
33 #include "tclique/tclique_def.h"
35 #include "blockmemshell/memory.h"
36 
37 
38 
39 #define CHUNK_SIZE (64)
40 #define CLIQUEHASH_INITSIZE (1024)
41 
42 
43 
44 
45 /***************************
46  * clique hash table methods
47  ***************************/
48 
49 typedef struct clique CLIQUE; /**< single element of the clique hash table */
50 
51 /** single element of the clique hash table */
52 struct clique
53 {
54  int* nodes; /**< node number of the clique elements */
55  int nnodes; /**< length of the clique */
56 };
57 
58 typedef struct cliquehash CLIQUEHASH; /**< hash table for storing cliques */
59 
60 /** hash table for storing cliques */
61 struct cliquehash
62 {
63  CLIQUE** cliques; /**< elements of the table */
64  int cliquessize; /**< size of the table */
65  int ncliques; /**< number of cliques stored in the table */
66 };
67 
68 
69 /** creates a clique */
70 static
72  CLIQUE** clique, /**< pointer to the clique */
73  int* nodes, /**< nodes of the clique */
74  int nnodes /**< number of nodes in the clique */
75  )
76 {
77  int i;
78 
79  assert(clique != NULL);
80 
81  ALLOC_ABORT( BMSallocMemory(clique) );
82  ALLOC_ABORT( BMSallocMemoryArray(&(*clique)->nodes, nnodes) );
83 
84  /* sort the nodes into the clique's node array */
85  for( i = 0; i < nnodes; ++i )
86  {
87  int node;
88  int j;
89 
90  node = nodes[i];
91  for( j = i; j > 0 && node < (*clique)->nodes[j-1]; --j )
92  (*clique)->nodes[j] = (*clique)->nodes[j-1];
93  (*clique)->nodes[j] = node;
94  }
95  (*clique)->nnodes = nnodes;
96 }
97 
98 /** frees a clique */
99 static
101  CLIQUE** clique /**< pointer to the clique */
102  )
103 {
104  assert(clique != NULL);
105  assert(*clique != NULL);
106 
107  BMSfreeMemoryArray(&(*clique)->nodes);
108  BMSfreeMemory(clique);
109 }
110 
111 /** checks, whether clique1 is a subset of clique2 and returns the following value:
112  * == 0 if clique1 == clique2, or clique1 is contained in clique2,
113  * < 0 if clique1 < clique2, and clique1 is not contained in clique2,
114  * > 0 if clique1 > clique2, and clique1 is not contained in clique2
115  */
116 static
118  CLIQUE* clique1, /**< first clique to compare */
119  CLIQUE* clique2 /**< second clique to compare */
120  )
121 {
122  int pos1;
123  int pos2;
124  TCLIQUE_Bool clique2smaller;
125 
126  assert(clique1 != NULL);
127  assert(clique2 != NULL);
128 
129  pos1 = 0;
130  pos2 = 0;
131  clique2smaller = FALSE;
132  while( pos1 < clique1->nnodes && pos2 < clique2->nnodes )
133  {
134  if( clique1->nodes[pos1] < clique2->nodes[pos2] )
135  {
136  /* clique1 has an element not contained in clique2: clique1 is lex-smaller, if clique2 was not
137  * detected earlier to be lex-smaller
138  */
139  return (clique2smaller ? +1 : -1);
140  }
141  else if( clique1->nodes[pos1] > clique2->nodes[pos2] )
142  {
143  /* clique2 has an element not contained in clique1: clique2 is lex-smaller, but probably clique1 is
144  * contained in clique2
145  */
146  pos2++;
147  clique2smaller = TRUE;
148  }
149  else
150  {
151  pos1++;
152  pos2++;
153  }
154  }
155 
156  /* if clique1 has additional elements, it is not contained in clique2 */
157  if( pos1 < clique1->nnodes )
158  return (clique2smaller ? +1 : -1);
159 
160  /* clique1 is contained in clique2 */
161  return 0;
162 }
163 
164 #ifndef NDEBUG
165 /** performs an integrity check of the clique hash table */
166 static
168  CLIQUEHASH* cliquehash /**< clique hash table */
169  )
170 {
171  int i;
172 
173  assert(cliquehash != NULL);
174 
175  for( i = 0; i < cliquehash->ncliques-1; ++i )
176  assert(compSubcliques(cliquehash->cliques[i], cliquehash->cliques[i+1]) < 0);
177 }
178 #else
179 #define checkCliquehash(cliquehash) /**/
180 #endif
181 
182 /** creates a table for storing cliques */
183 static
185  CLIQUEHASH** cliquehash, /**< pointer to store the clique hash table */
186  int tablesize /**< initial size of the clique hash table */
187  )
188 {
189  assert(cliquehash != NULL);
190  assert(tablesize > 0);
191 
192  ALLOC_ABORT( BMSallocMemory(cliquehash) );
193  ALLOC_ABORT( BMSallocMemoryArray(&(*cliquehash)->cliques, tablesize) );
194  (*cliquehash)->cliquessize = tablesize;
195  (*cliquehash)->ncliques = 0;
196 }
197 
198 /** clears the clique hash table and frees all inserted cliques */
199 static
201  CLIQUEHASH* cliquehash /**< clique hash table */
202  )
203 {
204  int i;
205 
206  assert(cliquehash != NULL);
207 
208  /* free the cliques in the table */
209  for( i = 0; i < cliquehash->ncliques; ++i )
210  freeClique(&cliquehash->cliques[i]);
211 
212  cliquehash->ncliques = 0;
213 }
214 
215 /** frees the table for storing cliques and all inserted cliques */
216 static
218  CLIQUEHASH** cliquehash /**< pointer to the clique hash table */
219  )
220 {
221  assert(cliquehash != NULL);
222  assert(*cliquehash != NULL);
223 
224  /* free the cliques in the table */
225  clearCliquehash(*cliquehash);
226 
227  /* free the table data structure */
228  BMSfreeMemoryArray(&(*cliquehash)->cliques);
229  BMSfreeMemory(cliquehash);
230 }
231 
232 /** ensures, that the clique hash table is able to store at least the given number of cliques */
233 static
235  CLIQUEHASH* cliquehash, /**< clique hash table */
236  int num /**< minimal number of cliques to store */
237  )
238 {
239  assert(cliquehash != NULL);
240 
241  if( num > cliquehash->cliquessize )
242  {
243  int newsize;
244 
245  newsize = 2*cliquehash->cliquessize;
246  if( num > newsize )
247  newsize = num;
248 
249  ALLOC_ABORT( BMSreallocMemoryArray(&cliquehash->cliques, newsize) );
250  cliquehash->cliquessize = newsize;
251  }
252  assert(cliquehash->cliquessize >= num);
253 }
254 
255 #ifdef TCLIQUE_DEBUG
256 /** displayes clique hash table */
257 static
258 void printCliquehash(
259  CLIQUEHASH* cliquehash /**< clique hash table */
260  )
261 {
262  int i;
263 
264  assert(cliquehash != NULL);
265 
266  debugMessage("cliquehash (%d cliques):\n", cliquehash->ncliques);
267  for( i = 0; i < cliquehash->ncliques; ++i )
268  {
269  int j;
270 
271  debugPrintf("%d:", i);
272  for( j = 0; j < cliquehash->cliques[i]->nnodes; ++j )
273  debugPrintf(" %d", cliquehash->cliques[i]->nodes[j]);
274  debugPrintf("\n");
275  }
276 }
277 #endif
278 
279 /** searches the given clique in the clique hash table and returns whether it (or a stronger clique) exists */
280 static
282  CLIQUEHASH* cliquehash, /**< clique hash table */
283  CLIQUE* clique, /**< clique to search in the table */
284  int* insertpos /**< position where the clique should be inserted in the table */
285  )
286 {
287  int left;
288  int right;
289  int middle;
290  int cmp;
291 
292  assert(cliquehash != NULL);
293  assert(cliquehash->cliquessize > 0);
294  assert(clique != NULL);
295  assert(insertpos != NULL);
296 
297  /* perform a binary search on the clique hash table */
298  left = 0;
299  right = cliquehash->ncliques-1;
300  while( left <= right )
301  {
302  middle = (left+right)/2;
303  cmp = compSubcliques(clique, cliquehash->cliques[middle]);
304  if( cmp > 0 )
305  left = middle+1;
306  else if( cmp < 0 )
307  right = middle-1;
308  else
309  {
310  *insertpos = middle;
311  return TRUE;
312  }
313  }
314 
315  /* we found the correct insertion position for the clique, but it might be contained in a lex-smaller clique */
316  *insertpos = left;
317  for( middle = left-1; middle >= 0; --middle )
318  {
319  cmp = compSubcliques(clique, cliquehash->cliques[middle]);
320  assert(cmp >= 0);
321  if( cmp == 0 )
322  return TRUE;
323  }
324 
325  return FALSE;
326 }
327 
328 /** inserts clique into clique hash table */
329 static
331  CLIQUEHASH* cliquehash, /**< clique hash table */
332  CLIQUE* clique, /**< clique to search in the table */
333  int insertpos /**< position to insert clique into table (returned by inCliquehash()) */
334  )
335 {
336  int i;
337 
338  assert(cliquehash != NULL);
339  assert(clique != NULL);
340  assert(0 <= insertpos && insertpos <= cliquehash->ncliques);
341 
342  /* allocate memory */
343  ensureCliquehashSize(cliquehash, cliquehash->ncliques+1);
344 
345  /* insert clique into table */
346  for( i = cliquehash->ncliques; i > insertpos; --i )
347  cliquehash->cliques[i] = cliquehash->cliques[i-1];
348  cliquehash->cliques[insertpos] = clique;
349  cliquehash->ncliques++;
350 
351  /* check, whether the clique hash table is still sorted */
352  checkCliquehash(cliquehash);
353 
354  debug(printCliquehash(cliquehash));
355 }
356 
357 
358 
359 
360 /****************************
361  * clique calculation methods
362  ****************************/
363 
364 /** extends given clique by additional zero-weight nodes of the given node set */
365 static
367  TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
368  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
369  int* buffer, /**< buffer of size nnodes */
370  int* Vzero, /**< zero weighted nodes */
371  int nVzero, /**< number of zero weighted nodes */
372  int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
373  int* curcliquenodes, /**< nodes of the clique */
374  int* ncurcliquenodes /**< pointer to store number of nodes in the clique */
375  )
376 {
377  int i;
378  int* zerocands;
379  int nzerocands;
380  int nzeroextensions;
381 
382  assert(selectadjnodes != NULL);
383  assert(buffer != NULL);
384  assert(Vzero != NULL);
385  assert(curcliquenodes != NULL);
386  assert(ncurcliquenodes != NULL);
387 
388  debugMessage("extending temporary clique (size %d) with zero-weighted nodes (nVzero=%d)\n", *ncurcliquenodes, nVzero);
389 
390  if( maxnzeroextensions == 0 )
391  return;
392 
393  /* initialize the zero-weighted candidates for clique extension */
394  zerocands = buffer;
395  BMScopyMemoryArray(zerocands, Vzero, nVzero);
396  nzerocands = nVzero;
397 
398  /* for each node in the clique, remove non-adjacent nodes from the zero extension candidates */
399  for( i = 0; i < *ncurcliquenodes && nzerocands > 0; ++i )
400  {
401  nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[i], zerocands, nzerocands, zerocands);
402  }
403 
404  /* put zero-weighted candidates into the clique, and remove non-adjacent nodes from the candidate set */
405  nzeroextensions = 0;
406  while( nzerocands > 0 )
407  {
408  /* put first candidate into the clique */
409  curcliquenodes[*ncurcliquenodes] = zerocands[0];
410  (*ncurcliquenodes)++;
411  nzerocands--;
412  zerocands++;
413  nzeroextensions++;
414  if( nzeroextensions >= maxnzeroextensions )
415  break;
416 
417  /* remove candidates that are not adjacent to the inserted zero-weighted node */
418  nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[(*ncurcliquenodes)-1], zerocands, nzerocands, zerocands);
419  }
420 }
421 
422 /** calls user callback after a new solution was found, that is better than the current incumbent
423  *
424  * The callback decides, whether this solution should be accepted as new incumbent, and whether the solution process
425  * should be stopped.
426  */
427 static
429  TCLIQUE_SELECTADJNODES((*selectadjnodes)), /**< user function to select adjacent edges */
430  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
431  TCLIQUE_NEWSOL((*newsol)), /**< user function to call on every new solution */
432  TCLIQUE_DATA* tcliquedata, /**< user data to pass to user callback function */
433  CLIQUEHASH* cliquehash, /**< clique hash table */
434  int* buffer, /**< buffer of size nnodes */
435  int* Vzero, /**< zero weighted nodes */
436  int nVzero, /**< number of zero weighted nodes */
437  int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
438  int* curcliquenodes, /**< nodes of the new clique */
439  int ncurcliquenodes, /**< number of nodes in the new clique */
440  TCLIQUE_WEIGHT curcliqueweight, /**< weight of the new clique */
441  int* maxcliquenodes, /**< pointer to store nodes of the maximum weight clique */
442  int* nmaxcliquenodes, /**< pointer to store number of nodes in the maximum weight clique */
443  TCLIQUE_WEIGHT* maxcliqueweight, /**< pointer to store weight of the maximum weight clique */
444  TCLIQUE_Bool* stopsolving /**< pointer to store whether the solving should be stopped */
445  )
446 {
447  CLIQUE* clique;
448  int insertpos;
449  TCLIQUE_Bool acceptsol;
450 
451  assert(curcliquenodes != NULL);
452  assert(maxcliquenodes != NULL);
453  assert(nmaxcliquenodes != NULL);
454  assert(maxcliqueweight != NULL);
455  assert(curcliqueweight > *maxcliqueweight);
456  assert(stopsolving != NULL);
457  assert(newsol == NULL || cliquehash != NULL);
458 
459  acceptsol = TRUE;
460  *stopsolving = FALSE;
461  clique = NULL;
462  insertpos = 0;
463 
464  if( newsol != NULL )
465  {
466  /* check whether the clique is already stored in the table */
467  if( cliquehash->ncliques > 0 )
468  {
469  createClique(&clique, curcliquenodes, ncurcliquenodes);
470  acceptsol = !inCliquehash(cliquehash, clique, &insertpos);
471  }
472  }
473 
474  /* check, if this is a new clique */
475  if( acceptsol )
476  {
477  /* extend the clique with the zero-weighted nodes */
478  extendCliqueZeroWeight(selectadjnodes, tcliquegraph, buffer, Vzero, nVzero, maxnzeroextensions,
479  curcliquenodes, &ncurcliquenodes);
480 
481  if( newsol != NULL )
482  {
483  /* call user callback method */
484  newsol(tcliquedata, curcliquenodes, ncurcliquenodes, curcliqueweight, maxcliqueweight, &acceptsol, stopsolving);
485 
486  /* if clique was accepted, clear the clique hash table; otherwise, insert it into the clique hash table, such that
487  * the same or a weaker clique is not presented to the user again
488  */
489  if( acceptsol )
490  clearCliquehash(cliquehash);
491  else
492  {
493  /* if the clique was not yet created, do it now */
494  if( clique == NULL )
495  {
496  assert(insertpos == 0);
497  assert(cliquehash->ncliques == 0);
498  createClique(&clique, curcliquenodes, ncurcliquenodes);
499  }
500 
501  /* insert clique into clique hash table */
502  insertClique(cliquehash, clique, insertpos);
503  clique = NULL; /* the clique now belongs to the table */
504  }
505  }
506  }
507 
508  /* free the clique, if it was created and not put into the clique hash table */
509  if( clique != NULL )
510  freeClique(&clique);
511 
512  if( acceptsol )
513  {
514  /* copy the solution to the incumbent */
515  BMScopyMemoryArray(maxcliquenodes, curcliquenodes, ncurcliquenodes);
516  *nmaxcliquenodes = ncurcliquenodes;
517  if( curcliqueweight > *maxcliqueweight )
518  *maxcliqueweight = curcliqueweight;
519  }
520 
521 #ifdef TCLIQUE_DEBUG
522  debugMessage(" -> clique %s (weight %d):", acceptsol ? "accepted" : "rejected", curcliqueweight);
523  {
524  int i;
525  for( i = 0; i < ncurcliquenodes; ++i )
526  debugPrintf(" %d", curcliquenodes[i]);
527  debugPrintf("\n");
528  }
529 #endif
530 }
531 
532 /** tries to find a clique, if V has only one or two nodes */
533 static
534 void reduced(
535  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
536  TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */
537  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
538  int* V, /**< non-zero weighted nodes for branching */
539  int nV, /**< number of non-zero weighted nodes for branching */
540  TCLIQUE_WEIGHT* apbound, /**< apriori bound of nodes for branching */
541  int* tmpcliquenodes, /**< buffer for storing the temporary clique */
542  int* ntmpcliquenodes, /**< pointer to store number of nodes of the temporary clique */
543  TCLIQUE_WEIGHT* tmpcliqueweight /**< pointer to store weight of the temporary clique */
544  )
545 {
546  const TCLIQUE_WEIGHT* weights;
547 
548  assert(getweights != NULL);
549  assert(isedge != NULL);
550  assert(tcliquegraph != NULL);
551  assert(V != NULL);
552  assert(0 <= nV && nV <= 2);
553  assert(apbound != NULL);
554  assert(tmpcliquenodes != NULL);
555  assert(ntmpcliquenodes != NULL);
556  assert(tmpcliqueweight != NULL);
557 
558  weights = getweights(tcliquegraph);
559  assert(nV == 0 || weights[V[0]] > 0);
560  assert(nV <= 1 || weights[V[1]] > 0);
561 
562  if( nV >= 1 )
563  apbound[0] = weights[V[0]];
564  if( nV >= 2 )
565  apbound[1] = weights[V[1]];
566 
567  /* check if nodes are adjacent */
568  if( nV >= 2 && isedge(tcliquegraph, V[0], V[1]) )
569  {
570  assert(isedge(tcliquegraph, V[1], V[0]));
571 
572  /* put nodes into clique */
573  tmpcliquenodes[0] = V[0];
574  tmpcliquenodes[1] = V[1];
575  *ntmpcliquenodes = 2;
576  *tmpcliqueweight = weights[V[0]] + weights[V[1]];
577  apbound[0] += weights[V[1]];
578  }
579  else if( nV >= 2 && weights[V[1]] > weights[V[0]] )
580  {
581  /* put V[1] into clique */
582  tmpcliquenodes[0] = V[1];
583  *ntmpcliquenodes = 1;
584  *tmpcliqueweight = weights[V[1]];
585  }
586  else if( nV >= 1 )
587  {
588  /* put V[0] into clique */
589  tmpcliquenodes[0] = V[0];
590  *ntmpcliquenodes = 1;
591  *tmpcliqueweight = weights[V[0]];
592  }
593  else
594  {
595  *tmpcliqueweight = 0;
596  *ntmpcliquenodes = 0;
597  }
598 }
599 
600 /** calculates upper bound on remaining subgraph, and heuristically generates a clique */
601 static
603  TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
604  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
605  TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */
606  TCLIQUE_SELECTADJNODES((*selectadjnodes)), /**< user function to select adjacent edges */
607  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
608  BMS_CHKMEM* mem, /**< block memory */
609  int* buffer, /**< buffer of size nnodes */
610  int* V, /**< non-zero weighted nodes for branching */
611  int nV, /**< number of non-zero weighted nodes for branching */
612  NBC* gsd, /**< neighbour color information of all nodes */
613  TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
614  TCLIQUE_WEIGHT* apbound, /**< apriori bound of nodes for branching */
615  int* tmpcliquenodes, /**< buffer for storing the temporary clique */
616  int* ntmpcliquenodes, /**< pointer to store number of nodes of the temporary clique */
617  TCLIQUE_WEIGHT* tmpcliqueweight /**< pointer to store weight of the temporary clique */
618  )
619 {
620  assert(tmpcliqueweight != NULL);
621 
622  /* check if we are in an easy case with at most 2 nodes left */
623  if( nV <= 2 )
624  {
625  /* get 1- or 2-clique and bounds without coloring */
626  reduced(getweights, isedge, tcliquegraph, V, nV, apbound, tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
627  return *tmpcliqueweight;
628  }
629  else
630  {
631  /* color the graph induces by nodes of V to get an upper bound for the remaining subgraph */
632  return tcliqueColoring(getnnodes, getweights, selectadjnodes, tcliquegraph,
633  mem, buffer, V, nV, gsd, iscolored, apbound,
634  tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
635  }
636 }
637 
638 /** gets the index of the node of V with the maximum apriori bound; returns -1, if no node exists */
639 static
641  int nV, /**< number of nodes of V */
642  TCLIQUE_WEIGHT* apbound /**< apriori bound of nodes of V */
643  )
644 {
645  TCLIQUE_WEIGHT maxapbound;
646  int maxindex;
647  int i;
648 
649  assert(apbound != NULL);
650 
651  maxapbound = 0;
652  maxindex = -1;
653 
654  for( i = 0 ; i < nV; i++ )
655  {
656  assert(apbound[i] > 0);
657  if( apbound[i] >= maxapbound )
658  {
659  maxapbound = apbound[i];
660  maxindex = i;
661  }
662  }
663 
664  return maxindex;
665 }
666 
667 /** gets the index of the node of V with the maximum apriori bound, but ignores nodes with weights
668  * larger than the given maximal weight
669  *
670  * Returns -1 if no node with weight smaller or equal than maxweight is found.
671  */
672 static
674  int* V, /**< non-zero weighted nodes for branching */
675  int nV, /**< number of non-zero weighted nodes for branching */
676  const TCLIQUE_WEIGHT* apbound, /**< apriori bound of nodes of V */
677  const TCLIQUE_WEIGHT* weights, /**< weights of nodes */
678  TCLIQUE_WEIGHT maxweight /**< maximal weight of node to be candidate for selection */
679  )
680 {
681  TCLIQUE_WEIGHT maxapbound;
682  int maxindex;
683  int i;
684 
685  assert(apbound != NULL);
686 
687  maxapbound = 0;
688  maxindex = -1;
689 
690  for( i = 0 ; i < nV; i++ )
691  {
692  assert(apbound[i] > 0);
693  assert(weights[V[i]] > 0);
694 
695  if( apbound[i] >= maxapbound && weights[V[i]] <= maxweight )
696  {
697  maxapbound = apbound[i];
698  maxindex = i;
699  }
700  }
701 
702  return maxindex;
703 }
704 
705 /** branches the searching tree, branching nodes are selected in decreasing order of their apriori bound,
706  * returns the level to which we should backtrack, or INT_MAX for continuing normally
707  */
708 static
709 int branch(
710  TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
711  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
712  TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */
713  TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
714  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
715  TCLIQUE_NEWSOL((*newsol)), /**< user function to call on every new solution */
716  TCLIQUE_DATA* tcliquedata, /**< user data to pass to user callback function */
717  BMS_CHKMEM* mem, /**< block memory */
718  CLIQUEHASH* cliquehash, /**< clique hash table */
719  int* buffer, /**< buffer of size nnodes */
720  int level, /**< level of b&b tree */
721  int* V, /**< non-zero weighted nodes for branching */
722  int nV, /**< number of non-zero weighted nodes for branching */
723  int* Vzero, /**< zero weighted nodes */
724  int nVzero, /**< number of zero weighted nodes */
725  NBC* gsd, /**< neighbour color information of all nodes */
726  TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
727  int* K, /**< nodes from the b&b tree */
728  TCLIQUE_WEIGHT weightK, /**< weight of the nodes from b&b tree */
729  int* maxcliquenodes, /**< pointer to store nodes of the maximum weight clique */
730  int* nmaxcliquenodes, /**< pointer to store number of nodes in the maximum weight clique */
731  TCLIQUE_WEIGHT* maxcliqueweight, /**< pointer to store weight of the maximum weight clique */
732  int* curcliquenodes, /**< pointer to store nodes of currenct clique */
733  int* ncurcliquenodes, /**< pointer to store number of nodes in current clique */
734  TCLIQUE_WEIGHT* curcliqueweight, /**< pointer to store weight of current clique */
735  int* tmpcliquenodes, /**< buffer for storing the temporary clique */
736  TCLIQUE_WEIGHT maxfirstnodeweight, /**< maximum weight of branching nodes in level 0; 0 if not used
737  * (for cliques with at least one fractional node) */
738  int* ntreenodes, /**< pointer to store number of nodes of b&b tree */
739  int maxntreenodes, /**< maximal number of nodes of b&b tree */
740  int backtrackfreq, /**< frequency to backtrack to first level of tree (0: no premature backtracking) */
741  int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
742  int fixednode, /**< node that is forced to be in the clique, or -1; must have positive weight */
743  TCLIQUE_STATUS* status /**< pointer to store the status of the solving call */
744  )
745 {
746  TCLIQUE_Bool isleaf;
747  const TCLIQUE_WEIGHT* weights;
748  TCLIQUE_WEIGHT* apbound;
749  TCLIQUE_WEIGHT subgraphweight;
750  TCLIQUE_WEIGHT weightKold;
751  TCLIQUE_WEIGHT tmpcliqueweight;
752  int backtracklevel;
753  int ntmpcliquenodes;
754  int i;
755 
756  assert(getnnodes != NULL);
757  assert(getweights != NULL);
758  assert(selectadjnodes != NULL);
759  assert(mem != NULL);
760  assert(V != NULL);
761  assert(gsd != NULL);
762  assert(iscolored != NULL);
763  assert(K != NULL);
764  assert(maxcliqueweight != NULL);
765  assert(curcliquenodes != NULL);
766  assert(ncurcliquenodes != NULL);
767  assert(curcliqueweight != NULL);
768  assert(ntreenodes != NULL);
769  assert(maxfirstnodeweight >= 0);
770  assert(*ntreenodes >= 0);
771  assert(maxntreenodes >= 0);
772  assert(status != NULL);
773 
774  /* increase the number of nodes, and stop solving, if the node limit is exceeded */
775  (*ntreenodes)++;
776 #ifdef TCLIQUE_DEBUG
777  debugMessage("(level %d, treenode %d) maxclique = %d, curclique = %d [mem=%" SCIP_LONGINT_FORMAT " (%" SCIP_LONGINT_FORMAT "), cliques=%d]\n",
778  level, *ntreenodes, *maxcliqueweight, *curcliqueweight,
779  BMSgetChunkMemoryUsed(mem), BMSgetMemoryUsed(), cliquehash == NULL ? 0 : cliquehash->ncliques);
780 
781  debugMessage(" -> current branching (weight %d):", weightK);
782  for( i = 0; i < level; ++i )
783  debugPrintf(" %d", K[i]);
784  debugPrintf("\n");
785  debugMessage(" -> branching candidates:");
786  for( i = 0; i < nV; ++i )
787  debugPrintf(" %d", V[i]);
788  debugPrintf("\n");
789 #endif
790  if( *ntreenodes > maxntreenodes )
791  {
792  *status = TCLIQUE_NODELIMIT;
793  return TRUE;
794  }
795 
796  weights = getweights(tcliquegraph);
797  backtracklevel = INT_MAX;
798  isleaf = TRUE;
799 
800  /* allocate temporary memory for a priori bounds */
801  ALLOC_ABORT( BMSallocMemoryArray(&apbound, nV) );
802  BMSclearMemoryArray(apbound, nV);
803 
804  /* use coloring relaxation to generate an upper bound for the current subtree and a heuristic solution */
805  subgraphweight = boundSubgraph(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph,
806  mem, buffer, V, nV, gsd, iscolored, apbound,
807  tmpcliquenodes, &ntmpcliquenodes, &tmpcliqueweight);
808 
809 #ifndef NDEBUG
810  /* check correctness of V and apbound arrays */
811  for( i = 0; i < nV; ++i )
812  {
813  assert(0 <= V[i] && V[i] < getnnodes(tcliquegraph));
814  assert(i == 0 || V[i-1] < V[i]);
815  assert(apbound[i] >= 0);
816  assert((apbound[i] == 0) == (weights[V[i]] == 0));
817  }
818 #endif
819 
820  /* check, whether the heuristic solution is better than the current subtree's solution;
821  * if the user wanted to have a fixed variable inside the clique and we are in level 0, we first have to
822  * fix this variable in this level (the current clique might not contain the fixed node)
823  */
824  if( weightK + tmpcliqueweight > *curcliqueweight && (level > 0 || fixednode == -1) )
825  {
826  /* install the newly generated clique as current clique */
827  for( i = 0; i < level; ++i )
828  curcliquenodes[i] = K[i];
829  for( i = 0; i < ntmpcliquenodes; ++i )
830  curcliquenodes[level+i] = tmpcliquenodes[i];
831  *ncurcliquenodes = level + ntmpcliquenodes;
832  *curcliqueweight = weightK + tmpcliqueweight;
833 
834 #ifdef TCLIQUE_DEBUG
835  debugMessage(" -> new current clique with weight %d at node %d in level %d:",
836  *curcliqueweight, *ntreenodes, level);
837  for( i = 0; i < *ncurcliquenodes; ++i )
838  debugPrintf(" %d", curcliquenodes[i]);
839  debugPrintf("\n");
840 #endif
841  }
842 
843  /* discard subtree, if the upper bound is not better than the weight of the currently best clique;
844  * if only 2 nodes are left, the maximal weighted clique was already calculated in boundSubgraph() and nothing
845  * more has to be done;
846  * however, if the user wanted to have a fixed node and we are in the first decision level, we have to continue
847  */
848  if( weightK + subgraphweight > *maxcliqueweight && (nV > 2 || (fixednode >= 0 && level == 0)) )
849  {
850  int* Vcurrent;
851  int nVcurrent;
852  int nValive;
853  int branchingnode;
854 
855  assert(nV > 0);
856 
857  /* process current subtree */
858  level++;
859 
860  /* set up data structures */
861  ALLOC_ABORT( BMSallocMemoryArray(&Vcurrent, nV-1) );
862 
863  nValive = nV;
864  weightKold = weightK;
865 
866  debugMessage("============================ branching level %d ===============================\n", level);
867 
868  /* branch on the nodes of V by decreasing order of their apriori bound */
869  while( backtracklevel >= level && nValive > 0 )
870  {
871  int branchidx;
872 
873  /* check if we meet the backtracking frequency - in this case abort the search until we have reached first level */
874  if( level > 1 && backtrackfreq > 0 && (*ntreenodes) % backtrackfreq == 0 )
875  {
876  backtracklevel = 1;
877  break;
878  }
879 
880  /* get next branching node */
881  if( level == 1 && fixednode >= 0 )
882  {
883  /* select the fixed node as first "branching" candidate */
884  for( branchidx = 0; branchidx < nValive && V[branchidx] != fixednode; branchidx++ )
885  {}
886  assert(branchidx < nValive);
887  assert(V[branchidx] == fixednode);
888  }
889  else if( level == 1 && maxfirstnodeweight > 0 )
890  branchidx = getMaxApBoundIndexNotMaxWeight(V, nValive, apbound, weights, maxfirstnodeweight);
891  else
892  branchidx = getMaxApBoundIndex(nValive, apbound);
893  if( branchidx < 0 )
894  break;
895  assert(0 <= branchidx && branchidx < nValive && nValive <= nV);
896  assert(apbound[branchidx] > 0);
897  assert(weights[V[branchidx]] > 0);
898 
899  /* test a priori bound */
900  if( (weightKold + apbound[branchidx]) <= *maxcliqueweight )
901  break;
902 
903  debugMessage("%d. branching in level %d (treenode %d): bidx=%d, node %d, weight %d, upperbound: %d+%d = %d, maxclique=%d\n",
904  nV-nValive+1, level, *ntreenodes, branchidx, V[branchidx], weights[V[branchidx]], weightKold,
905  apbound[branchidx], weightKold + apbound[branchidx], *maxcliqueweight);
906 
907  /* because we branch on this node, the node is no leaf in the tree */
908  isleaf = FALSE;
909 
910  /* update the set of nodes from the b&b tree
911  * K = K & {branchingnode}
912  */
913  branchingnode = V[branchidx];
914  K[level-1] = branchingnode;
915  weightK = weightKold + weights[branchingnode];
916 
917  /* update the set of nodes for branching
918  * V = V \ {branchingnode}
919  */
920  nValive--;
921  for( i = branchidx; i < nValive; ++i )
922  {
923  V[i] = V[i+1];
924  apbound[i] = apbound[i+1];
925  }
926 
927  /* set the nodes for the next level of b&b tree
928  * Vcurrent = nodes of V, that are adjacent to branchingnode
929  */
930  nVcurrent = selectadjnodes(tcliquegraph, branchingnode, V, nValive, Vcurrent);
931 
932  /* process the selected subtree */
933  backtracklevel = branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata, /*lint !e838*/
934  mem, cliquehash, buffer,
935  level, Vcurrent, nVcurrent, Vzero, nVzero, gsd, iscolored, K, weightK,
936  maxcliquenodes, nmaxcliquenodes, maxcliqueweight,
937  curcliquenodes, ncurcliquenodes, curcliqueweight, tmpcliquenodes,
938  maxfirstnodeweight, ntreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, -1, status);
939 
940  /* if all other candidates stayed in the candidate list, the current branching was optimal and
941  * there is no need to try the remaining ones
942  */
943  if( nVcurrent == nValive )
944  {
945  debugMessage("branching on node %d was optimal - ignoring remaining candidates\n", branchingnode);
946  nValive = 0;
947  }
948 
949  /* if we had a fixed node, ignore all other nodes */
950  if( fixednode >= 0 )
951  nValive = 0;
952  }
953 
954  debugMessage("========================== branching level %d end =============================\n\n", level);
955 
956  /* free data structures */
957  BMSfreeMemoryArray(&Vcurrent);
958  }
959 
960  /* check, whether any branchings have been applied, or if this node is a leaf of the branching tree */
961  if( isleaf )
962  {
963  /* the current clique is the best clique found on the path to this leaf
964  * -> check, whether it is an improvement to the currently best clique
965  */
966  if( *curcliqueweight > *maxcliqueweight )
967  {
968  TCLIQUE_Bool stopsolving;
969 
970  debugMessage("found clique of weight %d at node %d in level %d\n", *curcliqueweight, *ntreenodes, level);
971  newSolution(selectadjnodes, tcliquegraph, newsol, tcliquedata, cliquehash, buffer, Vzero, nVzero,
972  maxnzeroextensions, curcliquenodes, *ncurcliquenodes, *curcliqueweight,
973  maxcliquenodes, nmaxcliquenodes, maxcliqueweight, &stopsolving);
974 
975  if( stopsolving )
976  {
977  debugMessage(" -> solving terminated by callback method\n");
978  backtracklevel = 0;
979  }
980  }
981 
982  /* discard the current clique */
983  *ncurcliquenodes = 0;
984  *curcliqueweight = 0;
985  }
986 
987 #ifdef TCLIQUE_DEBUG
988  if( level > backtracklevel )
989  {
990  debugMessage("premature backtracking after %d nodes - level %d\n", *ntreenodes, level);
991  }
992 #endif
993 
994  /* free data structures */
995  BMSfreeMemoryArray(&apbound);
996 
997  return backtracklevel;
998 }
999 
1000 /** finds maximum weight clique */
1002  TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
1003  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
1004  TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */
1005  TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
1006  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure that is passed to graph callbacks */
1007  TCLIQUE_NEWSOL((*newsol)), /**< user function to call on every new solution */
1008  TCLIQUE_DATA* tcliquedata, /**< user data to pass to new solution callback function */
1009  int* maxcliquenodes, /**< pointer to store nodes of the maximum weight clique */
1010  int* nmaxcliquenodes, /**< pointer to store number of nodes in the maximum weight clique */
1011  TCLIQUE_WEIGHT* maxcliqueweight, /**< pointer to store weight of the maximum weight clique */
1012  TCLIQUE_WEIGHT maxfirstnodeweight, /**< maximum weight of branching nodes in level 0; 0 if not used
1013  * for cliques with at least one fractional node) */
1014  TCLIQUE_WEIGHT minweight, /**< lower bound for weight of generated cliques */
1015  int maxntreenodes, /**< maximal number of nodes of b&b tree */
1016  int backtrackfreq, /**< frequency to backtrack to first level of tree (0: no premature backtracking) */
1017  int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
1018  int fixednode, /**< node that is forced to be in the clique, or -1; must have positive weight */
1019  int* ntreenodes, /**< pointer to store the number of used tree nodes (or NULL) */
1020  TCLIQUE_STATUS* status /**< pointer to store the status of the solving call */
1021  )
1022 {
1023  CLIQUEHASH* cliquehash;
1024  const TCLIQUE_WEIGHT* weights;
1025  int* buffer;
1026  int* K;
1027  int* V;
1028  int* Vzero;
1029  int nnodes;
1030  int nV;
1031  int nVzero;
1032  int i;
1033  BMS_CHKMEM* mem;
1034  NBC* gsd;
1035  TCLIQUE_Bool* iscolored;
1036  int* curcliquenodes;
1037  int ncurcliquenodes;
1038  TCLIQUE_WEIGHT curcliqueweight;
1039  int* tmpcliquenodes;
1040  int nbbtreenodes;
1041  int backtracklevel;
1042 
1043  assert(maxcliquenodes != NULL);
1044  assert(nmaxcliquenodes != NULL);
1045  assert(maxcliqueweight != NULL);
1046  assert(maxntreenodes >= 0);
1047  assert(backtrackfreq >= 0);
1048  assert(maxnzeroextensions >= 0);
1049  assert(status != NULL);
1050 
1051  *status = TCLIQUE_OPTIMAL;
1052 
1053  /* use default graph callbacks, if NULL pointers are given */
1054  if( getnnodes == NULL )
1055  getnnodes = tcliqueGetNNodes;
1056  if( getweights == NULL )
1057  getweights = tcliqueGetWeights;
1058  if( isedge == NULL )
1059  isedge = tcliqueIsEdge;
1060  if( selectadjnodes == NULL )
1061  selectadjnodes = tcliqueSelectAdjnodes;
1062 
1063  /* get number of nodes */
1064  nnodes = getnnodes(tcliquegraph);
1065 
1066  debugMessage("calculating maximal weighted clique in graph (%d nodes)\n", nnodes);
1067 
1068  /* set up data structures */
1069  if( newsol != NULL )
1070  createCliquehash(&cliquehash, CLIQUEHASH_INITSIZE);
1071  else
1072  cliquehash = NULL;
1073  ALLOC_ABORT( BMSallocMemoryArray(&buffer, nnodes) );
1074  ALLOC_ABORT( BMSallocMemoryArray(&K, nnodes) );
1075  ALLOC_ABORT( BMSallocMemoryArray(&V, nnodes) );
1076  ALLOC_ABORT( BMSallocMemoryArray(&Vzero, nnodes) );
1077  ALLOC_ABORT( BMSallocMemoryArray(&gsd, nnodes) );
1078  ALLOC_ABORT( BMSallocMemoryArray(&iscolored, nnodes) );
1079  ALLOC_ABORT( BMSallocMemoryArray(&curcliquenodes, nnodes) );
1080  ALLOC_ABORT( BMSallocMemoryArray(&tmpcliquenodes, nnodes) );
1081 
1082  /* set weight and number of nodes of maximum weighted clique */
1083  *nmaxcliquenodes = 0;
1084  *maxcliqueweight = minweight-1;
1085  ncurcliquenodes = 0;
1086  curcliqueweight = 0;
1087  nbbtreenodes = 0;
1088 
1089  /* set up V and Vzero */
1090  weights = getweights(tcliquegraph);
1091  assert(weights != NULL);
1092  nV = 0;
1093  nVzero = 0;
1094  for( i = 0 ; i < nnodes; i++ )
1095  {
1096  if( weights[i] == 0 )
1097  {
1098  Vzero[nVzero] = i;
1099  nVzero++;
1100  }
1101  else
1102  {
1103  V[nV] = i;
1104  nV++;
1105  }
1106  }
1107 
1108  /* initialize own memory allocator for coloring */
1109  mem = BMScreateChunkMemory(sizeof(LIST_ITV), CHUNK_SIZE, -1);
1110 
1111  /* branch to find maximum weight clique */
1112  backtracklevel = branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata, mem,
1113  cliquehash, buffer, 0, V, nV, Vzero, nVzero, gsd, iscolored, K, 0,
1114  maxcliquenodes, nmaxcliquenodes, maxcliqueweight,
1115  curcliquenodes, &ncurcliquenodes, &curcliqueweight, tmpcliquenodes,
1116  maxfirstnodeweight, &nbbtreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, fixednode, status);
1117 
1118  if ( ntreenodes != NULL )
1119  *ntreenodes = nbbtreenodes;
1120 
1121  if( backtracklevel != INT_MAX && *status == TCLIQUE_OPTIMAL )
1122  *status = TCLIQUE_USERABORT;
1123 
1124  /* delete own memory allocator for coloring */
1125  BMSdestroyChunkMemory(&mem);
1126 
1127  /* free data structures */
1128  BMSfreeMemoryArray(&tmpcliquenodes);
1129  BMSfreeMemoryArray(&curcliquenodes);
1130  BMSfreeMemoryArray(&iscolored);
1131  BMSfreeMemoryArray(&gsd);
1132  BMSfreeMemoryArray(&Vzero);
1133  BMSfreeMemoryArray(&V);
1134  BMSfreeMemoryArray(&K);
1135  BMSfreeMemoryArray(&buffer);
1136  if( newsol != NULL )
1137  freeCliquehash(&cliquehash);
1138 } /*lint !e438*/
#define TCLIQUE_GETWEIGHTS(x)
Definition: tclique.h:96
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
Definition: tclique.h:59
struct cliquehash CLIQUEHASH
struct BMS_ChkMem BMS_CHKMEM
Definition: memory.h:295
tclique defines
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
static void clearCliquehash(CLIQUEHASH *cliquehash)
static void freeCliquehash(CLIQUEHASH **cliquehash)
static void freeClique(CLIQUE **clique)
#define TCLIQUE_SELECTADJNODES(x)
Definition: tclique.h:121
static void extendCliqueZeroWeight(TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int *ncurcliquenodes)
#define ALLOC_ABORT(x)
Definition: tclique_def.h:43
static int getMaxApBoundIndexNotMaxWeight(int *V, int nV, const TCLIQUE_WEIGHT *apbound, const TCLIQUE_WEIGHT *weights, TCLIQUE_WEIGHT maxweight)
#define debugPrintf
Definition: tclique_def.h:74
#define CLIQUEHASH_INITSIZE
#define FALSE
Definition: def.h:87
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 TRUE
Definition: def.h:86
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)
Definition: memory.h:116
tclique user interface
#define BMSgetChunkMemoryUsed(mem)
Definition: memory.h:310
#define BMSfreeMemory(ptr)
Definition: memory.h:138
#define debugMessage
Definition: tclique_def.h:73
coloring part of algorithm for maximum cliques
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:140
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)
#define TCLIQUE_Bool
Definition: tclique.h:44
#define NULL
Definition: lpi_spx1.cpp:155
static TCLIQUE_Bool inCliquehash(CLIQUEHASH *cliquehash, CLIQUE *clique, int *insertpos)
#define TCLIQUE_ISEDGE(x)
Definition: tclique.h:106
#define debug(x)
Definition: tclique_def.h:72
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
#define BMScreateChunkMemory(sz, isz, gbf)
Definition: memory.h:300
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 CHUNK_SIZE
struct _NBC NBC
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:120
static int getMaxApBoundIndex(int nV, TCLIQUE_WEIGHT *apbound)
#define TCLIQUE_GETNNODES(x)
Definition: tclique.h:88
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()
Definition: memory.h:149
#define nnodes
Definition: gastrans.c:65
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
static void createClique(CLIQUE **clique, int *nodes, int nnodes)
int TCLIQUE_WEIGHT
Definition: tclique.h:39
struct clique CLIQUE
#define BMSdestroyChunkMemory(mem)
Definition: memory.h:302
struct _LIST_ITV LIST_ITV
#define TCLIQUE_NEWSOL(x)
Definition: tclique.h:79
memory allocation routines