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.h
26   	 * @brief  tclique user interface
27   	 * @author Tobias Achterberg
28   	 * @author Ralf Borndoerfer
29   	 * @author Zoltan Kormos
30   	 * @author Kati Wolter
31   	 */
32   	
33   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34   	
35   	#ifndef __TCLIQUE_H__
36   	#define __TCLIQUE_H__
37   	
38   	#ifdef __cplusplus
39   	extern "C" {
40   	#endif
41   	
42   	#include "tclique/tclique_def.h"
43   	
44   	/*
45   	 * Data Types and Structures
46   	 */
47   	
48   	typedef int  TCLIQUE_WEIGHT;                 /**< type used for node weights in the graph */
49   	typedef struct TCLIQUE_Graph TCLIQUE_GRAPH;  /**< user defined structure for storing the graph, passed to graph callbacks */
50   	typedef struct TCLIQUE_Data TCLIQUE_DATA;    /**< user defined data to pass to new solution callback method */
51   	
52   	#ifndef TCLIQUE_Bool
53   	#define TCLIQUE_Bool unsigned int            /**< type used for boolean values */
54   	#endif
55   	#ifndef TRUE
56   	#define TRUE  1                              /**< boolean value TRUE */
57   	#define FALSE 0                              /**< boolean value FALSE */
58   	#endif
59   	
60   	/** return status of the TCLIQUE algorithm */
61   	enum TCLIQUE_Status
62   	{
63   	   TCLIQUE_ERROR           = 0,         /**< an error occurred */
64   	   TCLIQUE_NODELIMIT       = 1,         /**< the node limit was reached */
65   	   TCLIQUE_USERABORT       = 2,         /**< the user call back function aborted the solving process */
66   	   TCLIQUE_OPTIMAL         = 3          /**< the optimal solution was found */
67   	};
68   	typedef enum TCLIQUE_Status TCLIQUE_STATUS;
69   	
70   	
71   	
72   	
73   	/*
74   	 * User Callback Methods
75   	 */
76   	
77   	/** user callback method which is called whenever a feasible clique was found
78   	 *  input:
79   	 *   - tcliquedata  : user data given to tcliqueMaxClique()
80   	 *   - cliquenodes  : array with nodes of the clique
81   	 *   - ncliquenodes : number of nodes in the clique
82   	 *   - cliqueweight : weight of the clique
83   	 *  output:
84   	 *   - minweight    : new minimal weight for feasible cliques
85   	 *   - acceptsol    : setting TRUE makes clique the new best clique, and updates minweight
86   	 *   - stopsolving  : setting TRUE aborts the search for cliques
87   	 */
88   	#define TCLIQUE_NEWSOL(x) void x (TCLIQUE_DATA* tcliquedata, int* cliquenodes, int ncliquenodes, \
89   	      TCLIQUE_WEIGHT cliqueweight, TCLIQUE_WEIGHT* minweight, TCLIQUE_Bool* acceptsol, TCLIQUE_Bool* stopsolving)
90   	
91   	/** user callback method to get number of nodes in the graph
92   	 *  input:
93   	 *   - tcliquegraph : user defined graph data structure given to tcliqueMaxClique()
94   	 *  returns:
95   	 *   number of nodes in the graph
96   	 */
97   	#define TCLIQUE_GETNNODES(x) int x (TCLIQUE_GRAPH* tcliquegraph)
98   	
99   	/** user callback method to get weights of nodes in the graph
100  	 *  input:
101  	 *   - tcliquegraph : user defined graph data structure given to tcliqueMaxClique()
102  	 *  returns:
103  	 *   array of node weights (of length at least equal to the number of nodes in the graph)
104  	 */
105  	#define TCLIQUE_GETWEIGHTS(x) const TCLIQUE_WEIGHT* x (TCLIQUE_GRAPH* tcliquegraph)
106  	
107  	/** user callback method to return whether the edge (node1, node2) is in the graph
108  	 *  input:
109  	 *   - tcliquegraph : user defined graph data structure given to tcliqueMaxClique()
110  	 *   - node1        : start node of edge (tail)
111  	 *   - node2        : end node of edge (head)
112  	 *  returns:
113  	 *   TRUE if edge is in the graph, FALSE otherwise
114  	 */
115  	#define TCLIQUE_ISEDGE(x) TCLIQUE_Bool x (TCLIQUE_GRAPH* tcliquegraph, int node1, int node2)
116  	
117  	/** user callback method to select all nodes from a given set of nodes which are adjacent to a given node
118  	 *  input:
119  	 *   - tcliquegraph : user defined graph data structure given to tcliqueMaxClique()
120  	 *   - node         : node to select adjacent nodes from
121  	 *   - nodes        : array of nodes to select nodes from
122  	 *   - nnodes       : number of nodes in 'nodes' array
123  	 *   - adjnodes     : pointer to memory to store the resulting nodes
124  	 *                    'adjnodes' and 'nodes' may point to the same memory location
125  	 *  output:
126  	 *   - adjnodes     : array of nodes that are contained in 'nodes' and that are adjacent to 'node'
127  	 *  returns:
128  	 *   number of nodes in 'adjnodes'
129  	 */
130  	#define TCLIQUE_SELECTADJNODES(x) int x (TCLIQUE_GRAPH* tcliquegraph, int node, int* nodes, int nnodes, int* adjnodes)
131  	
132  	
133  	
134  	
135  	/*
136  	 * Default Graph Implementation: Interface Methods used by the TClique algorithm
137  	 */
138  	
139  	/** gets number of nodes in the graph */
140  	SCIP_EXPORT
141  	TCLIQUE_GETNNODES(tcliqueGetNNodes);
142  	
143  	/** gets weight of nodes in the graph */
144  	SCIP_EXPORT
145  	TCLIQUE_GETWEIGHTS(tcliqueGetWeights);
146  	
147  	/** returns, whether the edge (node1, node2) is in the graph */
148  	SCIP_EXPORT
149  	TCLIQUE_ISEDGE(tcliqueIsEdge);
150  	
151  	/** selects all nodes from a given set of nodes which are adjacent to a given node
152  	 *  and returns the number of selected nodes */
153  	SCIP_EXPORT
154  	TCLIQUE_SELECTADJNODES(tcliqueSelectAdjnodes);
155  	
156  	
157  	
158  	
159  	/*
160  	 * Default Graph Implementation: External Interface Methods to access the graph
161  	 */
162  	
163  	/** creates graph data structure */
164  	SCIP_EXPORT
165  	TCLIQUE_Bool tcliqueCreate(
166  	   TCLIQUE_GRAPH**       tcliquegraph        /**< pointer to store graph data structure */
167  	   );
168  	
169  	/** frees graph data structure */
170  	SCIP_EXPORT
171  	void tcliqueFree(
172  	   TCLIQUE_GRAPH**       tcliquegraph        /**< pointer to graph data structure */
173  	   );
174  	
175  	/** adds nodes up to the given node number to graph data structure (intermediate nodes have weight 0) */
176  	SCIP_EXPORT
177  	TCLIQUE_Bool tcliqueAddNode(
178  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< graph data structure */
179  	   int                   node,               /**< node number to add */
180  	   TCLIQUE_WEIGHT        weight              /**< weight of node to add */
181  	   );
182  	
183  	/** changes weight of node in graph data structure */
184  	SCIP_EXPORT
185  	void tcliqueChangeWeight(
186  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< graph data structure */
187  	   int                   node,               /**< node to set new weight */
188  	   TCLIQUE_WEIGHT        weight              /**< new weight of node (allready scaled) */
189  	   );
190  	
191  	/** adds edge (node1, node2) to graph data structure (node1 and node2 have to be contained in
192  	 *  graph data structure)
193  	 *
194  	 *  New edges are cached, s.t. the graph data structures are not correct until a call to tcliqueFlush();
195  	 *  you have to make sure, that no double edges are inserted.
196  	 */
197  	SCIP_EXPORT
198  	TCLIQUE_Bool tcliqueAddEdge(
199  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< graph data structure */
200  	   int                   node1,              /**< start node of edge to add */
201  	   int                   node2               /**< end node of edge to add */
202  	   );
203  	
204  	/** inserts all cached edges into the data structures */
205  	SCIP_EXPORT
206  	TCLIQUE_Bool tcliqueFlush(
207  	   TCLIQUE_GRAPH*        tcliquegraph        /**< graph data structure */
208  	   );
209  	
210  	/** loads graph data structure from file */
211  	SCIP_EXPORT
212  	TCLIQUE_Bool tcliqueLoadFile(
213  	   TCLIQUE_GRAPH**       tcliquegraph,       /**< pointer to store graph data structure */
214  	   const char*           filename,           /**< name of file with graph data */
215  	   double                scaleval,           /**< value to scale weights (only integral part of scaled weights is considered) */
216  	   char*                 probname,           /**< buffer to store the name of the problem */
217  	   int                   sizeofprobname      /**< size of buffer to store the name of the problem */
218  	   );
219  	
220  	/** saves graph data structure to file */
221  	SCIP_EXPORT
222  	TCLIQUE_Bool tcliqueSaveFile(
223  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< graph data structure */
224  	   const char*           filename,           /**< name of file to create */
225  	   double                scaleval,           /**< value to unscale weights with */
226  	   const char*           probname            /**< name of the problem */
227  	   );
228  	
229  	/** gets number of edges in the graph */
230  	SCIP_EXPORT
231  	int tcliqueGetNEdges(
232  	   TCLIQUE_GRAPH*        tcliquegraph        /**< pointer to graph data structure */
233  	   );
234  	
235  	/** gets degree of nodes in graph */
236  	SCIP_EXPORT
237  	int* tcliqueGetDegrees(
238  	   TCLIQUE_GRAPH*        tcliquegraph        /**< pointer to graph data structure */
239  	   );
240  	
241  	/** gets adjacent nodes of edges in graph */
242  	SCIP_EXPORT
243  	int* tcliqueGetAdjnodes(
244  	   TCLIQUE_GRAPH*        tcliquegraph        /**< pointer to graph data structure */
245  	   );
246  	
247  	/** gets pointer to first adjacent edge of given node in graph */
248  	SCIP_EXPORT
249  	int* tcliqueGetFirstAdjedge(
250  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< pointer to graph data structure */
251  	   int                   node                /**< given node */
252  	   );
253  	
254  	/** gets pointer to last adjacent edge of given node in graph */
255  	SCIP_EXPORT
256  	int* tcliqueGetLastAdjedge(
257  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< pointer to graph data structure */
258  	   int                   node                /**< given node */
259  	   );
260  	
261  	/** prints graph data structure */
262  	SCIP_EXPORT
263  	void tcliquePrintGraph(
264  	   TCLIQUE_GRAPH*        tcliquegraph        /**< pointer to graph data structure */
265  	   );
266  	
267  	
268  	
269  	
270  	/*
271  	 * Interface Methods
272  	 */
273  	
274  	/** finds maximum weight clique */
275  	SCIP_EXPORT
276  	void tcliqueMaxClique(
277  	   TCLIQUE_GETNNODES((*getnnodes)),          /**< user function to get the number of nodes */
278  	   TCLIQUE_GETWEIGHTS((*getweights)),        /**< user function to get the node weights */
279  	   TCLIQUE_ISEDGE((*isedge)),                /**< user function to check for existence of an edge */
280  	   TCLIQUE_SELECTADJNODES((*selectadjnodes)), /**< user function to select adjacent edges */
281  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< pointer to graph data structure that is passed to graph callbacks */
282  	   TCLIQUE_NEWSOL((*newsol)),                /**< user function to call on every new solution */
283  	   TCLIQUE_DATA*         tcliquedata,        /**< user data to pass to new solution callback function */
284  	   int*                  maxcliquenodes,     /**< pointer to store nodes of the maximum weight clique */
285  	   int*                  nmaxcliquenodes,    /**< pointer to store number of nodes in the maximum weight clique */
286  	   TCLIQUE_WEIGHT*       maxcliqueweight,    /**< pointer to store weight of the maximum weight clique */
287  	   TCLIQUE_WEIGHT        maxfirstnodeweight, /**< maximum weight of branching nodes in level 0; 0 if not used
288  	                                              *   for cliques with at least one fractional node) */
289  	   TCLIQUE_WEIGHT        minweight,          /**< lower bound for weight of generated cliques */
290  	   int                   maxntreenodes,	     /**< maximal number of nodes of b&b tree */
291  	   int                   backtrackfreq,      /**< frequency to backtrack to first level of tree (0: no premature backtracking) */
292  	   int                   maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */
293  	   int                   fixednode,          /**< node that is forced to be in the clique, or -1; must have positive weight */
294  	   int*                  ntreenodes,         /**< pointer to store the number of used tree nodes (or NULL) */
295  	   TCLIQUE_STATUS*       status              /**< pointer to store the status of the solving call */
296  	   );
297  	
298  	#ifdef __cplusplus
299  	}
300  	#endif
301  	
302  	#endif
303