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