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