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-2016 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  BMScopyMemoryArray(tmp, probname, sizeofprobname);
591  probname[sizeofprobname-1] = '\0';
592  tmp[sizeofprobname] = '\0';
593 
594  /* continue reading until we reach the end of the problem name */
595  while( (int) strlen(tmp) == sizeofprobname && tmp[strlen(tmp)-1] != '\n' )
596  {
597  charresult = fgets(tmp, sizeofprobname, file);
598 
599  if( charresult == NULL )
600  {
601  infoMessage("Error while reading probname in file %s", filename);
602  fclose(file);
603  return FALSE;
604  }
605  }
606 
607  /* free temporary memory */
608  BMSfreeMemoryArray(&tmp);
609 
610  /* set number of nodes and number of edges in graph */
611  result = fscanf(file, "%d", &(*tcliquegraph)->nnodes);
612  if( result == EOF )
613  {
614  infoMessage("Error while reading number of nodes in file %s", filename);
615  fclose(file);
616  return FALSE;
617  }
618 
619  result = fscanf(file, "%d", &(*tcliquegraph)->nedges);
620  if( result == EOF )
621  {
622  infoMessage("Error while reading number of edges in file %s", filename);
623  fclose(file);
624  return FALSE;
625  }
626 
627  if( (*tcliquegraph)->nnodes < 0 || (*tcliquegraph)->nedges < 0 )
628  {
629  infoMessage("\nInvalid number of %s (%d) in file: %s", (*tcliquegraph)->nnodes < 0 ? "nodes" : "edges",
630  (*tcliquegraph)->nnodes < 0 ? (*tcliquegraph)->nnodes : (*tcliquegraph)->nedges, filename);
631  fclose(file);
632  return FALSE;
633  }
634 
635  /* set data structures for tclique,
636  * if an error occured, close the file before returning */
637  if( BMSallocMemoryArray(&(*tcliquegraph)->weights, (*tcliquegraph)->nnodes) == NULL )
638  {
639  infoMessage("Run out of memory while reading file %s", filename);
640  (void) fclose(file);
641  return FALSE;
642  }
643 
644  if( BMSallocMemoryArray(&(*tcliquegraph)->degrees, (*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)->adjnodes, (*tcliquegraph)->nedges) == 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)->adjedges, (*tcliquegraph)->nnodes) == NULL )
659  {
660  infoMessage("Run out of memory while reading file %s", filename);
661  (void) fclose(file);
662  return FALSE;
663  }
664 
665  /* set weights of all nodes (scaled!) */
666  for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
667  {
668  result = fscanf(file, "%lf", &weight);
669  if( result == EOF )
670  {
671  infoMessage("Error while reading weights of nodes in file %s", filename);
672  fclose(file);
673  return FALSE;
674  }
675 
676  (*tcliquegraph)->weights[i] = (TCLIQUE_WEIGHT)(weight * scaleval);
677  assert((*tcliquegraph)->weights[i] >= 0);
678  }
679 
680  /* set adjacent edges and degree of all nodes */
681  currentnode = -1;
682  for( i = 0; i < (*tcliquegraph)->nedges; i++ )
683  {
684  /* read edge (node1, node2) */
685  result = fscanf(file, "%d%d", &node1, &node2);
686  if( result == EOF )
687  {
688  infoMessage("Error while reading edges in file %s", filename);
689  fclose(file);
690  return FALSE;
691  }
692 
693  if( node1 < 0 || node2 < 0 )
694  {
695  infoMessage("\nInvalid node index (%d) in file: %s", node1 < 0 ? node1 : node2, filename);
696  fclose(file);
697  return FALSE;
698  }
699 
700  /* (node1, node2) is the first adjacent edge of node1 */
701  if( node1 != currentnode )
702  {
703  currentnode = node1;
704  (*tcliquegraph)->degrees[currentnode] = 0;
705  (*tcliquegraph)->adjedges[currentnode].first = i;
706  (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
707  }
708  (*tcliquegraph)->degrees[currentnode]++;
709  (*tcliquegraph)->adjnodes[i] = node2;
710  (*tcliquegraph)->adjedges[currentnode].last++;
711  }
712 
713  /* close file */
714  fclose(file);
715 
716  return TRUE;
717 }
718 
719 /** saves graph data structure to file */
721  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
722  const char* filename, /**< name of file to create */
723  double scaleval, /**< value to unscale weights with */
724  const char* probname /**< name of the problem */
725  )
726 {
727  FILE* file;
728  int i;
729  int j;
730 
731  assert(tcliquegraph != NULL);
732  assert(scaleval > 0.0);
733 
734  /* create file */
735  if( (file = fopen(filename, "w")) == NULL )
736  {
737  infoMessage("\nCan't create file: %s", filename);
738  return FALSE;
739  }
740 
741  /* write name of problem, number of nodes and number of edges in graph */
742  fprintf(file, "%s\n", probname);
743  fprintf(file, "%d\n", tcliquegraph->nnodes);
744  fprintf(file, "%d\n", tcliquegraph->nedges);
745 
746  /* write weights of all nodes (scaled!) */
747  for( i = 0; i < tcliquegraph->nnodes; i++ )
748  fprintf(file, "%f\n", (double)tcliquegraph->weights[i]/scaleval);
749 
750  /* write edges */
751  for( i = 0; i < tcliquegraph->nnodes; i++ )
752  {
753  for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
754  fprintf(file, "%d %d\n", i, tcliquegraph->adjnodes[j]);
755  }
756 
757  /* close file */
758  fclose(file);
759 
760  return TRUE;
761 }
762 
763 /** gets number of edges in the graph */
765  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
766  )
767 {
768  assert(tcliquegraph != NULL);
769 
770  return tcliquegraph->nedges + tcliquegraph->ncachededges;
771 }
772 
773 /** gets degree of nodes in graph */
775  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
776  )
777 {
778  assert(tcliquegraph != NULL);
779  assert(tcliquegraph->ncachededges == 0);
780 
781  return tcliquegraph->degrees;
782 }
783 
784 /** gets adjacent nodes of edges 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->adjnodes;
793 }
794 
795 /** gets pointer to first adjacent edge of given node in graph */
797  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
798  int node /**< given node */
799  )
800 {
801  HEAD_ADJ* adjedges;
802  int* adjnodes;
803 
804  assert(tcliquegraph != NULL);
805  assert(tcliquegraph->ncachededges == 0);
806  assert(0 <= node && node < tcliquegraph->nnodes);
807 
808  adjedges = tcliquegraph->adjedges;
809  assert(adjedges != NULL);
810  assert(adjedges[node].first >= 0);
811  assert(adjedges[node].first <= tcliqueGetNEdges(tcliquegraph));
812 
813  adjnodes = tcliqueGetAdjnodes(tcliquegraph);
814  assert(adjnodes != NULL);
815 
816  return &adjnodes[adjedges[node].first];
817 }
818 
819 /** gets pointer to last adjacent edge of given node in graph */
821  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
822  int node /**< given node */
823  )
824 {
825  HEAD_ADJ* adjedges;
826  int* adjnodes;
827 #ifndef NDEBUG
828  int* degrees;
829 #endif
830 
831  assert(tcliquegraph != NULL);
832  assert(tcliquegraph->ncachededges == 0);
833  assert(0 <= node && node < tcliquegraph->nnodes);
834 
835  adjedges = tcliquegraph->adjedges;
836 #ifndef NDEBUG
837  degrees = tcliqueGetDegrees(tcliquegraph);
838 #endif
839  assert(adjedges != NULL);
840  assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
841  assert(adjedges[node].last-1 <= tcliqueGetNEdges(tcliquegraph));
842 
843  assert(adjedges[node].last - adjedges[node].first == degrees[node]);
844 
845  adjnodes = tcliqueGetAdjnodes(tcliquegraph);
846  assert(adjnodes != NULL);
847 
848  return &adjnodes[adjedges[node].last-1];
849 }
850 
851 /** prints graph data structure */
853  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
854  )
855 {
856  const int* weights;
857  int* degrees;
858  int i;
859 
860  assert(tcliquegraph != NULL);
861  assert(tcliquegraph->ncachededges == 0);
862 
863  degrees = tcliqueGetDegrees(tcliquegraph);
864  weights = tcliqueGetWeights(tcliquegraph);
865 
866  infoMessage("nnodes=%d, nedges=%d\n", tcliqueGetNNodes(tcliquegraph), tcliqueGetNEdges(tcliquegraph));
867  for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
868  {
869  int* currentadjedge;
870  int* lastadjedge;
871 
872  infoMessage("node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
873 
874  currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, i);
875  lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, i);
876  assert(lastadjedge + 1 - currentadjedge == degrees[i]);
877 
878  for( ; currentadjedge <= lastadjedge; currentadjedge++ )
879  {
880  infoMessage("%d, ", *currentadjedge);
881  }
882  infoMessage("]\n");
883  }
884 }
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:102
int tcliqueGetNEdges(TCLIQUE_GRAPH *tcliquegraph)
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:38
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
TCLIQUE_GETWEIGHTS(tcliqueGetWeights)
Definition: tclique_graph.c:74
#define NULL
Definition: lpi_spx.cpp:130
#define FALSE
Definition: def.h:56
#define TRUE
Definition: def.h:55
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
static TCLIQUE_Bool tcliqueEnsureSizeCachedEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
tclique user interface
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
struct _HEAD_ADJ HEAD_ADJ
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
#define TCLIQUE_Bool
Definition: tclique.h:42
#define BMSallocMemory(ptr)
Definition: memory.h:74
#define ALLOC_FALSE(x)
Definition: tclique_def.h:47
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:82
#define BMSfreeMemory(ptr)
Definition: memory.h:100
TCLIQUE_SELECTADJNODES(tcliqueSelectAdjnodes)
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:103
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:89
TCLIQUE_ISEDGE(tcliqueIsEdge)
Definition: tclique_graph.c:82
#define infoMessage
Definition: tclique_def.h:71
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
int * tcliqueGetAdjnodes(TCLIQUE_GRAPH *tcliquegraph)
static TCLIQUE_Bool tcliqueEnsureSizeEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:78
int TCLIQUE_WEIGHT
Definition: tclique.h:37
memory allocation routines