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  BMSfreeChunkMemory(mem, &pciv);
208  pciv = tmp;
209  }
210  }
211  pgsd->satdeg += apciv->itv.sup - apciv->itv.inf + 1;
212 
213  /* updates the pointer to the first element of the list */
214  pgsd->lcitv = head.next;
215 }
216 
217 /** colors the positive weighted nodes of a given set of nodes V with the lowest possible number of colors and
218  * finds a clique in the graph induced by V, an upper bound and an apriori bound for further branching steps
219  */
221  TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
222  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
223  TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
224  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
225  BMS_CHKMEM* mem, /**< block memory */
226  int* buffer, /**< buffer of size nnodes */
227  int* V, /**< non-zero weighted nodes for branching */
228  int nV, /**< number of non-zero weighted nodes for branching */
229  NBC* gsd, /**< neighbor color information of all nodes */
230  TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
231  TCLIQUE_WEIGHT* apbound, /**< pointer to store apriori bound of nodes for branching */
232  int* clique, /**< buffer for storing the clique */
233  int* nclique, /**< pointer to store number of nodes in the clique */
234  TCLIQUE_WEIGHT* weightclique /**< pointer to store the weight of the clique */
235  )
236 {
237  const TCLIQUE_WEIGHT* weights;
238  TCLIQUE_WEIGHT maxsatdegree;
239  TCLIQUE_WEIGHT range;
240  TCLIQUE_Bool growclique;
241  int node;
242  int nodeVindex;
243  int i;
244  int j;
245  LIST_ITV* colorinterval;
246  LIST_ITV nwcitv;
247  LIST_ITV* pnc;
248  LIST_ITV* lcitv;
249  LIST_ITV* item;
250  LIST_ITV* tmpitem;
251  int* workclique;
252  int* currentclique;
253  int ncurrentclique;
254  int weightcurrentclique;
255  int* Vadj;
256  int nVadj;
257  int adjidx;
258 
259  assert(getnnodes != NULL);
260  assert(getweights != NULL);
261  assert(selectadjnodes != NULL);
262  assert(buffer != NULL);
263  assert(V != NULL);
264  assert(nV > 0);
265  assert(clique != NULL);
266  assert(nclique != NULL);
267  assert(weightclique != NULL);
268  assert(gsd != NULL);
269  assert(iscolored != NULL);
270 
271  weights = getweights(tcliquegraph);
272  assert(weights != NULL);
273 
274  /* initialize maximum weight clique found so far */
275  growclique = TRUE;
276  *nclique = 0;
277  *weightclique = 0;
278 
279  /* get node of V with maximum weight */
280  nodeVindex = getMaxWeightIndex(getnnodes, getweights, tcliquegraph, V, nV);
281  node = V[nodeVindex];
282  assert(0 <= node && node < getnnodes(tcliquegraph));
283  range = weights[node];
284  assert(range > 0);
285 
286  /* set up data structures for coloring */
287  BMSclearMemoryArray(iscolored, nV); /* new-memory */
288  BMSclearMemoryArray(gsd, nV); /* new-memory */
289  iscolored[nodeVindex] = TRUE;
290 
291  /* color the first node */
292  debugMessage("---------------coloring-----------------\n");
293  debugMessage("1. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d)\n",
294  nodeVindex, node, gsd[nodeVindex].satdeg, range);
295 
296  /* set apriori bound: apbound(v_i) = satdeg(v_i) + weight(v_i) */
297  apbound[nodeVindex] = range;
298  assert(apbound[nodeVindex] > 0);
299 
300  /* update maximum saturation degree: maxsatdeg = max { satdeg(v_i) + weight(v_i) | v_i in V } */
301  maxsatdegree = range;
302 
303  debugMessage("-> updated neighbors:\n");
304 
305  /* set neighbor color of the adjacent nodes of node */
306  Vadj = buffer;
307  nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
308  for( i = 0, adjidx = 0; i < nV && adjidx < nVadj; ++i )
309  {
310  assert(V[i] <= Vadj[adjidx]); /* Vadj is a subset of V */
311  if( V[i] == Vadj[adjidx] )
312  {
313  /* node is adjacent to itself, but we do not need to color it again */
314  if( i == nodeVindex )
315  {
316  /* go to the next node in Vadj */
317  adjidx++;
318  continue;
319  }
320 
321  debugMessage(" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ",
322  i, V[i], weights[V[i]], gsd[i].satdeg);
323 
324  /* sets satdeg for adjacent node */
325  gsd[i].satdeg = range;
326 
327  /* creates new color interval [1,range] */
328  ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) );
329  colorinterval->next = NULL;
330  colorinterval->itv.inf = 1;
331  colorinterval->itv.sup = range;
332 
333  /* colorinterval is the first added element of the list of neighborcolors of the adjacent node */
334  gsd[i].lcitv = colorinterval;
335 
336  /* go to the next node in Vadj */
337  adjidx++;
338 
339  debugPrintf("satdegnew=%d, nbc=[%d,%d]\n", gsd[i].satdeg, gsd[i].lcitv->itv.inf, gsd[i].lcitv->itv.sup);
340  }
341  }
342 
343  /* set up data structures for the current clique */
344  ALLOC_ABORT( BMSallocMemoryArray(&currentclique, nV) );
345  workclique = clique;
346 
347  /* add node to the current clique */
348  currentclique[0] = node;
349  ncurrentclique = 1;
350  weightcurrentclique = range;
351 
352  /* color all other nodes of V */
353  for( i = 0 ; i < nV-1; i++ )
354  {
355  assert((workclique == clique) != (currentclique == clique));
356 
357  /* selects the next uncolored node to color */
358  nodeVindex = getMaxSatdegIndex(V, nV, gsd, iscolored, weights);
359  if( nodeVindex == -1 ) /* no uncolored nodes left */
360  break;
361 
362  node = V[nodeVindex];
363  assert(0 <= node && node < getnnodes(tcliquegraph));
364  range = weights[node];
365  assert(range > 0);
366  iscolored[nodeVindex] = TRUE;
367 
368  debugMessage("%d. node choosen: vindex=%d, vertex=%d, satdeg=%d, range=%d, growclique=%u, weight=%d)\n",
369  i+2, nodeVindex, node, gsd[nodeVindex].satdeg, range, growclique, weightcurrentclique);
370 
371  /* set apriori bound: apbound(v_i) = satdeg(v_i) + weight(v_i) */
372  apbound[nodeVindex] = gsd[nodeVindex].satdeg + range;
373  assert(apbound[nodeVindex] > 0);
374 
375  /* update maximum saturation degree: maxsatdeg = max { satdeg(v_i) + weight(v_i) | v_i in V } */
376  if( maxsatdegree < apbound[nodeVindex] )
377  maxsatdegree = apbound[nodeVindex];
378 
379  /* update clique */
380  if( gsd[nodeVindex].satdeg == 0 )
381  {
382  /* current node is not adjacent to nodes of current clique,
383  * i.e. current clique can not be increased
384  */
385  debugMessage("current node not adjacend to current clique (weight:%d) -> starting new clique\n",
386  weightcurrentclique);
387 
388  /* check, if weight of current clique is larger than weight of maximum weight clique found so far */
389  if( weightcurrentclique > *weightclique )
390  {
391  int* tmp;
392 
393  /* update maximum weight clique found so far */
394  assert((workclique == clique) != (currentclique == clique));
395  tmp = workclique;
396  *weightclique = weightcurrentclique;
397  *nclique = ncurrentclique;
398  workclique = currentclique;
399  currentclique = tmp;
400  assert((workclique == clique) != (currentclique == clique));
401  }
402  weightcurrentclique = 0;
403  ncurrentclique = 0;
404  growclique = TRUE;
405  }
406  if( growclique )
407  {
408  /* check, if the current node is still adjacent to all nodes in the clique */
409  if( gsd[nodeVindex].satdeg == weightcurrentclique )
410  {
411  assert(ncurrentclique < nV);
412  currentclique[ncurrentclique] = node;
413  ncurrentclique++;
414  weightcurrentclique += range;
415 #ifdef TCLIQUE_DEBUG
416  {
417  int k;
418  debugMessage("current clique (size:%d, weight:%d):", ncurrentclique, weightcurrentclique);
419  for( k = 0; k < ncurrentclique; ++k )
420  debugPrintf(" %d", currentclique[k]);
421  debugPrintf("\n");
422  }
423 #endif
424  }
425  else
426  {
427  debugMessage("node satdeg: %d, clique weight: %d -> stop growing clique\n",
428  gsd[nodeVindex].satdeg, weightcurrentclique);
429  growclique = FALSE;
430  }
431  }
432 
433  /* search for fitting color intervals for current node */
434  pnc = &nwcitv;
435  if( gsd[nodeVindex].lcitv == NULL )
436  {
437  /* current node has no colored neighbors yet: create new color interval [1,range] */
438  ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) );
439  colorinterval->next = NULL;
440  colorinterval->itv.inf = 1;
441  colorinterval->itv.sup = range;
442 
443  /* add the new colorinterval [1, range] to the list of chosen colorintervals for node */
444  pnc->next = colorinterval;
445  }
446  else
447  {
448  int tocolor;
449  int dif;
450 
451  /* current node has colored neighbors */
452  tocolor = range;
453  lcitv = gsd[nodeVindex].lcitv;
454 
455  /* check, if first neighbor color interval [inf, sup] has inf > 1 */
456  if( lcitv->itv.inf != 1 )
457  {
458  /* create new interval [1, min{range, inf}] */
459  dif = lcitv->itv.inf - 1 ;
460  if( dif > tocolor )
461  dif = tocolor;
462 
463  ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) );
464  colorinterval->next = NULL;
465  colorinterval->itv.inf = 1;
466  colorinterval->itv.sup = dif;
467 
468  tocolor -= dif;
469  pnc->next = colorinterval;
470  pnc = colorinterval;
471  }
472 
473  /* as long as node is not colored with all colors, create new color interval by filling
474  * the gaps in the existing neighbor color intervals of the neighbors of node
475  */
476  while( tocolor > 0 )
477  {
478  dif = tocolor;
479 
480  ALLOC_ABORT( BMSallocChunkMemory(mem, &colorinterval) );
481  colorinterval->next = NULL;
482  colorinterval->itv.inf = lcitv->itv.sup+1;
483  if( lcitv->next != NULL )
484  {
485  int min;
486 
487  min = lcitv->next->itv.inf - lcitv->itv.sup - 1;
488 
489  if( dif > min )
490  dif = min;
491  lcitv = lcitv->next;
492  }
493  colorinterval->itv.sup = colorinterval->itv.inf + dif - 1;
494 
495  tocolor -= dif;
496  pnc->next = colorinterval;
497  pnc = colorinterval;
498  }
499  }
500 
501  debugMessage("-> updated neighbors:\n");
502 
503  /* update saturation degree and neighbor colorintervals of all neighbors of node */
504  Vadj = buffer;
505  nVadj = selectadjnodes(tcliquegraph, node, V, nV, Vadj);
506  for( j = 0, adjidx = 0; j < nV && adjidx < nVadj; ++j )
507  {
508  assert(V[j] <= Vadj[adjidx]); /* Vadj is a subset of V */
509  if( V[j] == Vadj[adjidx] )
510  {
511  if( !iscolored[j] )
512  {
513  debugMessage(" nodeVindex=%d, node=%d, weight=%d, satdegold=%d -> ",
514  j, V[j], weights[V[j]], gsd[j].satdeg);
515  updateNeighbor(mem, &gsd[j], nwcitv.next);
516  debugPrintf("satdegnew=%d, nbc=[%d,%d]\n", gsd[j].satdeg, gsd[j].lcitv->itv.inf, gsd[j].lcitv->itv.sup);
517  }
518 
519  /* go to the next node in Vadj */
520  adjidx++;
521  }
522  }
523 
524  /* free data structure of created colorintervals */
525  item = nwcitv.next;
526  while( item != NULL )
527  {
528  tmpitem = item->next;
529  BMSfreeChunkMemory(mem, &item);
530  item = tmpitem;
531  }
532 
533  /* free data structure of neighbor colorinterval of node just colored */
534  item = gsd[nodeVindex].lcitv;
535  while( item != NULL )
536  {
537  tmpitem = item->next;
538  BMSfreeChunkMemory(mem, &item);
539  item = tmpitem;
540  }
541  }
542  assert((workclique == clique) != (currentclique == clique));
543 
544  /* update maximum weight clique found so far */
545  if( weightcurrentclique > *weightclique )
546  {
547  int* tmp;
548 
549  tmp = workclique;
550  *weightclique = weightcurrentclique;
551  *nclique = ncurrentclique;
552  workclique = currentclique;
553  currentclique = tmp;
554  }
555  assert((workclique == clique) != (currentclique == clique));
556 
557  /* move the found clique to the provided clique pointer, if it is not the memory array */
558  if( workclique != clique )
559  {
560  assert(clique == currentclique);
561  assert(*nclique <= nV);
562  BMScopyMemoryArray(clique, workclique, *nclique);
563  currentclique = workclique;
564  }
565 
566  /* free data structures */
567  BMSfreeMemoryArray(&currentclique);
568 
569  /* clear chunk memory */
570  BMSclearChunkMemory(mem);
571 
572  debugMessage("------------coloringend-----------------\n");
573 
574  return maxsatdegree;
575 }
#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