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