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-2017 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  result = fscanf(file, "%d", &(*tcliquegraph)->nnodes);
619  if( result <= 0 )
620  {
621  infoMessage("Error while reading number of nodes in file %s", filename);
622  fclose(file);
623  return FALSE;
624  }
625 
626  result = fscanf(file, "%d", &(*tcliquegraph)->nedges);
627  if( result <= 0 )
628  {
629  infoMessage("Error while reading number of edges in file %s", filename);
630  fclose(file);
631  return FALSE;
632  }
633 
634  if( (*tcliquegraph)->nnodes < 0 || (*tcliquegraph)->nedges < 0 )
635  {
636  infoMessage("\nInvalid number of %s (%d) in file: %s", (*tcliquegraph)->nnodes < 0 ? "nodes" : "edges",
637  (*tcliquegraph)->nnodes < 0 ? (*tcliquegraph)->nnodes : (*tcliquegraph)->nedges, filename);
638  fclose(file);
639  return FALSE;
640  }
641 
642  /* set data structures for tclique,
643  * if an error occured, close the file before returning */
644  if( BMSallocMemoryArray(&(*tcliquegraph)->weights, (*tcliquegraph)->nnodes) == NULL )
645  {
646  infoMessage("Run out of memory while reading file %s", filename);
647  (void) fclose(file);
648  return FALSE;
649  }
650 
651  if( BMSallocMemoryArray(&(*tcliquegraph)->degrees, (*tcliquegraph)->nnodes) == NULL )
652  {
653  infoMessage("Run out of memory while reading file %s", filename);
654  (void) fclose(file);
655  return FALSE;
656  }
657 
658  if( BMSallocMemoryArray(&(*tcliquegraph)->adjnodes, (*tcliquegraph)->nedges) == NULL )
659  {
660  infoMessage("Run out of memory while reading file %s", filename);
661  (void) fclose(file);
662  return FALSE;
663  }
664 
665  if( BMSallocMemoryArray(&(*tcliquegraph)->adjedges, (*tcliquegraph)->nnodes) == NULL )
666  {
667  infoMessage("Run out of memory while reading file %s", filename);
668  (void) fclose(file);
669  return FALSE;
670  }
671 
672  /* set weights of all nodes (scaled!) */
673  for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
674  {
675  result = fscanf(file, "%lf", &weight);
676  if( result <= 0 )
677  {
678  infoMessage("Error while reading weights of nodes in file %s", filename);
679  fclose(file);
680  return FALSE;
681  }
682 
683  (*tcliquegraph)->weights[i] = (TCLIQUE_WEIGHT)(weight * scaleval);
684  assert((*tcliquegraph)->weights[i] >= 0);
685  }
686 
687  /* set adjacent edges and degree of all nodes */
688  currentnode = -1;
689  for( i = 0; i < (*tcliquegraph)->nedges; i++ )
690  {
691  /* read edge (node1, node2) */
692  result = fscanf(file, "%d%d", &node1, &node2);
693  if( result <= 1 )
694  {
695  infoMessage("Error while reading edges in file %s", filename);
696  fclose(file);
697  return FALSE;
698  }
699 
700  if( node1 < 0 || node2 < 0 )
701  {
702  infoMessage("\nInvalid node index (%d) in file: %s", node1 < 0 ? node1 : node2, filename);
703  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  (*tcliquegraph)->degrees[currentnode] = 0;
712  (*tcliquegraph)->adjedges[currentnode].first = i;
713  (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
714  }
715  (*tcliquegraph)->degrees[currentnode]++;
716  (*tcliquegraph)->adjnodes[i] = node2;
717  (*tcliquegraph)->adjedges[currentnode].last++;
718  }
719 
720  /* close file */
721  fclose(file);
722 
723  return TRUE;
724 }
725 
726 /** saves graph data structure to file */
728  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
729  const char* filename, /**< name of file to create */
730  double scaleval, /**< value to unscale weights with */
731  const char* probname /**< name of the problem */
732  )
733 {
734  FILE* file;
735  int i;
736  int j;
737 
738  assert(tcliquegraph != NULL);
739  assert(scaleval > 0.0);
740 
741  /* create file */
742  if( (file = fopen(filename, "w")) == NULL )
743  {
744  infoMessage("\nCan't create file: %s", filename);
745  return FALSE;
746  }
747 
748  /* write name of problem, number of nodes and number of edges in graph */
749  fprintf(file, "%s\n", probname);
750  fprintf(file, "%d\n", tcliquegraph->nnodes);
751  fprintf(file, "%d\n", tcliquegraph->nedges);
752 
753  /* write weights of all nodes (scaled!) */
754  for( i = 0; i < tcliquegraph->nnodes; i++ )
755  fprintf(file, "%f\n", (double)tcliquegraph->weights[i]/scaleval);
756 
757  /* write edges */
758  for( i = 0; i < tcliquegraph->nnodes; i++ )
759  {
760  for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
761  fprintf(file, "%d %d\n", i, tcliquegraph->adjnodes[j]);
762  }
763 
764  /* close file */
765  fclose(file);
766 
767  return TRUE;
768 }
769 
770 /** gets number of edges in the graph */
772  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
773  )
774 {
775  assert(tcliquegraph != NULL);
776 
777  return tcliquegraph->nedges + tcliquegraph->ncachededges;
778 }
779 
780 /** gets degree of nodes 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->degrees;
789 }
790 
791 /** gets adjacent nodes of edges in graph */
793  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
794  )
795 {
796  assert(tcliquegraph != NULL);
797  assert(tcliquegraph->ncachededges == 0);
798 
799  return tcliquegraph->adjnodes;
800 }
801 
802 /** gets pointer to first adjacent edge of given node in graph */
804  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
805  int node /**< given node */
806  )
807 {
808  HEAD_ADJ* adjedges;
809  int* adjnodes;
810 
811  assert(tcliquegraph != NULL);
812  assert(tcliquegraph->ncachededges == 0);
813  assert(0 <= node && node < tcliquegraph->nnodes);
814 
815  adjedges = tcliquegraph->adjedges;
816  assert(adjedges != NULL);
817  assert(adjedges[node].first >= 0);
818  assert(adjedges[node].first <= tcliqueGetNEdges(tcliquegraph));
819 
820  adjnodes = tcliqueGetAdjnodes(tcliquegraph);
821  assert(adjnodes != NULL);
822 
823  return &adjnodes[adjedges[node].first];
824 }
825 
826 /** gets pointer to last adjacent edge of given node in graph */
828  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
829  int node /**< given node */
830  )
831 {
832  HEAD_ADJ* adjedges;
833  int* adjnodes;
834 #ifndef NDEBUG
835  int* degrees;
836 #endif
837 
838  assert(tcliquegraph != NULL);
839  assert(tcliquegraph->ncachededges == 0);
840  assert(0 <= node && node < tcliquegraph->nnodes);
841 
842  adjedges = tcliquegraph->adjedges;
843 #ifndef NDEBUG
844  degrees = tcliqueGetDegrees(tcliquegraph);
845 #endif
846  assert(adjedges != NULL);
847  assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
848  assert(adjedges[node].last-1 <= tcliqueGetNEdges(tcliquegraph));
849 
850  assert(adjedges[node].last - adjedges[node].first == degrees[node]);
851 
852  adjnodes = tcliqueGetAdjnodes(tcliquegraph);
853  assert(adjnodes != NULL);
854 
855  return &adjnodes[adjedges[node].last-1];
856 }
857 
858 /** prints graph data structure */
860  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
861  )
862 {
863  const int* weights;
864  int* degrees;
865  int i;
866 
867  assert(tcliquegraph != NULL);
868  assert(tcliquegraph->ncachededges == 0);
869 
870  degrees = tcliqueGetDegrees(tcliquegraph);
871  weights = tcliqueGetWeights(tcliquegraph);
872 
873  infoMessage("nnodes=%d, nedges=%d\n", tcliqueGetNNodes(tcliquegraph), tcliqueGetNEdges(tcliquegraph));
874  for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
875  {
876  int* currentadjedge;
877  int* lastadjedge;
878 
879  infoMessage("node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
880 
881  currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, i);
882  lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, i);
883  assert(lastadjedge + 1 - currentadjedge == degrees[i]);
884 
885  for( ; currentadjedge <= lastadjedge; currentadjedge++ )
886  {
887  infoMessage("%d, ", *currentadjedge);
888  }
889  infoMessage("]\n");
890  }
891 }
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
int tcliqueGetNEdges(TCLIQUE_GRAPH *tcliquegraph)
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:130
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:64
#define TRUE
Definition: def.h:63
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:105
static TCLIQUE_Bool tcliqueEnsureSizeCachedEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
tclique user interface
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
#define BMSfreeMemory(ptr)
Definition: memory.h:127
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:129
#define TCLIQUE_Bool
Definition: tclique.h:44
#define ALLOC_FALSE(x)
Definition: tclique_def.h:47
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:75
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:116
TCLIQUE_ISEDGE(tcliqueIsEdge)
Definition: tclique_graph.c:82
#define infoMessage
Definition: tclique_def.h:71
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
#define BMSallocMemory(ptr)
Definition: memory.h:101
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:109
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:112
int TCLIQUE_WEIGHT
Definition: tclique.h:39
memory allocation routines