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