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-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_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  char* tmp;
560 
561  assert(tcliquegraph != NULL);
562  assert(scaleval > 0.0);
563 
564  /* open file */
565  if( (file = fopen(filename, "r")) == NULL )
566  {
567  if( (file = fopen("default.dat", "r")) == NULL )
568  {
569  infoMessage("\nCan't open file: %s", filename);
570  return FALSE;
571  }
572  }
573 
574  if( !tcliqueCreate(tcliquegraph) )
575  {
576  fclose(file);
577  return FALSE;
578  }
579 
580  /* set name of problem, copies 'sizeofprobname' characters into probname */
581  charresult = fgets(probname, sizeofprobname, file);
582  if( charresult == NULL )
583  {
584  infoMessage("Error while reading probname in file %s", filename);
585  fclose(file);
586  return FALSE;
587  }
588 
589  /* allocate temporary memory for skipping rest of problem name */
590  BMSallocMemoryArray(&tmp, sizeofprobname +1 );
591  if( tmp == NULL )
592  {
593  infoMessage("[%s:%d] No memory in function call", __FILE__, __LINE__);
594  fclose(file);
595  return FALSE;
596  }
597 
598  BMScopyMemoryArray(tmp, probname, sizeofprobname);
599  probname[sizeofprobname-1] = '\0';
600  tmp[sizeofprobname] = '\0';
601 
602  /* continue reading until we reach the end of the problem name */
603  while( (int) strlen(tmp) == sizeofprobname && tmp[strlen(tmp)-1] != '\n' )
604  {
605  charresult = fgets(tmp, sizeofprobname, file);
606 
607  if( charresult == NULL )
608  {
609  infoMessage("Error while reading probname in file %s", filename);
610  fclose(file);
611  return FALSE;
612  }
613  }
614 
615  /* free temporary memory */
616  BMSfreeMemoryArray(&tmp);
617 
618  /* set number of nodes and number of edges in graph */
619  /* coverity[tainted_data] */
620  result = fscanf(file, "%d", &(*tcliquegraph)->nnodes);
621  if( result <= 0 )
622  {
623  infoMessage("Error while reading number of nodes in file %s", filename);
624  fclose(file);
625  return FALSE;
626  }
627 
628  /* coverity[tainted_data] */
629  result = fscanf(file, "%d", &(*tcliquegraph)->nedges);
630  if( result <= 0 )
631  {
632  infoMessage("Error while reading number of edges in file %s", filename);
633  fclose(file);
634  return FALSE;
635  }
636 
637  if( (*tcliquegraph)->nnodes < 0 || (*tcliquegraph)->nedges < 0 )
638  {
639  infoMessage("\nInvalid number of %s (%d) in file: %s", (*tcliquegraph)->nnodes < 0 ? "nodes" : "edges",
640  (*tcliquegraph)->nnodes < 0 ? (*tcliquegraph)->nnodes : (*tcliquegraph)->nedges, filename);
641  fclose(file);
642  return FALSE;
643  }
644 
645  /* set data structures for tclique,
646  * if an error occured, close the file before returning */
647  if( BMSallocMemoryArray(&(*tcliquegraph)->weights, (*tcliquegraph)->nnodes) == NULL )
648  {
649  infoMessage("Run out of memory while reading file %s", filename);
650  (void) fclose(file);
651  return FALSE;
652  }
653 
654  if( BMSallocMemoryArray(&(*tcliquegraph)->degrees, (*tcliquegraph)->nnodes) == NULL )
655  {
656  infoMessage("Run out of memory while reading file %s", filename);
657  (void) fclose(file);
658  return FALSE;
659  }
660 
661  if( BMSallocMemoryArray(&(*tcliquegraph)->adjnodes, (*tcliquegraph)->nedges) == NULL )
662  {
663  infoMessage("Run out of memory while reading file %s", filename);
664  (void) fclose(file);
665  return FALSE;
666  }
667 
668  if( BMSallocMemoryArray(&(*tcliquegraph)->adjedges, (*tcliquegraph)->nnodes) == NULL )
669  {
670  infoMessage("Run out of memory while reading file %s", filename);
671  (void) fclose(file);
672  return FALSE;
673  }
674 
675  /* set weights of all nodes (scaled!) */
676  for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
677  {
678  result = fscanf(file, "%lf", &weight);
679  if( result <= 0 )
680  {
681  infoMessage("Error while reading weights of nodes in file %s", filename);
682  fclose(file);
683  return FALSE;
684  }
685 
686  (*tcliquegraph)->weights[i] = (TCLIQUE_WEIGHT)(weight * scaleval);
687  assert((*tcliquegraph)->weights[i] >= 0);
688  }
689 
690  /* set adjacent edges and degree of all nodes */
691  currentnode = -1;
692  for( i = 0; i < (*tcliquegraph)->nedges; i++ )
693  {
694  /* read edge (node1, node2) */
695  /* coverity[secure_coding] */
696  result = fscanf(file, "%d%d", &node1, &node2);
697  if( result <= 1 )
698  {
699  infoMessage("Error while reading edges in file %s", filename);
700  fclose(file);
701  return FALSE;
702  }
703 
704  if( node1 < 0 || node2 < 0 || node1 >= (*tcliquegraph)->nnodes || node2 >= (*tcliquegraph)->nnodes )
705  {
706  infoMessage("\nInvalid node index (%d) in file: %s", node1 < 0 ? node1 : node2, filename);
707  fclose(file);
708  return FALSE;
709  }
710 
711  /* (node1, node2) is the first adjacent edge of node1 */
712  if( node1 != currentnode )
713  {
714  currentnode = node1;
715  /* coverity[tainted_data] */
716  (*tcliquegraph)->degrees[currentnode] = 0;
717  (*tcliquegraph)->adjedges[currentnode].first = i;
718  (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
719  }
720  (*tcliquegraph)->degrees[currentnode]++;
721  (*tcliquegraph)->adjnodes[i] = node2;
722  (*tcliquegraph)->adjedges[currentnode].last++;
723  }
724 
725  /* close file */
726  fclose(file);
727 
728  return TRUE;
729 }
730 
731 /** saves graph data structure to file */
733  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
734  const char* filename, /**< name of file to create */
735  double scaleval, /**< value to unscale weights with */
736  const char* probname /**< name of the problem */
737  )
738 {
739  FILE* file;
740  int i;
741  int j;
742 
743  assert(tcliquegraph != NULL);
744  assert(scaleval > 0.0);
745 
746  /* create file */
747  if( (file = fopen(filename, "w")) == NULL )
748  {
749  infoMessage("\nCan't create file: %s", filename);
750  return FALSE;
751  }
752 
753  /* write name of problem, number of nodes and number of edges in graph */
754  fprintf(file, "%s\n", probname);
755  fprintf(file, "%d\n", tcliquegraph->nnodes);
756  fprintf(file, "%d\n", tcliquegraph->nedges);
757 
758  /* write weights of all nodes (scaled!) */
759  for( i = 0; i < tcliquegraph->nnodes; i++ )
760  fprintf(file, "%f\n", (double)tcliquegraph->weights[i]/scaleval);
761 
762  /* write edges */
763  for( i = 0; i < tcliquegraph->nnodes; i++ )
764  {
765  for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
766  fprintf(file, "%d %d\n", i, tcliquegraph->adjnodes[j]);
767  }
768 
769  /* close file */
770  fclose(file);
771 
772  return TRUE;
773 }
774 
775 /** gets number of edges in the graph */
777  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
778  )
779 {
780  assert(tcliquegraph != NULL);
781 
782  return tcliquegraph->nedges + tcliquegraph->ncachededges;
783 }
784 
785 /** gets degree of nodes in graph */
787  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
788  )
789 {
790  assert(tcliquegraph != NULL);
791  assert(tcliquegraph->ncachededges == 0);
792 
793  return tcliquegraph->degrees;
794 }
795 
796 /** gets adjacent nodes of edges in graph */
798  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
799  )
800 {
801  assert(tcliquegraph != NULL);
802  assert(tcliquegraph->ncachededges == 0);
803 
804  return tcliquegraph->adjnodes;
805 }
806 
807 /** gets pointer to first adjacent edge of given node in graph */
809  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
810  int node /**< given node */
811  )
812 {
813  HEAD_ADJ* adjedges;
814  int* adjnodes;
815 
816  assert(tcliquegraph != NULL);
817  assert(tcliquegraph->ncachededges == 0);
818  assert(0 <= node && node < tcliquegraph->nnodes);
819 
820  adjedges = tcliquegraph->adjedges;
821  assert(adjedges != NULL);
822  assert(adjedges[node].first >= 0);
823  assert(adjedges[node].first <= tcliqueGetNEdges(tcliquegraph));
824 
825  adjnodes = tcliqueGetAdjnodes(tcliquegraph);
826  assert(adjnodes != NULL);
827 
828  return &adjnodes[adjedges[node].first];
829 }
830 
831 /** gets pointer to last adjacent edge of given node in graph */
833  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
834  int node /**< given node */
835  )
836 {
837  HEAD_ADJ* adjedges;
838  int* adjnodes;
839 #ifndef NDEBUG
840  int* degrees;
841 #endif
842 
843  assert(tcliquegraph != NULL);
844  assert(tcliquegraph->ncachededges == 0);
845  assert(0 <= node && node < tcliquegraph->nnodes);
846 
847  adjedges = tcliquegraph->adjedges;
848 #ifndef NDEBUG
849  degrees = tcliqueGetDegrees(tcliquegraph);
850 #endif
851  assert(adjedges != NULL);
852  assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
853  assert(adjedges[node].last-1 <= tcliqueGetNEdges(tcliquegraph));
854 
855  assert(adjedges[node].last - adjedges[node].first == degrees[node]);
856 
857  adjnodes = tcliqueGetAdjnodes(tcliquegraph);
858  assert(adjnodes != NULL);
859 
860  return &adjnodes[adjedges[node].last-1];
861 }
862 
863 /** prints graph data structure */
865  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
866  )
867 {
868  const int* weights;
869  int* degrees;
870  int i;
871 
872  assert(tcliquegraph != NULL);
873  assert(tcliquegraph->ncachededges == 0);
874 
875  degrees = tcliqueGetDegrees(tcliquegraph);
876  weights = tcliqueGetWeights(tcliquegraph);
877 
878  infoMessage("nnodes=%d, nedges=%d\n", tcliqueGetNNodes(tcliquegraph), tcliqueGetNEdges(tcliquegraph));
879  for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
880  {
881  int* currentadjedge;
882  int* lastadjedge;
883 
884  infoMessage("node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
885 
886  currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, i);
887  lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, i);
888  assert(lastadjedge + 1 - currentadjedge == degrees[i]);
889 
890  for( ; currentadjedge <= lastadjedge; currentadjedge++ )
891  {
892  infoMessage("%d, ", *currentadjedge);
893  }
894  infoMessage("]\n");
895  }
896 }
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)
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:126
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