Detailed Description
tclique user interface
Definition in file tclique.h.
#include "tclique/tclique_def.h"
Go to the source code of this file.
Macros | |
#define | TCLIQUE_Bool unsigned int |
#define | TRUE 1 |
#define | FALSE 0 |
#define | TCLIQUE_NEWSOL(x) |
#define | TCLIQUE_GETNNODES(x) int x (TCLIQUE_GRAPH* tcliquegraph) |
#define | TCLIQUE_GETWEIGHTS(x) const TCLIQUE_WEIGHT* x (TCLIQUE_GRAPH* tcliquegraph) |
#define | TCLIQUE_ISEDGE(x) TCLIQUE_Bool x (TCLIQUE_GRAPH* tcliquegraph, int node1, int node2) |
#define | TCLIQUE_SELECTADJNODES(x) int x (TCLIQUE_GRAPH* tcliquegraph, int node, int* nodes, int nnodes, int* adjnodes) |
Typedefs | |
typedef int | TCLIQUE_WEIGHT |
typedef struct TCLIQUE_Graph | TCLIQUE_GRAPH |
typedef struct TCLIQUE_Data | TCLIQUE_DATA |
typedef enum TCLIQUE_Status | TCLIQUE_STATUS |
Enumerations | |
enum | TCLIQUE_Status { TCLIQUE_ERROR = 0, TCLIQUE_NODELIMIT = 1, TCLIQUE_USERABORT = 2, TCLIQUE_OPTIMAL = 3 } |
Functions | |
TCLIQUE_GETNNODES (tcliqueGetNNodes) | |
TCLIQUE_GETWEIGHTS (tcliqueGetWeights) | |
TCLIQUE_ISEDGE (tcliqueIsEdge) | |
TCLIQUE_SELECTADJNODES (tcliqueSelectAdjnodes) | |
TCLIQUE_Bool | tcliqueCreate (TCLIQUE_GRAPH **tcliquegraph) |
void | tcliqueFree (TCLIQUE_GRAPH **tcliquegraph) |
TCLIQUE_Bool | tcliqueAddNode (TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight) |
void | tcliqueChangeWeight (TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight) |
TCLIQUE_Bool | tcliqueAddEdge (TCLIQUE_GRAPH *tcliquegraph, int node1, int node2) |
TCLIQUE_Bool | tcliqueFlush (TCLIQUE_GRAPH *tcliquegraph) |
TCLIQUE_Bool | tcliqueLoadFile (TCLIQUE_GRAPH **tcliquegraph, const char *filename, double scaleval, char *probname, int sizeofprobname) |
TCLIQUE_Bool | tcliqueSaveFile (TCLIQUE_GRAPH *tcliquegraph, const char *filename, double scaleval, const char *probname) |
int | tcliqueGetNEdges (TCLIQUE_GRAPH *tcliquegraph) |
int * | tcliqueGetDegrees (TCLIQUE_GRAPH *tcliquegraph) |
int * | tcliqueGetAdjnodes (TCLIQUE_GRAPH *tcliquegraph) |
int * | tcliqueGetFirstAdjedge (TCLIQUE_GRAPH *tcliquegraph, int node) |
int * | tcliqueGetLastAdjedge (TCLIQUE_GRAPH *tcliquegraph, int node) |
void | tcliquePrintGraph (TCLIQUE_GRAPH *tcliquegraph) |
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) |
Macro Definition Documentation
◆ TCLIQUE_Bool
#define TCLIQUE_Bool unsigned int |
type used for boolean values
Definition at line 53 of file tclique.h.
Referenced by branch(), compSubcliques(), newSolution(), tcliqueColoring(), and tcliqueMaxClique().
◆ TRUE
◆ FALSE
◆ TCLIQUE_NEWSOL
#define TCLIQUE_NEWSOL | ( | x | ) |
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
◆ TCLIQUE_GETNNODES
#define TCLIQUE_GETNNODES | ( | x | ) | int x (TCLIQUE_GRAPH* tcliquegraph) |
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
◆ TCLIQUE_GETWEIGHTS
#define TCLIQUE_GETWEIGHTS | ( | x | ) | const TCLIQUE_WEIGHT* 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)
◆ TCLIQUE_ISEDGE
#define TCLIQUE_ISEDGE | ( | x | ) | TCLIQUE_Bool x (TCLIQUE_GRAPH* tcliquegraph, int node1, int node2) |
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
◆ TCLIQUE_SELECTADJNODES
#define TCLIQUE_SELECTADJNODES | ( | x | ) | int x (TCLIQUE_GRAPH* tcliquegraph, int node, int* nodes, int nnodes, int* adjnodes) |
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'
Typedef Documentation
◆ TCLIQUE_WEIGHT
typedef int TCLIQUE_WEIGHT |
◆ TCLIQUE_GRAPH
typedef struct TCLIQUE_Graph TCLIQUE_GRAPH |
◆ TCLIQUE_DATA
typedef struct TCLIQUE_Data TCLIQUE_DATA |
◆ TCLIQUE_STATUS
typedef enum TCLIQUE_Status TCLIQUE_STATUS |
Enumeration Type Documentation
◆ TCLIQUE_Status
enum TCLIQUE_Status |
Function Documentation
◆ TCLIQUE_GETNNODES()
TCLIQUE_GETNNODES | ( | tcliqueGetNNodes | ) |
◆ TCLIQUE_GETWEIGHTS()
TCLIQUE_GETWEIGHTS | ( | tcliqueGetWeights | ) |
◆ TCLIQUE_ISEDGE()
TCLIQUE_ISEDGE | ( | tcliqueIsEdge | ) |
returns, whether the edge (node1, node2) is in the graph
Definition at line 92 of file tclique_graph.c.
References FALSE, nnodes, NULL, tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and TRUE.
◆ TCLIQUE_SELECTADJNODES()
TCLIQUE_SELECTADJNODES | ( | tcliqueSelectAdjnodes | ) |
selects all nodes from a given set of nodes which are adjacent to a given node and returns the number of selected nodes
Definition at line 135 of file tclique_graph.c.
References nnodes, NULL, tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().
◆ tcliqueCreate()
TCLIQUE_Bool tcliqueCreate | ( | TCLIQUE_GRAPH ** | tcliquegraph | ) |
creates graph data structure
- Parameters
-
tcliquegraph pointer to store graph data structure
Definition at line 185 of file tclique_graph.c.
References ALLOC_FALSE, BMSallocMemory, NULL, and TRUE.
Referenced by createConsStoreGraphAtRoot(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIPcreateProbColoring(), and tcliqueLoadFile().
◆ tcliqueFree()
void tcliqueFree | ( | TCLIQUE_GRAPH ** | tcliquegraph | ) |
frees graph data structure
- Parameters
-
tcliquegraph pointer to graph data structure
Definition at line 211 of file tclique_graph.c.
References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, and NULL.
Referenced by doSeachEcAggr(), preprocessGraph(), SCIP_DECL_CONSDELETE(), SCIP_DECL_PROBDELORIG(), and SCIP_DECL_PROBDELTRANS().
◆ tcliqueAddNode()
TCLIQUE_Bool tcliqueAddNode | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node, | ||
TCLIQUE_WEIGHT | weight | ||
) |
adds nodes up to the given node number to graph data structure (intermediate nodes have weight 0)
- Parameters
-
tcliquegraph graph data structure node node number to add weight weight of node to add
Definition at line 340 of file tclique_graph.c.
References FALSE, MAX, tcliqueEnsureSizeNodes(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
◆ tcliqueChangeWeight()
void tcliqueChangeWeight | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node, | ||
TCLIQUE_WEIGHT | weight | ||
) |
changes weight of node in graph data structure
- Parameters
-
tcliquegraph graph data structure node node to set new weight weight new weight of node (allready scaled)
Definition at line 362 of file tclique_graph.c.
Referenced by preprocessGraph(), SCIP_DECL_PRICERREDCOST(), searchEcAggrWithCliques(), and updateWeightsTCliquegraph().
◆ tcliqueAddEdge()
TCLIQUE_Bool tcliqueAddEdge | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node1, | ||
int | node2 | ||
) |
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.
- Parameters
-
tcliquegraph graph data structure node1 start node of edge to add node2 end node of edge to add
Definition at line 380 of file tclique_graph.c.
References ALLOC_FALSE, BMSallocMemoryArray, BMSclearMemoryArray, FALSE, nnodes, NULL, tcliqueEnsureSizeCachedEdges(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
◆ tcliqueFlush()
TCLIQUE_Bool tcliqueFlush | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
inserts all cached edges into the data structures
- Parameters
-
tcliquegraph graph data structure
Definition at line 417 of file tclique_graph.c.
References BMSfreeMemoryArray, FALSE, nnodes, NULL, tcliqueEnsureSizeEdges(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
◆ tcliqueLoadFile()
TCLIQUE_Bool tcliqueLoadFile | ( | TCLIQUE_GRAPH ** | tcliquegraph, |
const char * | filename, | ||
double | scaleval, | ||
char * | probname, | ||
int | sizeofprobname | ||
) |
loads graph data structure from file
- Parameters
-
tcliquegraph pointer to store graph data structure filename name of file with graph data scaleval value to scale weights (only integral part of scaled weights is considered) probname buffer to store the name of the problem sizeofprobname size of buffer to store the name of the problem
Definition at line 552 of file tclique_graph.c.
References BMSallocMemoryArray, FALSE, infoMessage, NULL, tcliqueCreate(), and TRUE.
◆ tcliqueSaveFile()
TCLIQUE_Bool tcliqueSaveFile | ( | TCLIQUE_GRAPH * | tcliquegraph, |
const char * | filename, | ||
double | scaleval, | ||
const char * | probname | ||
) |
saves graph data structure to file
- Parameters
-
tcliquegraph graph data structure filename name of file to create scaleval value to unscale weights with probname name of the problem
Definition at line 728 of file tclique_graph.c.
References FALSE, infoMessage, NULL, and TRUE.
◆ tcliqueGetNEdges()
int tcliqueGetNEdges | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets number of edges in the graph
- Parameters
-
tcliquegraph pointer to graph data structure
Definition at line 772 of file tclique_graph.c.
References NULL.
Referenced by tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().
◆ tcliqueGetDegrees()
int* tcliqueGetDegrees | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets degree of nodes in graph
- Parameters
-
tcliquegraph pointer to graph data structure
Definition at line 782 of file tclique_graph.c.
References NULL.
Referenced by greedyStableSet(), preprocessGraph(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().
◆ tcliqueGetAdjnodes()
int* tcliqueGetAdjnodes | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets adjacent nodes of edges in graph
- Parameters
-
tcliquegraph pointer to graph data structure
Definition at line 793 of file tclique_graph.c.
References NULL.
Referenced by tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().
◆ tcliqueGetFirstAdjedge()
int* tcliqueGetFirstAdjedge | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node | ||
) |
gets pointer to first adjacent edge of given node in graph
- Parameters
-
tcliquegraph pointer to graph data structure node given node
Definition at line 804 of file tclique_graph.c.
References nnodes, NULL, tcliqueGetAdjnodes(), and tcliqueGetNEdges().
Referenced by COLORprobGetComplementaryGraph(), getNViolatedEdges(), preprocessGraph(), runTabuCol(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIP_DECL_READERWRITE(), TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().
◆ tcliqueGetLastAdjedge()
int* tcliqueGetLastAdjedge | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node | ||
) |
gets pointer to last adjacent edge of given node in graph
- Parameters
-
tcliquegraph pointer to graph data structure node given node
Definition at line 828 of file tclique_graph.c.
References nnodes, NULL, tcliqueGetAdjnodes(), tcliqueGetDegrees(), and tcliqueGetNEdges().
Referenced by COLORprobGetComplementaryGraph(), getNViolatedEdges(), preprocessGraph(), runTabuCol(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIP_DECL_READERWRITE(), TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().
◆ tcliquePrintGraph()
void tcliquePrintGraph | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
prints graph data structure
- Parameters
-
tcliquegraph pointer to graph data structure
Definition at line 860 of file tclique_graph.c.
References infoMessage, NULL, tcliqueGetDegrees(), tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliqueGetNEdges().
◆ tcliqueMaxClique()
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 | ||
) |
finds maximum weight clique
- Parameters
-
tcliquegraph pointer to graph data structure that is passed to graph callbacks tcliquedata user data to pass to new solution callback function maxcliquenodes pointer to store nodes of the maximum weight clique nmaxcliquenodes pointer to store number of nodes in the maximum weight clique maxcliqueweight pointer to store weight of the maximum weight clique maxfirstnodeweight maximum weight of branching nodes in level 0; 0 if not used for cliques with at least one fractional node) minweight lower bound for weight of generated cliques maxntreenodes maximal number of nodes of b&b tree backtrackfreq frequency to backtrack to first level of tree (0: no premature backtracking) maxnzeroextensions maximal number of zero-valued variables extending the clique fixednode node that is forced to be in the clique, or -1; must have positive weight ntreenodes pointer to store the number of used tree nodes (or NULL) status pointer to store the status of the solving call
Definition at line 1010 of file tclique_branch.c.
References ALLOC_ABORT, BMSallocMemoryArray, BMScreateChunkMemory, BMSdestroyChunkMemory, BMSfreeMemoryArray, branch(), CHUNK_SIZE, CLIQUEHASH_INITSIZE, createCliquehash(), debugMessage, freeCliquehash(), nnodes, NULL, TCLIQUE_Bool, TCLIQUE_OPTIMAL, and TCLIQUE_USERABORT.
Referenced by computeMinDistance(), findCumulativeConss(), preprocessGraph(), SCIP_DECL_PRICERREDCOST(), searchEcAggrWithCliques(), sepaBoundInequalitiesFromGraph(), and separateCuts().