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