# 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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
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
37 {
38  int first;
39  int last;
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 */
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 {
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
103
105  return FALSE;
106
107  /* checks if node2 is contained in adjacency list of node1
108  * (list is ordered by adjacent nodes) */
110  {
111  if( *currentadjedge >= node2 )
112  {
113  if( *currentadjedge == node2 )
114  return TRUE;
115  else
116  break;
117  }
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 */
127 {
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);
138
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]);
151  {
152  if( *currentadjedge >= nodes[i] )
153  {
154  /* current node is adjacent to given node */
155  if( *currentadjedge == nodes[i] )
156  {
159  }
160  break;
161  }
162  }
163  }
164
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;
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  {
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
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;
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) );
305
306  for( i = tcliquegraph->sizenodes; i < newsize; i++ )
307  {
308  tcliquegraph->weights[i] = 0;
309  tcliquegraph->degrees[i] = 0;
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);
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;
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);
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);
455  }
456
457  /* adjust the first and last edge pointers of the node */
459  tcliquegraph->adjedges[n].last = pos+1 + olddegree;
460
461  assert(n == tcliquegraph->nnodes-1
463  }
464  assert(ninsertedholes == tcliquegraph->ncachededges);
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);
482  assert(n == tcliquegraph->nnodes-1
484
485  /* edges of each node must be sorted by increasing destination node number */
488  {
490  }
493
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
528
530  {
532  }
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
560  assert(tcliquegraph != NULL);
561  assert(scaleval > 0.0);
562  assert(sizeofprobname >= 2);
563
564  /* open file */
565  if( (file = fopen(filename, "r")) == NULL )
566  {
567  if( (file = fopen("default.dat", "r")) == NULL )
568  {
569  infoMessage("Cannot open file: %s.\n", filename);
570  return FALSE;
571  }
572  }
573
574  if( !tcliqueCreate(tcliquegraph) )
575  {
576  (void) fclose(file);
577  return FALSE;
578  }
579
580  /* read name of problem (if line is longer than sizeofprobname continue reading until end of line) */
581  do
582  {
583  probname[sizeofprobname-2] = '\0';
584  charresult = fgets(probname, sizeofprobname, file);
585  if( charresult == NULL )
586  {
587  infoMessage("Error while reading probname in file %s.\n", filename);
588  (void) fclose(file);
589  return FALSE;
590  }
591  }
592  while( probname[sizeofprobname-2] != '\0' );
593
594  /* set number of nodes and number of edges in graph */
595  /* coverity[tainted_data] */
596  result = fscanf(file, "%d", &(*tcliquegraph)->nnodes);
597  if( result <= 0 )
598  {
599  infoMessage("Error while reading number of nodes in file %s.\n", filename);
600  (void) fclose(file);
601  return FALSE;
602  }
603
604  if( (*tcliquegraph)->nnodes < 0 )
605  {
606  infoMessage("Invalid number of nodes (%d) in file: %s.\n", (*tcliquegraph)->nnodes, filename);
607  (void) fclose(file);
608  return FALSE;
609  }
610
611  /* coverity[tainted_data] */
612  result = fscanf(file, "%d", &(*tcliquegraph)->nedges);
613  if( result <= 0 )
614  {
615  infoMessage("Error while reading number of edges in file %s.\n", filename);
616  (void) fclose(file);
617  return FALSE;
618  }
619
620  if( (*tcliquegraph)->nedges < 0 )
621  {
622  infoMessage("Invalid number of edges (%d) in file: %s.\n", (*tcliquegraph)->nedges, filename);
623  (void) fclose(file);
624  return FALSE;
625  }
626
627  /* set data structures for tclique,
628  * if an error occured, close the file before returning */
629  if( BMSallocMemoryArray(&(*tcliquegraph)->weights, (*tcliquegraph)->nnodes) == NULL )
630  {
631  infoMessage("Run out of memory while reading file %s.\n", filename);
632  (void) fclose(file);
633  return FALSE;
634  }
635
636  if( BMSallocMemoryArray(&(*tcliquegraph)->degrees, (*tcliquegraph)->nnodes) == NULL )
637  {
638  infoMessage("Run out of memory while reading file %s.\n", filename);
639  (void) fclose(file);
640  return FALSE;
641  }
642
643  if( BMSallocMemoryArray(&(*tcliquegraph)->adjnodes, (*tcliquegraph)->nedges) == NULL )
644  {
645  infoMessage("Run out of memory while reading file %s.\n", filename);
646  (void) fclose(file);
647  return FALSE;
648  }
649
650  if( BMSallocMemoryArray(&(*tcliquegraph)->adjedges, (*tcliquegraph)->nnodes) == NULL )
651  {
652  infoMessage("Run out of memory while reading file %s.\n", filename);
653  (void) fclose(file);
654  return FALSE;
655  }
656
657  /* set weights of all nodes (scaled!) */
658  /* coverity[tainted_data] */
659  for( i = 0; i < (*tcliquegraph)->nnodes; i++ )
660  {
661  result = fscanf(file, "%lf", &weight);
662  if( result <= 0 )
663  {
664  infoMessage("Error while reading weights of nodes in file %s.\n", filename);
665  (void) fclose(file);
666  return FALSE;
667  }
668
669  (*tcliquegraph)->weights[i] = (TCLIQUE_WEIGHT)(weight * scaleval);
670  assert((*tcliquegraph)->weights[i] >= 0);
671  }
672
673  /* set adjacent edges and degree of all nodes */
674  currentnode = -1;
675  /* coverity[tainted_data] */
676  for( i = 0; i < (*tcliquegraph)->nedges; i++ )
677  {
678  /* read edge (node1, node2) */
679  /* coverity[secure_coding] */
680  result = fscanf(file, "%d%d", &node1, &node2);
681  if( result <= 1 )
682  {
683  infoMessage("Error while reading edges in file %s.\n", filename);
684  (void) fclose(file);
685  return FALSE;
686  }
687
688  if( node1 < 0 || node2 < 0 || node1 >= (*tcliquegraph)->nnodes || node2 >= (*tcliquegraph)->nnodes )
689  {
690  infoMessage("Invalid node index (%d) in file: %s.\n", node1 < 0 ? node1 : node2, filename);
691  (void) fclose(file);
692  return FALSE;
693  }
694
695  /* (node1, node2) is the first adjacent edge of node1 */
696  if( node1 != currentnode )
697  {
698  currentnode = node1;
699  /* coverity[tainted_data] */
700  (*tcliquegraph)->degrees[currentnode] = 0;
703  }
704  (*tcliquegraph)->degrees[currentnode]++;
707  }
708
709  /* close file */
710  (void) fclose(file);
711
712  return TRUE;
713 }
714
715 /** saves graph data structure to file */
717  TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
718  const char* filename, /**< name of file to create */
719  double scaleval, /**< value to unscale weights with */
720  const char* probname /**< name of the problem */
721  )
722 {
723  FILE* file;
724  int i;
725  int j;
726
727  assert(tcliquegraph != NULL);
728  assert(scaleval > 0.0);
729
730  /* create file */
731  if( (file = fopen(filename, "w")) == NULL )
732  {
733  infoMessage("Can't create file: %s.\n", filename);
734  return FALSE;
735  }
736
737  /* write name of problem, number of nodes and number of edges in graph */
738  fprintf(file, "%s\n", probname);
739  fprintf(file, "%d\n", tcliquegraph->nnodes);
740  fprintf(file, "%d\n", tcliquegraph->nedges);
741
742  /* write weights of all nodes (scaled!) */
743  for( i = 0; i < tcliquegraph->nnodes; i++ )
744  fprintf(file, "%f\n", (double)tcliquegraph->weights[i]/scaleval);
745
746  /* write edges */
747  for( i = 0; i < tcliquegraph->nnodes; i++ )
748  {
750  fprintf(file, "%d %d\n", i, tcliquegraph->adjnodes[j]);
751  }
752
753  /* close file */
754  fclose(file);
755
756  return TRUE;
757 }
758
759 /** gets number of edges in the graph */
761  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
762  )
763 {
764  assert(tcliquegraph != NULL);
765
766  return tcliquegraph->nedges + tcliquegraph->ncachededges;
767 }
768
769 /** gets degree of nodes in graph */
771  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
772  )
773 {
774  assert(tcliquegraph != NULL);
775  assert(tcliquegraph->ncachededges == 0);
776
777  return tcliquegraph->degrees;
778 }
779
780 /** gets adjacent nodes of edges in graph */
782  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
783  )
784 {
785  assert(tcliquegraph != NULL);
786  assert(tcliquegraph->ncachededges == 0);
787
789 }
790
791 /** gets pointer to first adjacent edge of given node in graph */
793  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
794  int node /**< given node */
795  )
796 {
799
800  assert(tcliquegraph != NULL);
801  assert(tcliquegraph->ncachededges == 0);
802  assert(0 <= node && node < tcliquegraph->nnodes);
803
808
811
813 }
814
815 /** gets pointer to last adjacent edge of given node in graph */
817  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
818  int node /**< given node */
819  )
820 {
823 #ifndef NDEBUG
824  int* degrees;
825 #endif
826
827  assert(tcliquegraph != NULL);
828  assert(tcliquegraph->ncachededges == 0);
829  assert(0 <= node && node < tcliquegraph->nnodes);
830
832 #ifndef NDEBUG
833  degrees = tcliqueGetDegrees(tcliquegraph);
834 #endif
836  assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
838
840
843
845 }
846
847 /** prints graph data structure */
849  TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
850  )
851 {
852  const int* weights;
853  int* degrees;
854  int i;
855
856  assert(tcliquegraph != NULL);
857  assert(tcliquegraph->ncachededges == 0);
858
859  degrees = tcliqueGetDegrees(tcliquegraph);
860  weights = tcliqueGetWeights(tcliquegraph);
861
862  infoMessage("nnodes=%d, nedges=%d\n", tcliqueGetNNodes(tcliquegraph), tcliqueGetNEdges(tcliquegraph));
863  for( i = 0; i < tcliqueGetNNodes(tcliquegraph); i++ )
864  {
867
868  infoMessage("node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
869
873
875  {
877  }
878  infoMessage("]\n");
879  }
880 }
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
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)
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)
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