Scippy

SCIP

Solving Constraint Integer Programs

tclique.h
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.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 */
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 };
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
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
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
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
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
207  TCLIQUE_GRAPH* tcliquegraph /**< graph data structure */
208  );
209 
210 /** loads graph data structure from file */
211 SCIP_EXPORT
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
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
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
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
#define TCLIQUE_GETWEIGHTS(x)
Definition: tclique.h:105
enum TCLIQUE_Status TCLIQUE_STATUS
Definition: tclique.h:68
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
tclique defines
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
TCLIQUE_Bool tcliqueSaveFile(TCLIQUE_GRAPH *tcliquegraph, const char *filename, double scaleval, const char *probname)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
#define TCLIQUE_SELECTADJNODES(x)
Definition: tclique.h:130
void tcliquePrintGraph(TCLIQUE_GRAPH *tcliquegraph)
TCLIQUE_Bool tcliqueLoadFile(TCLIQUE_GRAPH **tcliquegraph, const char *filename, double scaleval, char *probname, int sizeofprobname)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
#define TCLIQUE_Bool
Definition: tclique.h:53
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
#define TCLIQUE_ISEDGE(x)
Definition: tclique.h:115
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
TCLIQUE_Status
Definition: tclique.h:61
SCIP_Real scaleval
Definition: cons_sos1.c:245
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
int tcliqueGetNEdges(TCLIQUE_GRAPH *tcliquegraph)
int * tcliqueGetAdjnodes(TCLIQUE_GRAPH *tcliquegraph)
#define TCLIQUE_GETNNODES(x)
Definition: tclique.h:97
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
int TCLIQUE_WEIGHT
Definition: tclique.h:48
#define TCLIQUE_NEWSOL(x)
Definition: tclique.h:88