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