/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* */ /* This file is part of the program */ /* TCLIQUE --- Algorithm for Maximum Cliques */ /* */ /* Copyright 1996-2022 Zuse Institute Berlin */ /* */ /* Licensed under the Apache License, Version 2.0 (the "License"); */ /* you may not use this file except in compliance with the License. */ /* You may obtain a copy of the License at */ /* */ /* http://www.apache.org/licenses/LICENSE-2.0 */ /* */ /* Unless required by applicable law or agreed to in writing, software */ /* distributed under the License is distributed on an "AS IS" BASIS, */ /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ /* See the License for the specific language governing permissions and */ /* limitations under the License. */ /* */ /* You should have received a copy of the Apache-2.0 license */ /* along with TCLIQUE; see the file LICENSE. */ /* */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /**@file tclique.h * @brief tclique user interface * @author Tobias Achterberg * @author Ralf Borndoerfer * @author Zoltan Kormos * @author Kati Wolter */ /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ #ifndef __TCLIQUE_H__ #define __TCLIQUE_H__ #ifdef __cplusplus extern "C" { #endif #include "tclique/tclique_def.h" /* * Data Types and Structures */ typedef int TCLIQUE_WEIGHT; /**< type used for node weights in the graph */ typedef struct TCLIQUE_Graph TCLIQUE_GRAPH; /**< user defined structure for storing the graph, passed to graph callbacks */ typedef struct TCLIQUE_Data TCLIQUE_DATA; /**< user defined data to pass to new solution callback method */ #ifndef TCLIQUE_Bool #define TCLIQUE_Bool unsigned int /**< type used for boolean values */ #endif #ifndef TRUE #define TRUE 1 /**< boolean value TRUE */ #define FALSE 0 /**< boolean value FALSE */ #endif /** return status of the TCLIQUE algorithm */ enum TCLIQUE_Status { TCLIQUE_ERROR = 0, /**< an error occurred */ TCLIQUE_NODELIMIT = 1, /**< the node limit was reached */ TCLIQUE_USERABORT = 2, /**< the user call back function aborted the solving process */ TCLIQUE_OPTIMAL = 3 /**< the optimal solution was found */ }; typedef enum TCLIQUE_Status TCLIQUE_STATUS; /* * User Callback Methods */ /** user callback method which is called whenever a feasible clique was found * input: * - tcliquedata : user data given to tcliqueMaxClique() * - cliquenodes : array with nodes of the clique * - ncliquenodes : number of nodes in the clique * - cliqueweight : weight of the clique * output: * - minweight : new minimal weight for feasible cliques * - acceptsol : setting TRUE makes clique the new best clique, and updates minweight * - stopsolving : setting TRUE aborts the search for cliques */ #define TCLIQUE_NEWSOL(x) void x (TCLIQUE_DATA* tcliquedata, int* cliquenodes, int ncliquenodes, \ TCLIQUE_WEIGHT cliqueweight, TCLIQUE_WEIGHT* minweight, TCLIQUE_Bool* acceptsol, TCLIQUE_Bool* stopsolving) /** user callback method to get number of nodes in the graph * input: * - tcliquegraph : user defined graph data structure given to tcliqueMaxClique() * returns: * number of nodes in the graph */ #define TCLIQUE_GETNNODES(x) int x (TCLIQUE_GRAPH* tcliquegraph) /** user callback method to get weights of nodes in the graph * input: * - tcliquegraph : user defined graph data structure given to tcliqueMaxClique() * returns: * array of node weights (of length at least equal to the number of nodes in the graph) */ #define TCLIQUE_GETWEIGHTS(x) const TCLIQUE_WEIGHT* x (TCLIQUE_GRAPH* tcliquegraph) /** user callback method to return whether the edge (node1, node2) is in the graph * input: * - tcliquegraph : user defined graph data structure given to tcliqueMaxClique() * - node1 : start node of edge (tail) * - node2 : end node of edge (head) * returns: * TRUE if edge is in the graph, FALSE otherwise */ #define TCLIQUE_ISEDGE(x) TCLIQUE_Bool x (TCLIQUE_GRAPH* tcliquegraph, int node1, int node2) /** user callback method to select all nodes from a given set of nodes which are adjacent to a given node * input: * - tcliquegraph : user defined graph data structure given to tcliqueMaxClique() * - node : node to select adjacent nodes from * - nodes : array of nodes to select nodes from * - nnodes : number of nodes in 'nodes' array * - adjnodes : pointer to memory to store the resulting nodes * 'adjnodes' and 'nodes' may point to the same memory location * output: * - adjnodes : array of nodes that are contained in 'nodes' and that are adjacent to 'node' * returns: * number of nodes in 'adjnodes' */ #define TCLIQUE_SELECTADJNODES(x) int x (TCLIQUE_GRAPH* tcliquegraph, int node, int* nodes, int nnodes, int* adjnodes) /* * Default Graph Implementation: Interface Methods used by the TClique algorithm */ /** gets number of nodes in the graph */ SCIP_EXPORT TCLIQUE_GETNNODES(tcliqueGetNNodes); /** gets weight of nodes in the graph */ SCIP_EXPORT TCLIQUE_GETWEIGHTS(tcliqueGetWeights); /** returns, whether the edge (node1, node2) is in the graph */ SCIP_EXPORT TCLIQUE_ISEDGE(tcliqueIsEdge); /** selects all nodes from a given set of nodes which are adjacent to a given node * and returns the number of selected nodes */ SCIP_EXPORT TCLIQUE_SELECTADJNODES(tcliqueSelectAdjnodes); /* * Default Graph Implementation: External Interface Methods to access the graph */ /** creates graph data structure */ SCIP_EXPORT TCLIQUE_Bool tcliqueCreate( TCLIQUE_GRAPH** tcliquegraph /**< pointer to store graph data structure */ ); /** frees graph data structure */ SCIP_EXPORT void tcliqueFree( TCLIQUE_GRAPH** tcliquegraph /**< pointer to graph data structure */ ); /** adds nodes up to the given node number to graph data structure (intermediate nodes have weight 0) */ SCIP_EXPORT TCLIQUE_Bool tcliqueAddNode( TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */ int node, /**< node number to add */ TCLIQUE_WEIGHT weight /**< weight of node to add */ ); /** changes weight of node in graph data structure */ SCIP_EXPORT void tcliqueChangeWeight( TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */ int node, /**< node to set new weight */ TCLIQUE_WEIGHT weight /**< new weight of node (allready scaled) */ ); /** adds edge (node1, node2) to graph data structure (node1 and node2 have to be contained in * graph data structure) * * New edges are cached, s.t. the graph data structures are not correct until a call to tcliqueFlush(); * you have to make sure, that no double edges are inserted. */ SCIP_EXPORT TCLIQUE_Bool tcliqueAddEdge( TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */ int node1, /**< start node of edge to add */ int node2 /**< end node of edge to add */ ); /** inserts all cached edges into the data structures */ SCIP_EXPORT TCLIQUE_Bool tcliqueFlush( TCLIQUE_GRAPH* tcliquegraph /**< graph data structure */ ); /** loads graph data structure from file */ SCIP_EXPORT TCLIQUE_Bool tcliqueLoadFile( TCLIQUE_GRAPH** tcliquegraph, /**< pointer to store graph data structure */ const char* filename, /**< name of file with graph data */ double scaleval, /**< value to scale weights (only integral part of scaled weights is considered) */ char* probname, /**< buffer to store the name of the problem */ int sizeofprobname /**< size of buffer to store the name of the problem */ ); /** saves graph data structure to file */ SCIP_EXPORT TCLIQUE_Bool tcliqueSaveFile( TCLIQUE_GRAPH* tcliquegraph, /**< graph data structure */ const char* filename, /**< name of file to create */ double scaleval, /**< value to unscale weights with */ const char* probname /**< name of the problem */ ); /** gets number of edges in the graph */ SCIP_EXPORT int tcliqueGetNEdges( TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */ ); /** gets degree of nodes in graph */ SCIP_EXPORT int* tcliqueGetDegrees( TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */ ); /** gets adjacent nodes of edges in graph */ SCIP_EXPORT int* tcliqueGetAdjnodes( TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */ ); /** gets pointer to first adjacent edge of given node in graph */ SCIP_EXPORT int* tcliqueGetFirstAdjedge( TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */ int node /**< given node */ ); /** gets pointer to last adjacent edge of given node in graph */ SCIP_EXPORT int* tcliqueGetLastAdjedge( TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */ int node /**< given node */ ); /** prints graph data structure */ SCIP_EXPORT void tcliquePrintGraph( TCLIQUE_GRAPH* tcliquegraph /**< pointer to graph data structure */ ); /* * Interface Methods */ /** finds maximum weight clique */ SCIP_EXPORT void tcliqueMaxClique( TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */ TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */ TCLIQUE_ISEDGE((*isedge)), /**< user function to check for existence of an edge */ TCLIQUE_SELECTADJNODES((*selectadjnodes)), /**< user function to select adjacent edges */ TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure that is passed to graph callbacks */ TCLIQUE_NEWSOL((*newsol)), /**< user function to call on every new solution */ TCLIQUE_DATA* tcliquedata, /**< user data to pass to new solution callback function */ int* maxcliquenodes, /**< pointer to store nodes of the maximum weight clique */ int* nmaxcliquenodes, /**< pointer to store number of nodes in the maximum weight clique */ TCLIQUE_WEIGHT* maxcliqueweight, /**< pointer to store weight of the maximum weight clique */ TCLIQUE_WEIGHT maxfirstnodeweight, /**< maximum weight of branching nodes in level 0; 0 if not used * for cliques with at least one fractional node) */ TCLIQUE_WEIGHT minweight, /**< lower bound for weight of generated cliques */ int maxntreenodes, /**< maximal number of nodes of b&b tree */ int backtrackfreq, /**< frequency to backtrack to first level of tree (0: no premature backtracking) */ int maxnzeroextensions, /**< maximal number of zero-valued variables extending the clique */ int fixednode, /**< node that is forced to be in the clique, or -1; must have positive weight */ int* ntreenodes, /**< pointer to store the number of used tree nodes (or NULL) */ TCLIQUE_STATUS* status /**< pointer to store the status of the solving call */ ); #ifdef __cplusplus } #endif #endif