1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program                         */
4    	/*              TCLIQUE --- Algorithm for Maximum Cliques                    */
5    	/*                                                                           */
6    	/*  Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB)                      */
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"
43   	#include "tclique/tclique_coloring.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
80   	void createClique(
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
109  	void freeClique(
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
126  	int compSubcliques(
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
176  	void checkCliquehash(
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
193  	void createCliquehash(
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
209  	void clearCliquehash(
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
226  	void freeCliquehash(
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
243  	void ensureCliquehashSize(
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
290  	TCLIQUE_Bool inCliquehash(
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
339  	void insertClique(
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
375  	void extendCliqueZeroWeight(
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
437  	void newSolution(
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
611  	TCLIQUE_WEIGHT boundSubgraph(
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
649  	int getMaxApBoundIndex(
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
682  	int getMaxApBoundIndexNotMaxWeight(
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 */
1010 	void tcliqueMaxClique(
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*/
1148