1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program */ 4 /* TCLIQUE --- Algorithm for Maximum Cliques */ 5 /* */ 6 /* Copyright (C) 1996-2021 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 */ 52 enum TCLIQUE_Status 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 }; 59 typedef enum TCLIQUE_Status TCLIQUE_STATUS; 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 */ 131 SCIP_EXPORT 132 TCLIQUE_GETNNODES(tcliqueGetNNodes); 133 134 /** gets weight of nodes in the graph */ 135 SCIP_EXPORT 136 TCLIQUE_GETWEIGHTS(tcliqueGetWeights); 137 138 /** returns, whether the edge (node1, node2) is in the graph */ 139 SCIP_EXPORT 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 */ 144 SCIP_EXPORT 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 */ 155 SCIP_EXPORT 156 TCLIQUE_Bool tcliqueCreate( 157 TCLIQUE_GRAPH** tcliquegraph /**< pointer to store graph data structure */ 158 ); 159 160 /** frees graph data structure */ 161 SCIP_EXPORT 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) */ 167 SCIP_EXPORT 168 TCLIQUE_Bool tcliqueAddNode( 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 */ 175 SCIP_EXPORT 176 void tcliqueChangeWeight( 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 */ 188 SCIP_EXPORT 189 TCLIQUE_Bool tcliqueAddEdge( 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 */ 196 SCIP_EXPORT 197 TCLIQUE_Bool tcliqueFlush( 198 TCLIQUE_GRAPH* tcliquegraph /**< graph data structure */ 199 ); 200 201 /** loads graph data structure from file */ 202 SCIP_EXPORT 203 TCLIQUE_Bool tcliqueLoadFile( 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 */ 212 SCIP_EXPORT 213 TCLIQUE_Bool tcliqueSaveFile( 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 */ 221 SCIP_EXPORT 222 int tcliqueGetNEdges( 223 TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */ 224 ); 225 226 /** gets degree of nodes in graph */ 227 SCIP_EXPORT 228 int* tcliqueGetDegrees( 229 TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */ 230 ); 231 232 /** gets adjacent nodes of edges in graph */ 233 SCIP_EXPORT 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 */ 239 SCIP_EXPORT 240 int* tcliqueGetFirstAdjedge( 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 */ 246 SCIP_EXPORT 247 int* tcliqueGetLastAdjedge( 248 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */ 249 int node /**< given node */ 250 ); 251 252 /** prints graph data structure */ 253 SCIP_EXPORT 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 */ 266 SCIP_EXPORT 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 294