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) |
#define | TCLIQUE_GETWEIGHTS(x) |
#define | TCLIQUE_ISEDGE(x) |
#define | TCLIQUE_SELECTADJNODES(x) |
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) |
#define TCLIQUE_Bool unsigned int |
type used for boolean values
Definition at line 53 of file tclique.h.
Referenced by boundSubgraph(), branch(), compSubcliques(), getMaxSatdegIndex(), inCliquehash(), newSolution(), tcliqueAddEdge(), tcliqueAddNode(), tcliqueColoring(), tcliqueCreate(), tcliqueEnsureSizeCachedEdges(), tcliqueEnsureSizeEdges(), tcliqueEnsureSizeNodes(), tcliqueFlush(), tcliqueLoadFile(), tcliqueMaxClique(), and tcliqueSaveFile().
#define TCLIQUE_NEWSOL | ( | x | ) |
user callback method which is called whenever a feasible clique was found input:
#define TCLIQUE_GETNNODES | ( | x | ) |
user callback method to get number of nodes in the graph input:
#define TCLIQUE_GETWEIGHTS | ( | x | ) |
user callback method to get weights of nodes in the graph input:
#define TCLIQUE_ISEDGE | ( | x | ) |
user callback method to return whether the edge (node1, node2) is in the graph input:
#define TCLIQUE_SELECTADJNODES | ( | x | ) |
user callback method to select all nodes from a given set of nodes which are adjacent to a given node input:
typedef int TCLIQUE_WEIGHT |
typedef struct TCLIQUE_Graph TCLIQUE_GRAPH |
typedef struct TCLIQUE_Data TCLIQUE_DATA |
typedef enum TCLIQUE_Status TCLIQUE_STATUS |
enum TCLIQUE_Status |
TCLIQUE_GETNNODES | ( | tcliqueGetNNodes | ) |
gets number of nodes in the graph
Definition at line 76 of file tclique_graph.c.
TCLIQUE_GETWEIGHTS | ( | tcliqueGetWeights | ) |
gets weight of nodes in the graph
Definition at line 84 of file tclique_graph.c.
TCLIQUE_ISEDGE | ( | tcliqueIsEdge | ) |
returns, whether the edge (node1, node2) is in the graph
Definition at line 92 of file tclique_graph.c.
References assert(), FALSE, nnodes, NULL, tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and TRUE.
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 assert(), i, nnodes, NULL, tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().
TCLIQUE_Bool tcliqueCreate | ( | TCLIQUE_GRAPH ** | tcliquegraph | ) |
creates graph data structure
tcliquegraph | pointer to store graph data structure |
Definition at line 185 of file tclique_graph.c.
References ALLOC_FALSE, assert(), BMSallocMemory, NULL, TCLIQUE_Bool, and TRUE.
Referenced by createConsStoreGraphAtRoot(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIPcreateProbColoring(), and tcliqueLoadFile().
void tcliqueFree | ( | TCLIQUE_GRAPH ** | tcliquegraph | ) |
frees graph data structure
tcliquegraph | pointer to graph data structure |
Definition at line 211 of file tclique_graph.c.
References assert(), BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, and NULL.
Referenced by doSeachEcAggr(), preprocessGraph(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSEXITSOL(), SCIP_DECL_PROBDELORIG(), and SCIP_DECL_PROBDELTRANS().
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)
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 assert(), FALSE, MAX, TCLIQUE_Bool, tcliqueEnsureSizeNodes(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
void tcliqueChangeWeight | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node, | ||
TCLIQUE_WEIGHT | weight ) |
changes weight of node in graph data structure
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.
References assert().
Referenced by preprocessGraph(), SCIP_DECL_PRICERREDCOST(), searchEcAggrWithCliques(), and updateWeightsTCliquegraph().
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.
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, assert(), BMSallocMemoryArray, BMSclearMemoryArray, FALSE, nnodes, NULL, TCLIQUE_Bool, tcliqueEnsureSizeCachedEdges(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
TCLIQUE_Bool tcliqueFlush | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
inserts all cached edges into the data structures
tcliquegraph | graph data structure |
Definition at line 417 of file tclique_graph.c.
References assert(), BMSfreeMemoryArray, FALSE, i, nnodes, NULL, TCLIQUE_Bool, tcliqueEnsureSizeEdges(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
TCLIQUE_Bool tcliqueLoadFile | ( | TCLIQUE_GRAPH ** | tcliquegraph, |
const char * | filename, | ||
double | scaleval, | ||
char * | probname, | ||
int | sizeofprobname ) |
loads graph data structure from file
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 assert(), BMSallocMemoryArray, FALSE, i, infoMessage, NULL, result, TCLIQUE_Bool, tcliqueCreate(), and TRUE.
TCLIQUE_Bool tcliqueSaveFile | ( | TCLIQUE_GRAPH * | tcliquegraph, |
const char * | filename, | ||
double | scaleval, | ||
const char * | probname ) |
saves graph data structure to file
tcliquegraph | graph data structure |
filename | name of file to create |
scaleval | value to unscale weights with |
probname | name of the problem |
Definition at line 729 of file tclique_graph.c.
References assert(), FALSE, i, infoMessage, NULL, TCLIQUE_Bool, and TRUE.
int tcliqueGetNEdges | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets number of edges in the graph
tcliquegraph | pointer to graph data structure |
Definition at line 773 of file tclique_graph.c.
References assert(), and NULL.
Referenced by tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().
int * tcliqueGetDegrees | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets degree of nodes in graph
tcliquegraph | pointer to graph data structure |
Definition at line 783 of file tclique_graph.c.
References assert(), and NULL.
Referenced by greedyStableSet(), greedyStableSet(), preprocessGraph(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().
int * tcliqueGetAdjnodes | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets adjacent nodes of edges in graph
tcliquegraph | pointer to graph data structure |
Definition at line 794 of file tclique_graph.c.
References assert(), and NULL.
Referenced by tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().
int * tcliqueGetFirstAdjedge | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node ) |
gets pointer to first adjacent edge of given node in graph
tcliquegraph | pointer to graph data structure |
node | given node |
Definition at line 805 of file tclique_graph.c.
References assert(), 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().
int * tcliqueGetLastAdjedge | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node ) |
gets pointer to last adjacent edge of given node in graph
tcliquegraph | pointer to graph data structure |
node | given node |
Definition at line 829 of file tclique_graph.c.
References assert(), 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().
void tcliquePrintGraph | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
prints graph data structure
tcliquegraph | pointer to graph data structure |
Definition at line 861 of file tclique_graph.c.
References assert(), i, infoMessage, NULL, tcliqueGetDegrees(), tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliqueGetNEdges().
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
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, assert(), BMSallocMemoryArray, BMScreateChunkMemory, BMSdestroyChunkMemory, BMSfreeMemoryArray, branch(), CHUNK_SIZE, CLIQUEHASH_INITSIZE, createCliquehash(), debugMessage, freeCliquehash(), i, nnodes, NULL, TCLIQUE_Bool, TCLIQUE_OPTIMAL, and TCLIQUE_USERABORT.
Referenced by computeMinDistance(), findCumulativeConss(), preprocessGraph(), SCIP_DECL_PRICERREDCOST(), searchEcAggrWithCliques(), sepaBoundInequalitiesFromGraph(), and separateCuts().