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