Scippy

SCIP

Solving Constraint Integer Programs

tclique_coloring.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* TCLIQUE --- Algorithm for Maximum Cliques */
5 /* */
6 /* Copyright (c) 1996-2024 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"
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
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
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
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  */
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 }
#define TCLIQUE_GETWEIGHTS(x)
Definition: tclique.h:105
#define NULL
Definition: def.h:267
struct BMS_ChkMem BMS_CHKMEM
Definition: memory.h:302
tclique defines
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
#define BMSclearChunkMemory(mem)
Definition: memory.h:308
#define TCLIQUE_SELECTADJNODES(x)
Definition: tclique.h:130
#define ALLOC_ABORT(x)
Definition: tclique_def.h:50
#define debugPrintf
Definition: tclique_def.h:81
#define FALSE
Definition: def.h:94
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:93
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:123
tclique user interface
#define debugMessage
Definition: tclique_def.h:80
coloring part of algorithm for maximum cliques
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:147
static int getMaxWeightIndex(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_GRAPH *tcliquegraph, int *V, int nV)
#define TCLIQUE_Bool
Definition: tclique.h:53
static int getMaxSatdegIndex(int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, const TCLIQUE_WEIGHT *weights)
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
static void updateNeighbor(BMS_CHKMEM *mem, NBC *pgsd, LIST_ITV *pnc)
struct _NBC NBC
#define TCLIQUE_GETNNODES(x)
Definition: tclique.h:97
#define BMSallocChunkMemory(mem, ptr)
Definition: memory.h:311
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
#define BMSfreeChunkMemory(mem, ptr)
Definition: memory.h:314
int TCLIQUE_WEIGHT
Definition: tclique.h:48
struct _LIST_ITV LIST_ITV
memory allocation routines