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 */ 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 } 581 } 582 583 if( !tcliqueCreate(tcliquegraph) ) 584 { 585 (void) fclose(file); 586 return FALSE; 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); 594 if( charresult == NULL ) 595 { 596 infoMessage("Error while reading probname in file %s.\n", filename); 597 (void) fclose(file); 598 return FALSE; 599 } 600 } 601 while( probname[sizeofprobname-2] != '\0' ); 602 603 /* set number of nodes and number of edges in graph */ 604 /* coverity[tainted_data] */ 605 result = fscanf(file, "%d", &(*tcliquegraph)->nnodes); 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; 611 } 612 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; 618 } 619 620 /* coverity[tainted_data] */ 621 result = fscanf(file, "%d", &(*tcliquegraph)->nedges); 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; 627 } 628 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; 634 } 635 636 /* set data structures for tclique, 637 * if an error occured, close the file before returning */ 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