Scippy

SCIP

Solving Constraint Integer Programs

tclique_graph.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-2021 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_graph.c
17  * @ingroup OTHER_CFILES
18  * @brief graph data 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 <string.h>
29 #include <assert.h>
30 
31 #include "tclique/tclique.h"
32 #include "tclique/tclique_def.h"
33 #include "blockmemshell/memory.h"
34 
35 
36 typedef struct _HEAD_ADJ
37 {
38  int first;
39  int last;
40 } HEAD_ADJ;
41 
42 struct TCLIQUE_Graph
43 {
44  int nnodes; /**< number of nodes in graph */
45  int nedges; /**< number of edges in graph */
46  TCLIQUE_WEIGHT* weights; /**< weight of nodes */
47  int* degrees; /**< degree of nodes */
48  int* adjnodes; /**< adjacent nodes of edges */
49  HEAD_ADJ* adjedges; /**< pointer to first and one after last adjacent edge of nodes */
50  int sizenodes; /**< size of arrays concerning nodes (weights, degrees and adjedges) */
51  int sizeedges; /**< size of arrays concerning edges (adjnodes) */
52  int* cacheddegrees; /**< number of adjacent cached edges for each node */
53  int* cachedorigs; /**< origin nodes of cached edges */
54  int* cacheddests; /**< destination nodes of cached edges */
55  int ncachededges; /**< number of cached edges (not yet inserted in all data structures) */
56  int sizecachededges; /**< size of arrays concerning cached edges */
57 };
58 
59 
60 
61 
62 /*
63  * Interface Methods used by the TClique algorithm
64  */
65 
66 /** gets number of nodes in the graph */
67 TCLIQUE_GETNNODES(tcliqueGetNNodes)
68 {
69  assert(tcliquegraph != NULL);
70 
71  return tcliquegraph->nnodes;
72 }
73 
74 /** gets weight of nodes in the graph */
75 TCLIQUE_GETWEIGHTS(tcliqueGetWeights)
76 {
77  assert(tcliquegraph != NULL);
78 
79  return tcliquegraph->weights;
80 }
81 
82 /** returns, whether the edge (node1, node2) is in the graph */
83 TCLIQUE_ISEDGE(tcliqueIsEdge)
84 {
85  int* currentadjedge;
86  int* lastadjedge;
87  int tmp;
88 
89  assert(tcliquegraph != NULL);
90  assert(tcliquegraph->ncachededges == 0);
91  assert(0 <= node1 && node1 < tcliquegraph->nnodes);
92  assert(0 <= node2 && node2 < tcliquegraph->nnodes);
93 
94  if( node1 < node2 )
95  {
96  tmp = node1;
97  node1 = node2;
98  node2 = tmp;
99  }
100 
101  currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, node1);
102  lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, node1);
103 
104  if( currentadjedge > lastadjedge || *lastadjedge < node2 )
105  return FALSE;
106 
107  /* checks if node2 is contained in adjacency list of node1
108  * (list is ordered by adjacent nodes) */
109  while( currentadjedge <= lastadjedge )
110  {
111  if( *currentadjedge >= node2 )
112  {
113  if( *currentadjedge == node2 )
114  return TRUE;
115  else
116  break;
117  }
118  currentadjedge++;
119  }
120 
121  return FALSE;
122 }
123 
124 /** selects all nodes from a given set of nodes which are adjacent to a given node
125  * and returns the number of selected nodes */
126 TCLIQUE_SELECTADJNODES(tcliqueSelectAdjnodes)
127 {
128  int nadjnodes;
129  int* currentadjedge;
130  int* lastadjedge;
131  int i;
132 
133  assert(tcliquegraph != NULL);
134  assert(tcliquegraph->ncachededges == 0);
135  assert(0 <= node && node < tcliquegraph->nnodes);
136  assert(nnodes == 0 || nodes != NULL);
137  assert(adjnodes != NULL);
138 
139  nadjnodes = 0;
140  currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, node);
141  lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, node);
142 
143  /* checks for each node in given set nodes, if it is adjacent to given node
144  * (adjacent nodes are ordered by node index)
145  */
146  for( i = 0; i < nnodes; i++ )
147  {
148  assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
149  assert(i == 0 || nodes[i-1] < nodes[i]);
150  for( ; currentadjedge <= lastadjedge; currentadjedge++ )
151  {
152  if( *currentadjedge >= nodes[i] )
153  {
154  /* current node is adjacent to given node */
155  if( *currentadjedge == nodes[i] )
156  {
157  adjnodes[nadjnodes] = nodes[i];
158  nadjnodes++;
159  }
160  break;
161  }
162  }
163  }
164 
165  return nadjnodes;
166 }
167 
168 
169 
170 
171 /*
172  * External Interface Methods to access the graph (this can be changed without affecting the TClique algorithm)
173  */
174 
175 /** creates graph data structure */
177  TCLIQUE_GRAPH** tcliquegraph /**< pointer to store graph data structure */
178  )
179 {
180  assert(tcliquegraph != NULL);
181 
182  ALLOC_FALSE( BMSallocMemory(tcliquegraph) );
183 
184  (*tcliquegraph)->nnodes = 0;
185  (*tcliquegraph)->nedges = 0;
186  (*tcliquegraph)->weights = NULL;
187  (*tcliquegraph)->degrees = NULL;
188  (*tcliquegraph)->adjnodes = NULL;
189  (*tcliquegraph)->adjedges = NULL;
190  (*tcliquegraph)->sizenodes = 0;
191  (*tcliquegraph)->sizeedges = 0;
192  (*tcliquegraph)->cacheddegrees = NULL;
193  (*tcliquegraph)->cachedorigs = NULL;
194  (*tcliquegraph)->cacheddests = NULL;
195  (*tcliquegraph)->ncachededges = 0;
196  (*tcliquegraph)->sizecachededges = 0;
197 
198  return TRUE;
199 }
200 
201 /** frees graph data structure */
203  TCLIQUE_GRAPH** tcliquegraph /**< pointer to graph data structure */
204  )
205 {
206  assert(tcliquegraph != NULL);
207 
208  if( *tcliquegraph != NULL )
209  {
210  if ( (*tcliquegraph)->adjedges != NULL )
211  {
212  BMSfreeMemoryArray(&(*tcliquegraph)->adjedges);
213  BMSfreeMemoryArray(&(*tcliquegraph)->adjnodes);
214  BMSfreeMemoryArray(&(*tcliquegraph)->degrees);
215  BMSfreeMemoryArray(&(*tcliquegraph)->weights);
216  }
217  if ( (*tcliquegraph)->cacheddegrees )
218  {
219  BMSfreeMemoryArrayNull(&(*tcliquegraph)->cacheddegrees);
220  BMSfreeMemoryArrayNull(&(*tcliquegraph)->cachedorigs);
221  BMSfreeMemoryArrayNull(&(*tcliquegraph)->cacheddests);
222  }
223  BMSfreeMemory(tcliquegraph);
224  }
225 }
226 
227 /** ensures, that arrays concerning edges in graph data structure can store at least num entries */
228 static
230  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
231  int num /**< minimum number of entries concerning edges to store */
232  )
233 {
234  assert(tcliquegraph != NULL);
235 
236  if( num > tcliquegraph->sizeedges )
237  {
238  int newsize;
239 
240  newsize = 2*tcliquegraph->sizeedges;
241  if( newsize < num )
242  newsize = num;
243 
244  ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->adjnodes, newsize) );
245  tcliquegraph->sizeedges = newsize;
246  }
247 
248  assert(num <= tcliquegraph->sizeedges);
249 
250  return TRUE;
251 }
252 
253 /** ensures, that arrays concerning cached edges in graph data structure can store at least num entries */
254 static
256  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
257  int num /**< minimum number of entries concerning cached edges to store */
258  )
259 {
260  assert(tcliquegraph != NULL);
261 
262  if( num > tcliquegraph->sizecachededges )
263  {
264  int newsize;
265 
266  newsize = 2*tcliquegraph->sizecachededges;
267  if( newsize < num )
268  newsize = num;
269 
270  ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->cachedorigs, newsize) );
271  ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->cacheddests, newsize) );
272  tcliquegraph->sizecachededges = newsize;
273  }
274 
275  assert(num <= tcliquegraph->sizecachededges);
276 
277  return TRUE;
278 }
279 
280 /** ensures, that arrays concerning nodes in graph data structure can store at least num entries */
281 static
283  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
284  int num /**< minimum number of entries concerning nodes to store */
285  )
286 {
287  assert(tcliquegraph != NULL);
288 
289  if( !tcliqueEnsureSizeEdges(tcliquegraph, 1) )
290  return FALSE;
291  assert(tcliquegraph->adjnodes != NULL);
292 
293  if( num > tcliquegraph->sizenodes )
294  {
295  int newsize;
296  int i;
297 
298  newsize = 2*tcliquegraph->sizenodes;
299  if( newsize < num )
300  newsize = num;
301 
302  ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->weights, newsize) );
303  ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->degrees, newsize) );
304  ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->adjedges, newsize) );
305 
306  for( i = tcliquegraph->sizenodes; i < newsize; i++ )
307  {
308  tcliquegraph->weights[i] = 0;
309  tcliquegraph->degrees[i] = 0;
310  tcliquegraph->adjedges[i].first = tcliquegraph->nedges;
311  tcliquegraph->adjedges[i].last = tcliquegraph->nedges;
312  }
313 
314  if( tcliquegraph->ncachededges > 0 )
315  {
316  assert(tcliquegraph->cacheddegrees != NULL);
317  ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->cacheddegrees, newsize) );
318  for( i = tcliquegraph->sizenodes; i < newsize; i++ )
319  tcliquegraph->cacheddegrees[i] = 0;
320  }
321 
322  tcliquegraph->sizenodes = newsize;
323  }
324  assert(num <= tcliquegraph->sizenodes);
325 
326  return TRUE;
327 }
328 
329 
330 /** adds nodes up to the given node number to graph data structure (intermediate nodes have weight 0) */
332  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
333  int node, /**< node number to add */
334  TCLIQUE_WEIGHT weight /**< weight of node to add */
335  )
336 {
337  assert(weight >= 0);
338 
339  if( !tcliqueEnsureSizeNodes(tcliquegraph, node + 1) )
340  return FALSE;
341 
342  tcliquegraph->weights[node] = weight;
343 
344  assert(tcliquegraph->degrees[node] == 0);
345  assert(tcliquegraph->adjedges[node].first <= tcliquegraph->nedges);
346  assert(tcliquegraph->adjedges[node].last == tcliquegraph->adjedges[node].first);
347  tcliquegraph->nnodes = MAX(tcliquegraph->nnodes, node+1);
348 
349  return TRUE;
350 }
351 
352 /** changes weight of node in graph data structure */
354  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
355  int node, /**< node to set new weight */
356  TCLIQUE_WEIGHT weight /**< new weight of node (allready scaled) */
357  )
358 {
359  assert(0 <= node && node < tcliqueGetNNodes(tcliquegraph));
360  assert(weight >= 0);
361 
362  tcliquegraph->weights[node] = weight;
363 }
364 
365 /** adds edge (node1, node2) to graph data structure (node1 and node2 have to be contained in
366  * graph data structure)
367  *
368  * New edges are cached, s.t. the graph data structures are not correct until a call to tcliqueFlush();
369  * you have to make sure, that no double edges are inserted.
370  */
372  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
373  int node1, /**< start node of edge to add */
374  int node2 /**< end node of edge to add */
375  )
376 {
377  assert(tcliquegraph != NULL);
378  assert(0 <= node1 && node1 < tcliquegraph->nnodes);
379  assert(0 <= node2 && node2 < tcliquegraph->nnodes);
380  assert(node1 != node2);
381 
382  if( !tcliqueEnsureSizeCachedEdges(tcliquegraph, tcliquegraph->ncachededges + 2) )
383  return FALSE;
384 
385  /* make sure, the array for counting the cached node degrees exists */
386  if( tcliquegraph->ncachededges == 0 && tcliquegraph->sizenodes > 0 )
387  {
388  assert(tcliquegraph->cacheddegrees == NULL);
389  ALLOC_FALSE( BMSallocMemoryArray(&tcliquegraph->cacheddegrees, tcliquegraph->sizenodes) );
390  BMSclearMemoryArray(tcliquegraph->cacheddegrees, tcliquegraph->sizenodes);
391  }
392  assert(tcliquegraph->cacheddegrees != NULL);
393 
394  /* just remember both new half edges in the cache; the full insertion is done later on demand */
395  tcliquegraph->cachedorigs[tcliquegraph->ncachededges] = node1;
396  tcliquegraph->cacheddests[tcliquegraph->ncachededges] = node2;
397  tcliquegraph->ncachededges++;
398  tcliquegraph->cachedorigs[tcliquegraph->ncachededges] = node2;
399  tcliquegraph->cacheddests[tcliquegraph->ncachededges] = node1;
400  tcliquegraph->ncachededges++;
401  tcliquegraph->cacheddegrees[node1]++;
402  tcliquegraph->cacheddegrees[node2]++;
403 
404  return TRUE;
405 }
406 
407 /** inserts all cached edges into the data structures */
409  TCLIQUE_GRAPH* tcliquegraph /**< graph data structure */
410  )
411 {
412  assert(tcliquegraph != NULL);
413 
414  /* check, whether there are cached edges */
415  if( tcliquegraph->ncachededges > 0 )
416  {
417  int ninsertedholes;
418  int pos;
419  int n;
420  int i;
421 
422  /* reallocate adjnodes array to be able to store all additional edges */
423  if( !tcliqueEnsureSizeEdges(tcliquegraph, tcliquegraph->nedges + tcliquegraph->ncachededges) )
424  return FALSE;
425  assert(tcliquegraph->adjnodes != NULL);
426  assert(tcliquegraph->adjedges != NULL);
427 
428  /* move the old edges in the adjnodes array, s.t. there is enough free space for the additional edges */
429  ninsertedholes = 0;
430  pos = tcliquegraph->nedges + tcliquegraph->ncachededges - 1;
431  for( n = tcliquegraph->nnodes-1; ; --n ) /* no abort criterion, because at n == 0, the loop is break'ed */
432  {
433  int olddegree;
434 
435  assert(n >= 0);
436  assert(tcliquegraph->adjedges[n].last - tcliquegraph->adjedges[n].first == tcliquegraph->degrees[n]);
437 
438  /* increase the degree of the node */
439  olddegree = tcliquegraph->degrees[n];
440  tcliquegraph->degrees[n] += tcliquegraph->cacheddegrees[n];
441 
442  /* skip space for new edges */
443  pos -= tcliquegraph->cacheddegrees[n];
444  ninsertedholes += tcliquegraph->cacheddegrees[n];
445  assert(ninsertedholes <= tcliquegraph->ncachededges);
446  if( ninsertedholes == tcliquegraph->ncachededges )
447  break;
448  assert(n > 0);
449 
450  /* move old edges */
451  for( i = tcliquegraph->adjedges[n].last - 1; i >= tcliquegraph->adjedges[n].first; --i, --pos )
452  {
453  assert(0 <= i && i < pos && pos < tcliquegraph->nedges + tcliquegraph->ncachededges);
454  tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[i];
455  }
456 
457  /* adjust the first and last edge pointers of the node */
458  tcliquegraph->adjedges[n].first = pos+1;
459  tcliquegraph->adjedges[n].last = pos+1 + olddegree;
460 
461  assert(n == tcliquegraph->nnodes-1
462  || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
463  }
464  assert(ninsertedholes == tcliquegraph->ncachededges);
465  assert(tcliquegraph->adjedges[n].last == pos+1);
466 #ifndef NDEBUG
467  for( --n; n >= 0; --n )
468  assert(tcliquegraph->cacheddegrees[n] == 0);
469 #endif
470 
471  /* insert the cached edges into the adjnodes array */
472  for( i = 0; i < tcliquegraph->ncachededges; ++i )
473  {
474  int dest;
475 
476  n = tcliquegraph->cachedorigs[i];
477  dest = tcliquegraph->cacheddests[i];
478  assert(0 <= n && n < tcliquegraph->nnodes);
479  assert(0 <= dest && dest < tcliquegraph->nnodes);
480  assert(tcliquegraph->adjedges[n].last <= tcliquegraph->nedges + tcliquegraph->ncachededges);
481  assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
482  assert(n == tcliquegraph->nnodes-1
483  || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
484 
485  /* edges of each node must be sorted by increasing destination node number */
486  for( pos = tcliquegraph->adjedges[n].last;
487  pos > tcliquegraph->adjedges[n].first && dest < tcliquegraph->adjnodes[pos-1]; --pos )
488  {
489  tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[pos-1];
490  }
491  tcliquegraph->adjnodes[pos] = dest;
492  tcliquegraph->adjedges[n].last++;
493 
494  assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
495  }
496 
497  /* update the number of edges */
498  tcliquegraph->nedges += tcliquegraph->ncachededges;
499 
500  /* free the cache */
501  BMSfreeMemoryArray(&tcliquegraph->cacheddegrees);
502  BMSfreeMemoryArray(&tcliquegraph->cachedorigs);
503  BMSfreeMemoryArray(&tcliquegraph->cacheddests);
504  tcliquegraph->ncachededges = 0;
505  tcliquegraph->sizecachededges = 0;
506  }
507 
508  /* the cache should now be freed */
509  assert(tcliquegraph->ncachededges == 0);
510  assert(tcliquegraph->sizecachededges == 0);
511  assert(tcliquegraph->cacheddegrees == NULL);
512  assert(tcliquegraph->cachedorigs == NULL);
513  assert(tcliquegraph->cacheddests == NULL);
514 
515 #ifndef NDEBUG
516  /* check integrity of the data structures */
517  {
518  int pos;
519  int n;
520 
521  pos = 0;
522  for( n = 0; n < tcliquegraph->nnodes; ++n )
523  {
524  int i;
525 
526  assert(tcliquegraph->adjedges[n].first == pos);
527  assert(tcliquegraph->adjedges[n].last == tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n]);
528 
529  for( i = tcliquegraph->adjedges[n].first; i < tcliquegraph->adjedges[n].last-1; ++i )
530  {
531  assert(tcliquegraph->adjnodes[i] < tcliquegraph->adjnodes[i+1]);
532  }
533  pos = tcliquegraph->adjedges[n].last;
534  }
535  assert(pos == tcliquegraph->nedges);
536  }
537 #endif
538 
539  return TRUE;
540 }
541 
542 /** loads graph data structure from file */
544  TCLIQUE_GRAPH** tcliquegraph, /**< pointer to store graph data structure */
545  const char* filename, /**< name of file with graph data */
546  double scaleval, /**< value to scale weights (only integral part of scaled weights is considered) */
547  char* probname, /**< buffer to store the name of the problem */
548  int sizeofprobname /**< size of buffer to store the name of the problem */
549  )
550 {
551  FILE* file;
552  double weight;
553  int node1;
554  int node2;
555  int currentnode;
556  int i;
557  int result;
558  char* charresult;
559 
560  assert(tcliquegraph != NULL);
561  assert(scaleval > 0.0);
562  assert(sizeofprobname >= 2);
563 
564  /* open file */
565  if( (file = fopen(filename, "r")) == NULL )
566  {
567  if( (file = fopen("default.dat", "r")) == NULL )
568  {
569  infoMessage("Cannot open file: %s.\n", filename);
570  return FALSE;
571  }
572  }
573 
574  if( !tcliqueCreate(tcliquegraph) )
575  {
576  (void) fclose(file);
577  return FALSE;
578  }
579 
580  /* read name of problem (if line is longer than sizeofprobname continue reading until end of line) */
581  do
582  {
583  probname[sizeofprobname-2] = '\0';
584  charresult = fgets(probname, sizeofprobname, file);
585  if( charresult == NULL )
586  {
587  infoMessage("Error while reading probname in file %s.\n", filename);
588  (void) fclose(file);
589  return FALSE;
590  }
591  }
592  while( probname[sizeofprobname-2] != '\0' );
593 
594  /* set number of nodes and number of edges in graph */
595  /* coverity[tainted_data] */
596  result = fscanf(file, "%d", &(*tcliquegraph)->nnodes);
597  if( result <= 0 )
598  {
599  infoMessage("Error while reading number of nodes in file %s.\n", filename);
600  (void) fclose(file);
601  return FALSE;
602  }
603 
604  if( (*tcliquegraph)->nnodes < 0 )
605  {
606  infoMessage("Invalid number of nodes (%d) in file: %s.\n", (*tcliquegraph)->nnodes, filename);
607  (void) fclose(file);
608  return FALSE;
609  }
610 
611  /* coverity[tainted_data] */
612  result = fscanf(file, "%d", &(*tcliquegraph)->nedges);
613  if( result <= 0 )
614  {
615  infoMessage("Error while reading number of edges in file %s.\n", filename);
616  (void) fclose(file);
617  return FALSE;
618  }
619 
620  if( (*tcliquegraph)->nedges < 0 )
621  {
622  infoMessage("Invalid number of edges (%d) in file: %s.\n", (*tcliquegraph)->nedges, filename);
623  (void) fclose(file);
624  return FALSE;
625  }
626 
627  /* set data structures for tclique,
628  * if an error occured, close the file before returning */
629  if( BMSallocMemoryArray(&(*tcliquegraph)->weights, (*tcliquegraph)->nnodes) == NULL )
630  {
631  infoMessage("Run out of memory while reading file %s.\n", filename);
632  (void) fclose(file);
633  return FALSE;
634  }
635 
636  if( BMSallocMemoryArray(&(*tcliquegraph)->degrees, (*tcliquegraph)->nnodes) == NULL )
637  {
638  infoMessage("Run out of memory while reading file %s.\n", filename);
639  (void) fclose(file);
640  return FALSE;
641  }
642 
643  if( BMSallocMemoryArray(&(*tcliquegraph)->adjnodes, (*tcliquegraph)->nedges) == NULL )
644  {
645  infoMessage("Run out of memory while reading file %s.\n", filename);
646  (void) fclose(file);
647  return FALSE;
648  }
649 
650  if( BMSallocMemoryArray(&(*tcliquegraph)->adjedges, (*tcliquegraph)->nnodes) == NULL )
651  {
652  infoMessage("Run out of memory while reading file %s.\n", filename);
653  (void) fclose(file);
654  return FALSE;
655  }
656 
657  /* set weights of all nodes (scaled!) */
658  /* coverity[tainted_data] */
659  for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
660  {
661  result = fscanf(file, "%lf", &weight);
662  if( result <= 0 )
663  {
664  infoMessage("Error while reading weights of nodes in file %s.\n", filename);
665  (void) fclose(file);
666  return FALSE;
667  }
668 
669  (*tcliquegraph)->weights[i] = (TCLIQUE_WEIGHT)(weight * scaleval);
670  assert((*tcliquegraph)->weights[i] >= 0);
671  }
672 
673  /* set adjacent edges and degree of all nodes */
674  currentnode = -1;
675  /* coverity[tainted_data] */
676  for( i = 0; i < (*tcliquegraph)->nedges; i++ )
677  {
678  /* read edge (node1, node2) */
679  /* coverity[secure_coding] */
680  result = fscanf(file, "%d%d", &node1, &node2);
681  if( result <= 1 )
682  {
683  infoMessage("Error while reading edges in file %s.\n", filename);
684  (void) fclose(file);
685  return FALSE;
686  }
687 
688  if( node1 < 0 || node2 < 0 || node1 >= (*tcliquegraph)->nnodes || node2 >= (*tcliquegraph)->nnodes )
689  {
690  infoMessage("Invalid node index (%d) in file: %s.\n", node1 < 0 ? node1 : node2, filename);
691  (void) fclose(file);
692  return FALSE;
693  }
694 
695  /* (node1, node2) is the first adjacent edge of node1 */
696  if( node1 != currentnode )
697  {
698  currentnode = node1;
699  /* coverity[tainted_data] */
700  (*tcliquegraph)->degrees[currentnode] = 0;
701  (*tcliquegraph)->adjedges[currentnode].first = i;
702  (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
703  }
704  (*tcliquegraph)->degrees[currentnode]++;
705  (*tcliquegraph)->adjnodes[i] = node2;
706  (*tcliquegraph)->adjedges[currentnode].last++;
707  }
708 
709  /* close file */
710  (void) fclose(file);
711 
712  return TRUE;
713 }
714 
715 /** saves graph data structure to file */
717  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
718  const char* filename, /**< name of file to create */
719  double scaleval, /**< value to unscale weights with */
720  const char* probname /**< name of the problem */
721  )
722 {
723  FILE* file;
724  int i;
725  int j;
726 
727  assert(tcliquegraph != NULL);
728  assert(scaleval > 0.0);
729 
730  /* create file */
731  if( (file = fopen(filename, "w")) == NULL )
732  {
733  infoMessage("Can't create file: %s.\n", filename);
734  return FALSE;
735  }
736 
737  /* write name of problem, number of nodes and number of edges in graph */
738  fprintf(file, "%s\n", probname);
739  fprintf(file, "%d\n", tcliquegraph->nnodes);
740  fprintf(file, "%d\n", tcliquegraph->nedges);
741 
742  /* write weights of all nodes (scaled!) */
743  for( i = 0; i < tcliquegraph->nnodes; i++ )
744  fprintf(file, "%f\n", (double)tcliquegraph->weights[i]/scaleval);
745 
746  /* write edges */
747  for( i = 0; i < tcliquegraph->nnodes; i++ )
748  {
749  for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
750  fprintf(file, "%d %d\n", i, tcliquegraph->adjnodes[j]);
751  }
752 
753  /* close file */
754  fclose(file);
755 
756  return TRUE;
757 }
758 
759 /** gets number of edges in the graph */
761  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
762  )
763 {
764  assert(tcliquegraph != NULL);
765 
766  return tcliquegraph->nedges + tcliquegraph->ncachededges;
767 }
768 
769 /** gets degree of nodes in graph */
771  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
772  )
773 {
774  assert(tcliquegraph != NULL);
775  assert(tcliquegraph->ncachededges == 0);
776 
777  return tcliquegraph->degrees;
778 }
779 
780 /** gets adjacent nodes of edges in graph */
782  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
783  )
784 {
785  assert(tcliquegraph != NULL);
786  assert(tcliquegraph->ncachededges == 0);
787 
788  return tcliquegraph->adjnodes;
789 }
790 
791 /** gets pointer to first adjacent edge of given node in graph */
793  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
794  int node /**< given node */
795  )
796 {
797  HEAD_ADJ* adjedges;
798  int* adjnodes;
799 
800  assert(tcliquegraph != NULL);
801  assert(tcliquegraph->ncachededges == 0);
802  assert(0 <= node && node < tcliquegraph->nnodes);
803 
804  adjedges = tcliquegraph->adjedges;
805  assert(adjedges != NULL);
806  assert(adjedges[node].first >= 0);
807  assert(adjedges[node].first <= tcliqueGetNEdges(tcliquegraph));
808 
809  adjnodes = tcliqueGetAdjnodes(tcliquegraph);
810  assert(adjnodes != NULL);
811 
812  return &adjnodes[adjedges[node].first];
813 }
814 
815 /** gets pointer to last adjacent edge of given node in graph */
817  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
818  int node /**< given node */
819  )
820 {
821  HEAD_ADJ* adjedges;
822  int* adjnodes;
823 #ifndef NDEBUG
824  int* degrees;
825 #endif
826 
827  assert(tcliquegraph != NULL);
828  assert(tcliquegraph->ncachededges == 0);
829  assert(0 <= node && node < tcliquegraph->nnodes);
830 
831  adjedges = tcliquegraph->adjedges;
832 #ifndef NDEBUG
833  degrees = tcliqueGetDegrees(tcliquegraph);
834 #endif
835  assert(adjedges != NULL);
836  assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
837  assert(adjedges[node].last-1 <= tcliqueGetNEdges(tcliquegraph));
838 
839  assert(adjedges[node].last - adjedges[node].first == degrees[node]);
840 
841  adjnodes = tcliqueGetAdjnodes(tcliquegraph);
842  assert(adjnodes != NULL);
843 
844  return &adjnodes[adjedges[node].last-1];
845 }
846 
847 /** prints graph data structure */
849  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
850  )
851 {
852  const int* weights;
853  int* degrees;
854  int i;
855 
856  assert(tcliquegraph != NULL);
857  assert(tcliquegraph->ncachededges == 0);
858 
859  degrees = tcliqueGetDegrees(tcliquegraph);
860  weights = tcliqueGetWeights(tcliquegraph);
861 
862  infoMessage("nnodes=%d, nedges=%d\n", tcliqueGetNNodes(tcliquegraph), tcliqueGetNEdges(tcliquegraph));
863  for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
864  {
865  int* currentadjedge;
866  int* lastadjedge;
867 
868  infoMessage("node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
869 
870  currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, i);
871  lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, i);
872  assert(lastadjedge + 1 - currentadjedge == degrees[i]);
873 
874  for( ; currentadjedge <= lastadjedge; currentadjedge++ )
875  {
876  infoMessage("%d, ", *currentadjedge);
877  }
878  infoMessage("]\n");
879  }
880 }
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
int tcliqueGetNEdges(TCLIQUE_GRAPH *tcliquegraph)
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:140
tclique defines
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
static TCLIQUE_Bool tcliqueEnsureSizeNodes(TCLIQUE_GRAPH *tcliquegraph, int num)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
TCLIQUE_GETWEIGHTS(tcliqueGetWeights)
Definition: tclique_graph.c:75
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:115
static TCLIQUE_Bool tcliqueEnsureSizeCachedEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
tclique user interface
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
#define BMSfreeMemory(ptr)
Definition: memory.h:137
struct _HEAD_ADJ HEAD_ADJ
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:139
#define TCLIQUE_Bool
Definition: tclique.h:44
#define ALLOC_FALSE(x)
Definition: tclique_def.h:55
#define NULL
Definition: lpi_spx1.cpp:155
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
TCLIQUE_SELECTADJNODES(tcliqueSelectAdjnodes)
void tcliquePrintGraph(TCLIQUE_GRAPH *tcliquegraph)
TCLIQUE_Bool tcliqueLoadFile(TCLIQUE_GRAPH **tcliquegraph, const char *filename, double scaleval, char *probname, int sizeofprobname)
#define MAX(x, y)
Definition: tclique_def.h:83
TCLIQUE_GETNNODES(tcliqueGetNNodes)
Definition: tclique_graph.c:67
TCLIQUE_Bool tcliqueSaveFile(TCLIQUE_GRAPH *tcliquegraph, const char *filename, double scaleval, const char *probname)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
TCLIQUE_ISEDGE(tcliqueIsEdge)
Definition: tclique_graph.c:83
#define infoMessage
Definition: tclique_def.h:79
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:119
int * tcliqueGetAdjnodes(TCLIQUE_GRAPH *tcliquegraph)
#define nnodes
Definition: gastrans.c:65
static TCLIQUE_Bool tcliqueEnsureSizeEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
int TCLIQUE_WEIGHT
Definition: tclique.h:39
memory allocation routines