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