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