SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
tclique_graph.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program */
4/* TCLIQUE --- Algorithm for Maximum Cliques */
5/* */
6/* Copyright (c) 1996-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"
43
44
45typedef struct _HEAD_ADJ
46{
47 int first;
48 int last;
50
51struct 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 */
77{
78 assert(tcliquegraph != NULL);
79
80 return tcliquegraph->nnodes;
81}
82
83/** gets weight of nodes in the graph */
85{
86 assert(tcliquegraph != NULL);
87
88 return tcliquegraph->weights;
89}
90
91/** returns, whether the edge (node1, node2) is in the graph */
93{
94 int* currentadjedge;
95 int* lastadjedge;
96 int tmp;
97
98 assert(tcliquegraph != NULL);
99 assert(tcliquegraph->ncachededges == 0);
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 }
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 */
136{
137 int nadjnodes;
138 int* currentadjedge;
139 int* lastadjedge;
140 int i;
141
142 assert(tcliquegraph != NULL);
143 assert(tcliquegraph->ncachededges == 0);
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]);
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 */
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 */
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 */
237static
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
258
259 return TRUE;
260}
261
262/** ensures, that arrays concerning cached edges in graph data structure can store at least num entries */
263static
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 */
290static
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 }
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) */
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 */
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 */
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);
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 */
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];
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];
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 */
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);
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 */
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 */
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 */
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 */
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 */
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);
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 */
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);
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 */
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
887 {
888 infoMessage("%d, ", *currentadjedge);
889 }
890 infoMessage("]\n");
891 }
892}
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define nnodes
Definition gastrans.c:74
assert(minobj< SCIPgetCutoffbound(scip))
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define BMSfreeMemory(ptr)
Definition memory.h:147
#define BMSreallocMemoryArray(ptr, num)
Definition memory.h:129
#define BMSallocMemoryArray(ptr, num)
Definition memory.h:125
#define BMSfreeMemoryArray(ptr)
Definition memory.h:149
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
#define BMSfreeMemoryArrayNull(ptr)
Definition memory.h:150
#define BMSallocMemory(ptr)
Definition memory.h:120
tclique user interface
#define TCLIQUE_GETWEIGHTS(x)
Definition tclique.h:105
#define TCLIQUE_GETNNODES(x)
Definition tclique.h:97
#define TCLIQUE_ISEDGE(x)
Definition tclique.h:115
#define TCLIQUE_SELECTADJNODES(x)
Definition tclique.h:130
int TCLIQUE_WEIGHT
Definition tclique.h:48
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition tclique.h:49
#define TCLIQUE_Bool
Definition tclique.h:53
tclique defines
#define ALLOC_FALSE(x)
Definition tclique_def.h:64
#define MAX(x, y)
Definition tclique_def.h:92
#define infoMessage
Definition tclique_def.h:88
static TCLIQUE_Bool tcliqueEnsureSizeCachedEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
void tcliquePrintGraph(TCLIQUE_GRAPH *tcliquegraph)
static TCLIQUE_Bool tcliqueEnsureSizeNodes(TCLIQUE_GRAPH *tcliquegraph, int num)
int tcliqueGetNEdges(TCLIQUE_GRAPH *tcliquegraph)
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
TCLIQUE_Bool tcliqueLoadFile(TCLIQUE_GRAPH **tcliquegraph, const char *filename, double scaleval, char *probname, int sizeofprobname)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
int * tcliqueGetAdjnodes(TCLIQUE_GRAPH *tcliquegraph)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
struct _HEAD_ADJ HEAD_ADJ
TCLIQUE_Bool tcliqueSaveFile(TCLIQUE_GRAPH *tcliquegraph, const char *filename, double scaleval, const char *probname)
static TCLIQUE_Bool tcliqueEnsureSizeEdges(TCLIQUE_GRAPH *tcliquegraph, int num)
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)