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