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