1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* TCLIQUE --- Algorithm for Maximum Cliques */
5 /* */
6 /* Copyright (C) 1996-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* TCLIQUE is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with TCLIQUE; see the file COPYING. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file tclique_graph.c
17 * @ingroup OTHER_CFILES
18 * @brief graph data part of algorithm for maximum cliques
19 * @author Tobias Achterberg
20 * @author Ralf Borndoerfer
21 * @author Zoltan Kormos
22 * @author Kati Wolter
23 */
24
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26
27 #include <stdio.h>
28 #include <string.h>
29 #include <assert.h>
30
31 #include "tclique/tclique.h"
32 #include "tclique/tclique_def.h"
33 #include "blockmemshell/memory.h"
34
35
36 typedef struct _HEAD_ADJ
37 {
38 int first;
39 int last;
40 } HEAD_ADJ;
41
42 struct TCLIQUE_Graph
43 {
44 int nnodes; /**< number of nodes in graph */
45 int nedges; /**< number of edges in graph */
46 TCLIQUE_WEIGHT* weights; /**< weight of nodes */
47 int* degrees; /**< degree of nodes */
48 int* adjnodes; /**< adjacent nodes of edges */
49 HEAD_ADJ* adjedges; /**< pointer to first and one after last adjacent edge of nodes */
50 int sizenodes; /**< size of arrays concerning nodes (weights, degrees and adjedges) */
51 int sizeedges; /**< size of arrays concerning edges (adjnodes) */
52 int* cacheddegrees; /**< number of adjacent cached edges for each node */
53 int* cachedorigs; /**< origin nodes of cached edges */
54 int* cacheddests; /**< destination nodes of cached edges */
55 int ncachededges; /**< number of cached edges (not yet inserted in all data structures) */
56 int sizecachededges; /**< size of arrays concerning cached edges */
57 };
58
59
60
61
62 /*
63 * Interface Methods used by the TClique algorithm
64 */
65
66 /** gets number of nodes in the graph */
TCLIQUE_GETNNODES(tcliqueGetNNodes)67 TCLIQUE_GETNNODES(tcliqueGetNNodes)
68 {
69 assert(tcliquegraph != NULL);
70
71 return tcliquegraph->nnodes;
72 }
73
74 /** gets weight of nodes in the graph */
TCLIQUE_GETWEIGHTS(tcliqueGetWeights)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 */
TCLIQUE_ISEDGE(tcliqueIsEdge)83 TCLIQUE_ISEDGE(tcliqueIsEdge)
84 {
85 int* currentadjedge;
86 int* lastadjedge;
87 int tmp;
88
89 assert(tcliquegraph != NULL);
90 assert(tcliquegraph->ncachededges == 0);
91 assert(0 <= node1 && node1 < tcliquegraph->nnodes);
92 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
93
94 if( node1 < node2 )
95 {
96 tmp = node1;
97 node1 = node2;
98 node2 = tmp;
99 }
100
101 currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, node1);
102 lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, node1);
103
104 if( currentadjedge > lastadjedge || *lastadjedge < node2 )
105 return FALSE;
106
107 /* checks if node2 is contained in adjacency list of node1
108 * (list is ordered by adjacent nodes) */
109 while( currentadjedge <= lastadjedge )
110 {
111 if( *currentadjedge >= node2 )
112 {
113 if( *currentadjedge == node2 )
114 return TRUE;
115 else
116 break;
117 }
118 currentadjedge++;
119 }
120
121 return FALSE;
122 }
123
124 /** selects all nodes from a given set of nodes which are adjacent to a given node
125 * and returns the number of selected nodes */
TCLIQUE_SELECTADJNODES(tcliqueSelectAdjnodes)126 TCLIQUE_SELECTADJNODES(tcliqueSelectAdjnodes)
127 {
128 int nadjnodes;
129 int* currentadjedge;
130 int* lastadjedge;
131 int i;
132
133 assert(tcliquegraph != NULL);
134 assert(tcliquegraph->ncachededges == 0);
135 assert(0 <= node && node < tcliquegraph->nnodes);
136 assert(nnodes == 0 || nodes != NULL);
137 assert(adjnodes != NULL);
138
139 nadjnodes = 0;
140 currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, node);
141 lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, node);
142
143 /* checks for each node in given set nodes, if it is adjacent to given node
144 * (adjacent nodes are ordered by node index)
145 */
146 for( i = 0; i < nnodes; i++ )
147 {
148 assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
149 assert(i == 0 || nodes[i-1] < nodes[i]);
150 for( ; currentadjedge <= lastadjedge; currentadjedge++ )
151 {
152 if( *currentadjedge >= nodes[i] )
153 {
154 /* current node is adjacent to given node */
155 if( *currentadjedge == nodes[i] )
156 {
157 adjnodes[nadjnodes] = nodes[i];
158 nadjnodes++;
159 }
160 break;
161 }
162 }
163 }
164
165 return nadjnodes;
166 }
167
168
169
170
171 /*
172 * External Interface Methods to access the graph (this can be changed without affecting the TClique algorithm)
173 */
174
175 /** creates graph data structure */
tcliqueCreate(TCLIQUE_GRAPH ** tcliquegraph)176 TCLIQUE_Bool tcliqueCreate(
177 TCLIQUE_GRAPH** tcliquegraph /**< pointer to store graph data structure */
178 )
179 {
180 assert(tcliquegraph != NULL);
181
182 ALLOC_FALSE( BMSallocMemory(tcliquegraph) );
183
184 (*tcliquegraph)->nnodes = 0;
185 (*tcliquegraph)->nedges = 0;
186 (*tcliquegraph)->weights = NULL;
187 (*tcliquegraph)->degrees = NULL;
188 (*tcliquegraph)->adjnodes = NULL;
189 (*tcliquegraph)->adjedges = NULL;
190 (*tcliquegraph)->sizenodes = 0;
191 (*tcliquegraph)->sizeedges = 0;
192 (*tcliquegraph)->cacheddegrees = NULL;
193 (*tcliquegraph)->cachedorigs = NULL;
194 (*tcliquegraph)->cacheddests = NULL;
195 (*tcliquegraph)->ncachededges = 0;
196 (*tcliquegraph)->sizecachededges = 0;
197
198 return TRUE;
199 }
200
201 /** frees graph data structure */
tcliqueFree(TCLIQUE_GRAPH ** tcliquegraph)202 void tcliqueFree(
203 TCLIQUE_GRAPH** tcliquegraph /**< pointer to graph data structure */
204 )
205 {
206 assert(tcliquegraph != NULL);
207
208 if( *tcliquegraph != NULL )
209 {
210 if ( (*tcliquegraph)->adjedges != NULL )
211 {
212 BMSfreeMemoryArray(&(*tcliquegraph)->adjedges);
213 BMSfreeMemoryArray(&(*tcliquegraph)->adjnodes);
214 BMSfreeMemoryArray(&(*tcliquegraph)->degrees);
215 BMSfreeMemoryArray(&(*tcliquegraph)->weights);
216 }
217 if ( (*tcliquegraph)->cacheddegrees )
218 {
219 BMSfreeMemoryArrayNull(&(*tcliquegraph)->cacheddegrees);
220 BMSfreeMemoryArrayNull(&(*tcliquegraph)->cachedorigs);
221 BMSfreeMemoryArrayNull(&(*tcliquegraph)->cacheddests);
222 }
223 BMSfreeMemory(tcliquegraph);
224 }
225 }
226
227 /** ensures, that arrays concerning edges in graph data structure can store at least num entries */
228 static
tcliqueEnsureSizeEdges(TCLIQUE_GRAPH * tcliquegraph,int num)229 TCLIQUE_Bool tcliqueEnsureSizeEdges(
230 TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
231 int num /**< minimum number of entries concerning edges to store */
232 )
233 {
234 assert(tcliquegraph != NULL);
235
236 if( num > tcliquegraph->sizeedges )
237 {
238 int newsize;
239
240 newsize = 2*tcliquegraph->sizeedges;
241 if( newsize < num )
242 newsize = num;
243
244 ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->adjnodes, newsize) );
245 tcliquegraph->sizeedges = newsize;
246 }
247
248 assert(num <= tcliquegraph->sizeedges);
249
250 return TRUE;
251 }
252
253 /** ensures, that arrays concerning cached edges in graph data structure can store at least num entries */
254 static
tcliqueEnsureSizeCachedEdges(TCLIQUE_GRAPH * tcliquegraph,int num)255 TCLIQUE_Bool tcliqueEnsureSizeCachedEdges(
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
tcliqueEnsureSizeNodes(TCLIQUE_GRAPH * tcliquegraph,int num)282 TCLIQUE_Bool tcliqueEnsureSizeNodes(
283 TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
284 int num /**< minimum number of entries concerning nodes to store */
285 )
286 {
287 assert(tcliquegraph != NULL);
288
289 if( !tcliqueEnsureSizeEdges(tcliquegraph, 1) )
290 return FALSE;
291 assert(tcliquegraph->adjnodes != NULL);
292
293 if( num > tcliquegraph->sizenodes )
294 {
295 int newsize;
296 int i;
297
298 newsize = 2*tcliquegraph->sizenodes;
299 if( newsize < num )
300 newsize = num;
301
302 ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->weights, newsize) );
303 ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->degrees, newsize) );
304 ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->adjedges, newsize) );
305
306 for( i = tcliquegraph->sizenodes; i < newsize; i++ )
307 {
308 tcliquegraph->weights[i] = 0;
309 tcliquegraph->degrees[i] = 0;
310 tcliquegraph->adjedges[i].first = tcliquegraph->nedges;
311 tcliquegraph->adjedges[i].last = tcliquegraph->nedges;
312 }
313
314 if( tcliquegraph->ncachededges > 0 )
315 {
316 assert(tcliquegraph->cacheddegrees != NULL);
317 ALLOC_FALSE( BMSreallocMemoryArray(&tcliquegraph->cacheddegrees, newsize) );
318 for( i = tcliquegraph->sizenodes; i < newsize; i++ )
319 tcliquegraph->cacheddegrees[i] = 0;
320 }
321
322 tcliquegraph->sizenodes = newsize;
323 }
324 assert(num <= tcliquegraph->sizenodes);
325
326 return TRUE;
327 }
328
329
330 /** adds nodes up to the given node number to graph data structure (intermediate nodes have weight 0) */
tcliqueAddNode(TCLIQUE_GRAPH * tcliquegraph,int node,TCLIQUE_WEIGHT weight)331 TCLIQUE_Bool tcliqueAddNode(
332 TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */
333 int node, /**< node number to add */
334 TCLIQUE_WEIGHT weight /**< weight of node to add */
335 )
336 {
337 assert(weight >= 0);
338
339 if( !tcliqueEnsureSizeNodes(tcliquegraph, node + 1) )
340 return FALSE;
341
342 tcliquegraph->weights[node] = weight;
343
344 assert(tcliquegraph->degrees[node] == 0);
345 assert(tcliquegraph->adjedges[node].first <= tcliquegraph->nedges);
346 assert(tcliquegraph->adjedges[node].last == tcliquegraph->adjedges[node].first);
347 tcliquegraph->nnodes = MAX(tcliquegraph->nnodes, node+1);
348
349 return TRUE;
350 }
351
352 /** changes weight of node in graph data structure */
tcliqueChangeWeight(TCLIQUE_GRAPH * tcliquegraph,int node,TCLIQUE_WEIGHT weight)353 void tcliqueChangeWeight(
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 */
tcliqueAddEdge(TCLIQUE_GRAPH * tcliquegraph,int node1,int node2)371 TCLIQUE_Bool tcliqueAddEdge(
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 */
tcliqueFlush(TCLIQUE_GRAPH * tcliquegraph)408 TCLIQUE_Bool tcliqueFlush(
409 TCLIQUE_GRAPH* tcliquegraph /**< graph data structure */
410 )
411 {
412 assert(tcliquegraph != NULL);
413
414 /* check, whether there are cached edges */
415 if( tcliquegraph->ncachededges > 0 )
416 {
417 int ninsertedholes;
418 int pos;
419 int n;
420 int i;
421
422 /* reallocate adjnodes array to be able to store all additional edges */
423 if( !tcliqueEnsureSizeEdges(tcliquegraph, tcliquegraph->nedges + tcliquegraph->ncachededges) )
424 return FALSE;
425 assert(tcliquegraph->adjnodes != NULL);
426 assert(tcliquegraph->adjedges != NULL);
427
428 /* move the old edges in the adjnodes array, s.t. there is enough free space for the additional edges */
429 ninsertedholes = 0;
430 pos = tcliquegraph->nedges + tcliquegraph->ncachededges - 1;
431 for( n = tcliquegraph->nnodes-1; ; --n ) /* no abort criterion, because at n == 0, the loop is break'ed */
432 {
433 int olddegree;
434
435 assert(n >= 0);
436 assert(tcliquegraph->adjedges[n].last - tcliquegraph->adjedges[n].first == tcliquegraph->degrees[n]);
437
438 /* increase the degree of the node */
439 olddegree = tcliquegraph->degrees[n];
440 tcliquegraph->degrees[n] += tcliquegraph->cacheddegrees[n];
441
442 /* skip space for new edges */
443 pos -= tcliquegraph->cacheddegrees[n];
444 ninsertedholes += tcliquegraph->cacheddegrees[n];
445 assert(ninsertedholes <= tcliquegraph->ncachededges);
446 if( ninsertedholes == tcliquegraph->ncachededges )
447 break;
448 assert(n > 0);
449
450 /* move old edges */
451 for( i = tcliquegraph->adjedges[n].last - 1; i >= tcliquegraph->adjedges[n].first; --i, --pos )
452 {
453 assert(0 <= i && i < pos && pos < tcliquegraph->nedges + tcliquegraph->ncachededges);
454 tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[i];
455 }
456
457 /* adjust the first and last edge pointers of the node */
458 tcliquegraph->adjedges[n].first = pos+1;
459 tcliquegraph->adjedges[n].last = pos+1 + olddegree;
460
461 assert(n == tcliquegraph->nnodes-1
462 || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
463 }
464 assert(ninsertedholes == tcliquegraph->ncachededges);
465 assert(tcliquegraph->adjedges[n].last == pos+1);
466 #ifndef NDEBUG
467 for( --n; n >= 0; --n )
468 assert(tcliquegraph->cacheddegrees[n] == 0);
469 #endif
470
471 /* insert the cached edges into the adjnodes array */
472 for( i = 0; i < tcliquegraph->ncachededges; ++i )
473 {
474 int dest;
475
476 n = tcliquegraph->cachedorigs[i];
477 dest = tcliquegraph->cacheddests[i];
478 assert(0 <= n && n < tcliquegraph->nnodes);
479 assert(0 <= dest && dest < tcliquegraph->nnodes);
480 assert(tcliquegraph->adjedges[n].last <= tcliquegraph->nedges + tcliquegraph->ncachededges);
481 assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
482 assert(n == tcliquegraph->nnodes-1
483 || tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n] == tcliquegraph->adjedges[n+1].first);
484
485 /* edges of each node must be sorted by increasing destination node number */
486 for( pos = tcliquegraph->adjedges[n].last;
487 pos > tcliquegraph->adjedges[n].first && dest < tcliquegraph->adjnodes[pos-1]; --pos )
488 {
489 tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[pos-1];
490 }
491 tcliquegraph->adjnodes[pos] = dest;
492 tcliquegraph->adjedges[n].last++;
493
494 assert(n == tcliquegraph->nnodes-1 || tcliquegraph->adjedges[n].last <= tcliquegraph->adjedges[n+1].first);
495 }
496
497 /* update the number of edges */
498 tcliquegraph->nedges += tcliquegraph->ncachededges;
499
500 /* free the cache */
501 BMSfreeMemoryArray(&tcliquegraph->cacheddegrees);
502 BMSfreeMemoryArray(&tcliquegraph->cachedorigs);
503 BMSfreeMemoryArray(&tcliquegraph->cacheddests);
504 tcliquegraph->ncachededges = 0;
505 tcliquegraph->sizecachededges = 0;
506 }
507
508 /* the cache should now be freed */
509 assert(tcliquegraph->ncachededges == 0);
510 assert(tcliquegraph->sizecachededges == 0);
511 assert(tcliquegraph->cacheddegrees == NULL);
512 assert(tcliquegraph->cachedorigs == NULL);
513 assert(tcliquegraph->cacheddests == NULL);
514
515 #ifndef NDEBUG
516 /* check integrity of the data structures */
517 {
518 int pos;
519 int n;
520
521 pos = 0;
522 for( n = 0; n < tcliquegraph->nnodes; ++n )
523 {
524 int i;
525
526 assert(tcliquegraph->adjedges[n].first == pos);
527 assert(tcliquegraph->adjedges[n].last == tcliquegraph->adjedges[n].first + tcliquegraph->degrees[n]);
528
529 for( i = tcliquegraph->adjedges[n].first; i < tcliquegraph->adjedges[n].last-1; ++i )
530 {
531 assert(tcliquegraph->adjnodes[i] < tcliquegraph->adjnodes[i+1]);
532 }
533 pos = tcliquegraph->adjedges[n].last;
534 }
535 assert(pos == tcliquegraph->nedges);
536 }
537 #endif
538
539 return TRUE;
540 }
541
542 /** loads graph data structure from file */
tcliqueLoadFile(TCLIQUE_GRAPH ** tcliquegraph,const char * filename,double scaleval,char * probname,int sizeofprobname)543 TCLIQUE_Bool tcliqueLoadFile(
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;
701 (*tcliquegraph)->adjedges[currentnode].first = i;
702 (*tcliquegraph)->adjedges[currentnode].last = (*tcliquegraph)->adjedges[currentnode].first;
703 }
704 (*tcliquegraph)->degrees[currentnode]++;
705 (*tcliquegraph)->adjnodes[i] = node2;
706 (*tcliquegraph)->adjedges[currentnode].last++;
707 }
708
709 /* close file */
710 (void) fclose(file);
711
712 return TRUE;
713 }
714
715 /** saves graph data structure to file */
tcliqueSaveFile(TCLIQUE_GRAPH * tcliquegraph,const char * filename,double scaleval,const char * probname)716 TCLIQUE_Bool tcliqueSaveFile(
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 {
749 for( j = tcliquegraph->adjedges[i].first; j < tcliquegraph->adjedges[i].last; j++ )
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 */
tcliqueGetNEdges(TCLIQUE_GRAPH * tcliquegraph)760 int tcliqueGetNEdges(
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 */
tcliqueGetDegrees(TCLIQUE_GRAPH * tcliquegraph)770 int* tcliqueGetDegrees(
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 */
tcliqueGetAdjnodes(TCLIQUE_GRAPH * tcliquegraph)781 int* tcliqueGetAdjnodes(
782 TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */
783 )
784 {
785 assert(tcliquegraph != NULL);
786 assert(tcliquegraph->ncachededges == 0);
787
788 return tcliquegraph->adjnodes;
789 }
790
791 /** gets pointer to first adjacent edge of given node in graph */
tcliqueGetFirstAdjedge(TCLIQUE_GRAPH * tcliquegraph,int node)792 int* tcliqueGetFirstAdjedge(
793 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
794 int node /**< given node */
795 )
796 {
797 HEAD_ADJ* adjedges;
798 int* adjnodes;
799
800 assert(tcliquegraph != NULL);
801 assert(tcliquegraph->ncachededges == 0);
802 assert(0 <= node && node < tcliquegraph->nnodes);
803
804 adjedges = tcliquegraph->adjedges;
805 assert(adjedges != NULL);
806 assert(adjedges[node].first >= 0);
807 assert(adjedges[node].first <= tcliqueGetNEdges(tcliquegraph));
808
809 adjnodes = tcliqueGetAdjnodes(tcliquegraph);
810 assert(adjnodes != NULL);
811
812 return &adjnodes[adjedges[node].first];
813 }
814
815 /** gets pointer to last adjacent edge of given node in graph */
tcliqueGetLastAdjedge(TCLIQUE_GRAPH * tcliquegraph,int node)816 int* tcliqueGetLastAdjedge(
817 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
818 int node /**< given node */
819 )
820 {
821 HEAD_ADJ* adjedges;
822 int* adjnodes;
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
831 adjedges = tcliquegraph->adjedges;
832 #ifndef NDEBUG
833 degrees = tcliqueGetDegrees(tcliquegraph);
834 #endif
835 assert(adjedges != NULL);
836 assert(degrees[node] == 0 || adjedges[node].last-1 >= 0);
837 assert(adjedges[node].last-1 <= tcliqueGetNEdges(tcliquegraph));
838
839 assert(adjedges[node].last - adjedges[node].first == degrees[node]);
840
841 adjnodes = tcliqueGetAdjnodes(tcliquegraph);
842 assert(adjnodes != NULL);
843
844 return &adjnodes[adjedges[node].last-1];
845 }
846
847 /** prints graph data structure */
tcliquePrintGraph(TCLIQUE_GRAPH * tcliquegraph)848 void tcliquePrintGraph(
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 {
865 int* currentadjedge;
866 int* lastadjedge;
867
868 infoMessage("node %d: weight=%d, degree=%d, adjnodes=\n[ ", i, weights[i], degrees[i]);
869
870 currentadjedge = tcliqueGetFirstAdjedge(tcliquegraph, i);
871 lastadjedge = tcliqueGetLastAdjedge(tcliquegraph, i);
872 assert(lastadjedge + 1 - currentadjedge == degrees[i]);
873
874 for( ; currentadjedge <= lastadjedge; currentadjedge++ )
875 {
876 infoMessage("%d, ", *currentadjedge);
877 }
878 infoMessage("]\n");
879 }
880 }
881