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_coloring.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  coloring 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   	
40   	#include "tclique/tclique.h"
41   	#include "tclique/tclique_def.h"
42   	#include "tclique/tclique_coloring.h"
43   	#include "blockmemshell/memory.h"
44   	
45   	
46   	
47   	/** gets index of the uncolored node in a given array of nodes in V with maximum satdeg;
48   	 *  in case of a tie choose node with maximum weight;
49   	 *  if no uncolored node is found, -1 is returned
50   	 */
51   	static
52   	int getMaxSatdegIndex(
53   	   int*                  V,                  /**< non-zero weighted nodes for branching */
54   	   int                   nV,                 /**< number of non-zero weighted nodes for branching */
55   	   NBC*                  gsd,                /**< neighbor color information of all nodes */
56   	   TCLIQUE_Bool*         iscolored,          /**< coloring status of all nodes */
57   	   const TCLIQUE_WEIGHT* weights             /**< weight of nodes in grpah */
58   	   )
59   	{
60   	   TCLIQUE_WEIGHT maxweight;
61   	   int maxsatdeg;
62   	   int maxsatdegindex;
63   	   int i;
64   	
65   	   maxweight = -1;
66   	   maxsatdeg = -1;
67   	   maxsatdegindex = -1;
68   	
69   	   assert(gsd != NULL);
70   	   assert(iscolored != NULL);
71   	
72   	   for( i = 0; i < nV; i++ )
73   	   {
74   	      TCLIQUE_WEIGHT weight;
75   	      int satdeg;
76   	
77   	      /* check only uncolored nodes */
78   	      if( iscolored[i] )
79   	         continue;
80   	
81   	      weight = weights[V[i]];
82   	      assert(weight > 0);
83   	
84   	      satdeg = gsd[i].satdeg;
85   	      if( satdeg > maxsatdeg || (satdeg == maxsatdeg && weight > maxweight) )
86   	      {
87   	         maxsatdeg = satdeg;
88   	         maxweight = weight;
89   	         maxsatdegindex = i;
90   	      }
91   	   }
92   	
93   	   return maxsatdegindex;
94   	}
95   	
96   	/** gets index of the node in a given set of nodes with maximum weight */
97   	static
98   	int getMaxWeightIndex(
99   	   TCLIQUE_GETNNODES((*getnnodes)),          /**< user function to get the number of nodes */
100  	   TCLIQUE_GETWEIGHTS((*getweights)),        /**< user function to get the node weights */
101  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< pointer to graph data structure */
102  	   int*                  V,                  /**< non-zero weighted nodes for branching */
103  	   int                   nV                  /**< number of non-zero weighted nodes for branching */
104  	   )
105  	{
106  	   const TCLIQUE_WEIGHT* weights;
107  	   TCLIQUE_WEIGHT maxweight;
108  	   int maxweightindex;
109  	   int i;
110  	
111  	   assert(getnnodes != NULL);
112  	   assert(getweights != NULL);
113  	   assert(tcliquegraph != NULL);
114  	   assert(nV > 0);
115  	
116  	   weights = getweights(tcliquegraph);
117  	
118  	   maxweightindex = -1;
119  	   maxweight = 0;
120  	
121  	   /* try to improve maxweight */
122  	   for( i = 0 ; i < nV; i++ )
123  	   {
124  	      assert(0 <= V[i] && V[i] < getnnodes(tcliquegraph));
125  	      assert(weights[V[i]] > 0);
126  	      if( weights[V[i]] > maxweight)
127  	      {
128  	         /* node has larger weight */
129  	         maxweight = weights[V[i]];
130  	         maxweightindex = i;
131  	      }
132  	   }
133  	   assert(maxweightindex >= 0);
134  	
135  	   return maxweightindex;
136  	}
137  	
138  	/** updates the neighbor colors information of a node: updates the list of neighbor color intervals
139  	 *  by making the union of the existing list and the given list of color intervals, and updates the saturation degree
140  	 */
141  	static
142  	void updateNeighbor(
143  	   BMS_CHKMEM*           mem,                /**< block memory */
144  	   NBC*                  pgsd,               /**< pointer to neighbor color information of node to update */
145  	   LIST_ITV*             pnc                 /**< pointer to given list of color intervals */
146  	   )
147  	{
148  	   LIST_ITV head;
149  	   LIST_ITV* apciv;
150  	   LIST_ITV* pciv;
151  	   LIST_ITV* nciv;
152  	
153  	   /* save the pointer to the first element of the list */
154  	   head.next = pgsd->lcitv;
155  	   apciv = &head;
156  	   pciv = apciv->next;
157  	
158  	   /* construct the union of the two intervals */
159  	   while( (pnc != NULL) && (pciv != NULL) )
160  	   {
161  	      if( pnc->itv.inf < pciv->itv.inf )
162  	      {
163  	         ALLOC_ABORT( BMSallocChunkMemory(mem, &nciv) );
164  	         nciv->itv = pnc->itv;
165  	         nciv->next = pciv;
166  	         apciv->next = nciv;
167  	         apciv = nciv;
168  	
169  	         pnc = pnc->next;
170  	      }
171  	      else if( pnc->itv.inf <= pciv->itv.sup )
172  	      {
173  	         if( pnc->itv.sup > pciv->itv.sup )
174  	            pciv->itv.sup = pnc->itv.sup;
175  	         pnc = pnc->next;
176  	      }
177  	      else
178  	      {
179  	         apciv = pciv;
180  	         pciv = pciv->next;
181  	      }
182  	   }
183  	
184  	   while( pnc != NULL )
185  	   {
186  	      ALLOC_ABORT( BMSallocChunkMemory(mem, &nciv) );
187  	      nciv->itv = pnc->itv;
188  	      nciv->next = NULL;
189  	
190  	      apciv->next = nciv;
191  	      apciv = nciv;
192  	
193  	      pnc = pnc->next;
194  	   }
195  	
196  	   /* try to reduce the number of intervals */
197  	   pgsd->satdeg = 0;
198  	   apciv = head.next;
199  	   while( (pciv = apciv->next) != NULL ) /*lint !e838*/
200  	   {
201  	      if( apciv->itv.sup < (pciv->itv.inf - 1) )
202  	      {
203  	         pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
204  	         apciv = apciv->next;
205  	      }
206  	      else
207  	      {
208  	         LIST_ITV* tmp;
209  	
210  	         if( apciv->itv.sup < pciv->itv.sup )
211  	            apciv->itv.sup = pciv->itv.sup;
212  	         apciv->next = pciv->next;
213  	
214  	         /* free data structure for created colorinterval */
215  	         tmp = pciv->next;
216  	         /* coverity[double_free] */
217  	         BMSfreeChunkMemory(mem, &pciv);
218  	         pciv = tmp;
219  	      }
220  	   }
221  	   pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
222  	
223  	   /* updates the pointer to the first element of the list */
224  	   pgsd->lcitv = head.next;
225  	}
226  	
227  	/** colors the positive weighted nodes of a given set of nodes V with the lowest possible number of colors and
228  	 *  finds a clique in the graph induced by V, an upper bound and an apriori bound for further branching steps
229  	 */
230  	TCLIQUE_WEIGHT tcliqueColoring(
231  	   TCLIQUE_GETNNODES((*getnnodes)),          /**< user function to get the number of nodes */
232  	   TCLIQUE_GETWEIGHTS((*getweights)),        /**< user function to get the node weights */
233  	   TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
234  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< pointer to graph data structure */
235  	   BMS_CHKMEM*           mem,                /**< block memory */
236  	   int*                  buffer,             /**< buffer of size nnodes */
237  	   int*                  V,                  /**< non-zero weighted nodes for branching */
238  	   int                   nV,                 /**< number of non-zero weighted nodes for branching */
239  	   NBC*                  gsd,                /**< neighbor color information of all nodes */
240  	   TCLIQUE_Bool*         iscolored,          /**< coloring status of all nodes */
241  	   TCLIQUE_WEIGHT*       apbound,            /**< pointer to store apriori bound of nodes for branching */
242  	   int*                  clique,             /**< buffer for storing the clique */
243  	   int*                  nclique,            /**< pointer to store number of nodes in the clique */
244  	   TCLIQUE_WEIGHT*       weightclique        /**< pointer to store the weight of the clique */
245  	   )
246  	{
247  	   const TCLIQUE_WEIGHT* weights;
248  	   TCLIQUE_WEIGHT maxsatdegree;
249  	   TCLIQUE_WEIGHT range;
250  	   TCLIQUE_Bool growclique;
251  	   int node;
252  	   int nodeVindex;
253  	   int i;
254  	   int j;
255  	   LIST_ITV* colorinterval;
256  	   LIST_ITV nwcitv;
257  	   LIST_ITV* pnc;
258  	   LIST_ITV* lcitv;
259  	   LIST_ITV* item;
260  	   LIST_ITV* tmpitem;
261  	   int* workclique;
262  	   int* currentclique;
263  	   int ncurrentclique;
264  	   int weightcurrentclique;
265  	   int* Vadj;
266  	   int nVadj;
267  	   int adjidx;
268  	
269  	   assert(getnnodes != NULL);
270  	   assert(getweights != NULL);
271  	   assert(selectadjnodes != NULL);
272  	   assert(buffer != NULL);
273  	   assert(V != NULL);
274  	   assert(nV > 0);
275  	   assert(clique != NULL);
276  	   assert(nclique != NULL);
277  	   assert(weightclique != NULL);
278  	   assert(gsd != NULL);
279  	   assert(iscolored != NULL);
280  	
281  	   weights = getweights(tcliquegraph);
282  	   assert(weights != NULL);
283  	
284  	   /* initialize maximum weight clique found so far */
285  	   growclique = TRUE;
286  	   *nclique = 0;
287  	   *weightclique = 0;
288  	
289  	   /* get node of V with maximum weight */
290  	   nodeVindex = getMaxWeightIndex(getnnodes, getweights, tcliquegraph, V, nV);
291  	   node = V[nodeVindex];
292  	   assert(0 <= node && node < getnnodes(tcliquegraph));
293  	   range = weights[node];
294  	   assert(range > 0);
295  	
296  	   /* set up data structures for coloring */
297  	   BMSclearMemoryArray(iscolored, nV); /* new-memory */
298  	   BMSclearMemoryArray(gsd, nV); /* new-memory */
299  	   iscolored[nodeVindex] = TRUE;
300  	
301  	   /* color the first node */
302  	   debugMessage("---------------coloring-----------------\n");
303  	   debugMessage("1. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d)\n",
304  	      nodeVindex, node, gsd[nodeVindex].satdeg, range);
305  	
306  	   /* set apriori bound: apbound(v_i) = satdeg(v_i) + weight(v_i) */
307  	   apbound[nodeVindex] = range;
308  	   assert(apbound[nodeVindex] > 0);
309  	
310  	   /* update maximum saturation degree: maxsatdeg = max { satdeg(v_i) + weight(v_i) | v_i in V } */
311  	   maxsatdegree = range;
312  	
313  	   debugMessage("-> updated neighbors:\n");
314  	
315  	   /* set neighbor color of the adjacent nodes of node */
316  	   Vadj = buffer;
317  	   nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
318  	   for( i = 0, adjidx = 0; i < nV && adjidx < nVadj; ++i )
319  	   {
320  	      assert(V[i] <= Vadj[adjidx]); /* Vadj is a subset of V */
321  	      if( V[i] == Vadj[adjidx] )
322  	      {
323  	         /* node is adjacent to itself, but we do not need to color it again */
324  	         if( i == nodeVindex )
325  	         {
326  	            /* go to the next node in Vadj */
327  	            adjidx++;
328  	            continue;
329  	         }
330  	
331  	         debugMessage("     nodeVindex=%d, node=%d, weight=%d, satdegold=%d  ->  ",
332  	            i, V[i], weights[V[i]], gsd[i].satdeg);
333  	
334  	         /* sets satdeg for adjacent node */
335  	         gsd[i].satdeg = range;
336  	
337  	         /* creates new color interval [1,range] */
338  	         ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) );
339  	         colorinterval->next = NULL;
340  	         colorinterval->itv.inf = 1;
341  	         colorinterval->itv.sup = range;
342  	
343  	         /* colorinterval is the first added element of the list of neighborcolors of the adjacent node  */
344  	         gsd[i].lcitv = colorinterval;
345  	
346  	         /* go to the next node in Vadj */
347  	         adjidx++;
348  	
349  	         debugPrintf("satdegnew=%d, nbc=[%d,%d]\n", gsd[i].satdeg, gsd[i].lcitv->itv.inf, gsd[i].lcitv->itv.sup);
350  	      }
351  	   }
352  	
353  	   /* set up data structures for the current clique */
354  	   ALLOC_ABORT( BMSallocMemoryArray(&currentclique, nV) );
355  	   workclique = clique;
356  	
357  	   /* add node to the current clique */
358  	   currentclique[0] = node;
359  	   ncurrentclique = 1;
360  	   weightcurrentclique = range;
361  	
362  	   /* color all other nodes of V */
363  	   for( i = 0 ; i < nV-1; i++ )
364  	   {
365  	      assert((workclique == clique) != (currentclique == clique));
366  	
367  	      /* selects the next uncolored node to color */
368  	      nodeVindex = getMaxSatdegIndex(V, nV, gsd, iscolored, weights);
369  	      if( nodeVindex == -1 ) /* no uncolored nodes left */
370  	         break;
371  	
372  	      node = V[nodeVindex];
373  	      assert(0 <= node && node < getnnodes(tcliquegraph));
374  	      range = weights[node];
375  	      assert(range > 0);
376  	      iscolored[nodeVindex] = TRUE;
377  	
378  	      debugMessage("%d. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d, growclique=%u, weight=%d)\n",
379  	         i+2, nodeVindex, node, gsd[nodeVindex].satdeg, range, growclique, weightcurrentclique);
380  	
381  	      /* set apriori bound: apbound(v_i) = satdeg(v_i) + weight(v_i) */
382  	      apbound[nodeVindex] = gsd[nodeVindex].satdeg + range;
383  	      assert(apbound[nodeVindex] > 0);
384  	
385  	      /* update maximum saturation degree: maxsatdeg = max { satdeg(v_i) + weight(v_i) | v_i in V } */
386  	      if( maxsatdegree < apbound[nodeVindex] )
387  	         maxsatdegree = apbound[nodeVindex];
388  	
389  	      /* update clique */
390  	      if( gsd[nodeVindex].satdeg == 0 )
391  	      {
392  	         /* current node is not adjacent to nodes of current clique,
393  	          * i.e. current clique can not be increased
394  	          */
395  	         debugMessage("current node not adjacend to current clique (weight:%d) -> starting new clique\n",
396  	            weightcurrentclique);
397  	
398  	         /* check, if weight of current clique is larger than weight of maximum weight clique found so far */
399  	         if( weightcurrentclique > *weightclique )
400  	         {
401  	            int* tmp;
402  	
403  	            /* update maximum weight clique found so far */
404  	            assert((workclique == clique) != (currentclique == clique));
405  	            tmp = workclique;
406  	            *weightclique = weightcurrentclique;
407  	            *nclique = ncurrentclique;
408  	            workclique = currentclique;
409  	            currentclique = tmp;
410  	            assert((workclique == clique) != (currentclique == clique));
411  	         }
412  	         weightcurrentclique = 0;
413  	         ncurrentclique = 0;
414  	         growclique = TRUE;
415  	      }
416  	      if( growclique )
417  	      {
418  	         /* check, if the current node is still adjacent to all nodes in the clique */
419  	         if( gsd[nodeVindex].satdeg == weightcurrentclique )
420  	         {
421  	            assert(ncurrentclique < nV);
422  	            currentclique[ncurrentclique] = node;
423  	            ncurrentclique++;
424  	            weightcurrentclique += range;
425  	#ifdef TCLIQUE_DEBUG
426  	            {
427  	               int k;
428  	               debugMessage("current clique (size:%d, weight:%d):", ncurrentclique, weightcurrentclique);
429  	               for( k = 0; k < ncurrentclique; ++k )
430  	                  debugPrintf(" %d", currentclique[k]);
431  	               debugPrintf("\n");
432  	            }
433  	#endif
434  	         }
435  	         else
436  	         {
437  	            debugMessage("node satdeg: %d, clique weight: %d -> stop growing clique\n",
438  	               gsd[nodeVindex].satdeg, weightcurrentclique);
439  	            growclique = FALSE;
440  	         }
441  	      }
442  	
443  	      /* search for fitting color intervals for current node */
444  	      pnc = &nwcitv;
445  	      if( gsd[nodeVindex].lcitv == NULL )
446  	      {
447  	         /* current node has no colored neighbors yet: create new color interval [1,range] */
448  	         ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) );
449  	         colorinterval->next = NULL;
450  	         colorinterval->itv.inf = 1;
451  	         colorinterval->itv.sup = range;
452  	
453  	         /* add the new colorinterval [1, range] to the list of chosen colorintervals for node */
454  	         pnc->next = colorinterval;
455  	      }
456  	      else
457  	      {
458  	         int tocolor;
459  	         int dif;
460  	
461  	         /* current node has colored neighbors */
462  	         tocolor = range;
463  	         lcitv = gsd[nodeVindex].lcitv;
464  	
465  	         /* check, if first neighbor color interval [inf, sup] has inf > 1 */
466  	         if( lcitv->itv.inf != 1 )
467  	         {
468  	            /* create new interval [1, min{range, inf}] */
469  	            dif =  lcitv->itv.inf - 1 ;
470  	            if( dif > tocolor )
471  	               dif = tocolor;
472  	
473  	            ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) );
474  	            colorinterval->next = NULL;
475  	            colorinterval->itv.inf = 1;
476  	            colorinterval->itv.sup = dif;
477  	
478  	            tocolor -= dif;
479  	            pnc->next = colorinterval;
480  	            pnc = colorinterval;
481  	         }
482  	
483  	         /* as long as node is not colored with all colors, create new color interval by filling
484  	          * the gaps in the existing neighbor color intervals of the neighbors of node
485  	          */
486  	         while( tocolor > 0 )
487  	         {
488  	            dif = tocolor;
489  	
490  	            ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) );
491  	            colorinterval->next = NULL;
492  	            colorinterval->itv.inf = lcitv->itv.sup+1;
493  	            if( lcitv->next != NULL )
494  	            {
495  	               int min;
496  	
497  	               min = lcitv->next->itv.inf - lcitv->itv.sup - 1;
498  	
499  	               if( dif > min )
500  	                  dif = min;
501  	               lcitv = lcitv->next;
502  	            }
503  	            colorinterval->itv.sup = colorinterval->itv.inf + dif - 1;
504  	
505  	            tocolor -= dif;
506  	            pnc->next = colorinterval;
507  	            pnc = colorinterval;
508  	         }
509  	      }
510  	
511  	      debugMessage("-> updated neighbors:\n");
512  	
513  	      /* update saturation degree and neighbor colorintervals of all neighbors of node */
514  	      Vadj = buffer;
515  	      nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
516  	      for( j = 0, adjidx = 0; j < nV && adjidx < nVadj; ++j )
517  	      {
518  	         assert(V[j] <= Vadj[adjidx]); /* Vadj is a subset of V */
519  	         if( V[j] == Vadj[adjidx] )
520  	         {
521  	            if( !iscolored[j] )
522  	            {
523  	               debugMessage("     nodeVindex=%d, node=%d, weight=%d, satdegold=%d  ->  ",
524  	                  j, V[j], weights[V[j]], gsd[j].satdeg);
525  	               updateNeighbor(mem, &gsd[j], nwcitv.next);
526  	               debugPrintf("satdegnew=%d, nbc=[%d,%d]\n", gsd[j].satdeg, gsd[j].lcitv->itv.inf, gsd[j].lcitv->itv.sup);
527  	            }
528  	
529  	            /* go to the next node in Vadj */
530  	            adjidx++;
531  	         }
532  	      }
533  	
534  	      /* free data structure of created colorintervals */
535  	      item = nwcitv.next;
536  	      while( item != NULL )
537  	      {
538  	         tmpitem = item->next;
539  	         /* coverity[double_free] */
540  	         BMSfreeChunkMemory(mem, &item);
541  	         item = tmpitem;
542  	      }
543  	
544  	      /* free data structure of neighbor colorinterval of node just colored */
545  	      item = gsd[nodeVindex].lcitv;
546  	      while( item != NULL )
547  	      {
548  	         tmpitem = item->next;
549  	         /* coverity[double_free] */
550  	         BMSfreeChunkMemory(mem, &item);
551  	         item = tmpitem;
552  	      }
553  	   }
554  	   assert((workclique == clique) != (currentclique == clique));
555  	
556  	   /* update maximum weight clique found so far */
557  	   if( weightcurrentclique > *weightclique )
558  	   {
559  	      int* tmp;
560  	
561  	      tmp = workclique;
562  	      *weightclique = weightcurrentclique;
563  	      *nclique = ncurrentclique;
564  	      workclique = currentclique;
565  	      currentclique = tmp;
566  	   }
567  	   assert((workclique == clique) != (currentclique == clique));
568  	
569  	   /* move the found clique to the provided clique pointer, if it is not the memory array */
570  	   if( workclique != clique )
571  	   {
572  	      assert(clique == currentclique);
573  	      assert(*nclique <= nV);
574  	      BMScopyMemoryArray(clique, workclique, *nclique);
575  	      currentclique = workclique;
576  	   }
577  	
578  	   /* free data structures */
579  	   BMSfreeMemoryArray(&currentclique);
580  	
581  	   /* clear chunk memory */
582  	   BMSclearChunkMemory(mem);
583  	
584  	   debugMessage("------------coloringend-----------------\n");
585  	
586  	   return maxsatdegree;
587  	}
588