Scippy

SCIP

Solving Constraint Integer Programs

tclique.h File Reference

Detailed Description

tclique user interface

Author
Tobias Achterberg
Ralf Borndoerfer
Zoltan Kormos
Kati Wolter

Definition in file tclique.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

#define TCLIQUE_Bool   unsigned int

type used for boolean values

Definition at line 42 of file tclique.h.

Referenced by branch(), compSubcliques(), newSolution(), tcliqueColoring(), and tcliqueMaxClique().

#define TRUE   1

boolean value TRUE

Definition at line 45 of file tclique.h.

#define FALSE   0

boolean value FALSE

Definition at line 46 of file tclique.h.

#define TCLIQUE_NEWSOL (   x)
Value:
void x (TCLIQUE_DATA* tcliquedata, int* cliquenodes, int ncliquenodes, \
TCLIQUE_WEIGHT cliqueweight, TCLIQUE_WEIGHT* minweight, TCLIQUE_Bool* acceptsol, TCLIQUE_Bool* stopsolving)

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

Definition at line 77 of file tclique.h.

#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

Definition at line 86 of file tclique.h.

#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)

Definition at line 94 of file tclique.h.

#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

Definition at line 104 of file tclique.h.

#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'

Definition at line 119 of file tclique.h.

Typedef Documentation

typedef int TCLIQUE_WEIGHT

type used for node weights in the graph

Definition at line 37 of file tclique.h.

typedef struct TCLIQUE_Graph TCLIQUE_GRAPH

user defined structure for storing the graph, passed to graph callbacks

Definition at line 38 of file tclique.h.

typedef struct TCLIQUE_Data TCLIQUE_DATA

user defined data to pass to new solution callback method

Definition at line 39 of file tclique.h.

Definition at line 57 of file tclique.h.

Enumeration Type Documentation

return status of the TCLIQUE algorithm

Enumerator:
TCLIQUE_ERROR 

an error occurred

TCLIQUE_NODELIMIT 

the node limit was reached

TCLIQUE_USERABORT 

the user call back function aborted the solving process

TCLIQUE_OPTIMAL 

the optimal solution was found

Definition at line 50 of file tclique.h.

Function Documentation

TCLIQUE_GETNNODES ( tcliqueGetNNodes  )

gets number of nodes in the graph

Definition at line 65 of file tclique_graph.c.

References NULL.

TCLIQUE_GETWEIGHTS ( tcliqueGetWeights  )

gets weight of nodes in the graph

Definition at line 73 of file tclique_graph.c.

References NULL.

TCLIQUE_ISEDGE ( tcliqueIsEdge  )

returns, whether the edge (node1, node2) is in the graph

Definition at line 81 of file tclique_graph.c.

References FALSE, NULL, tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and TRUE.

TCLIQUE_SELECTADJNODES ( tcliqueSelectAdjnodes  )

Definition at line 125 of file tclique_graph.c.

References NULL, tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

TCLIQUE_Bool tcliqueCreate ( TCLIQUE_GRAPH **  tcliquegraph)

creates graph data structure

Parameters
tcliquegraphpointer to store graph data structure

Definition at line 175 of file tclique_graph.c.

References ALLOC_FALSE, BMSallocMemory, NULL, and TRUE.

Referenced by tcliqueLoadFile().

void tcliqueFree ( TCLIQUE_GRAPH **  tcliquegraph)

frees graph data structure

Parameters
tcliquegraphpointer to graph data structure

Definition at line 201 of file tclique_graph.c.

References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, and NULL.

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
tcliquegraphgraph data structure
nodenode number to add
weightweight of node to add

Definition at line 330 of file tclique_graph.c.

References FALSE, MAX, tcliqueEnsureSizeNodes(), and TRUE.

void tcliqueChangeWeight ( TCLIQUE_GRAPH tcliquegraph,
int  node,
TCLIQUE_WEIGHT  weight 
)

changes weight of node in graph data structure

Parameters
tcliquegraphgraph data structure
nodenode to set new weight
weightnew weight of node (allready scaled)

Definition at line 352 of file tclique_graph.c.

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
tcliquegraphgraph data structure
node1start node of edge to add
node2end node of edge to add

Definition at line 369 of file tclique_graph.c.

References ALLOC_FALSE, BMSallocMemoryArray, BMSclearMemoryArray, FALSE, NULL, tcliqueEnsureSizeCachedEdges(), and TRUE.

TCLIQUE_Bool tcliqueFlush ( TCLIQUE_GRAPH tcliquegraph)

inserts all cached edges into the data structures

Parameters
tcliquegraphgraph data structure

Definition at line 406 of file tclique_graph.c.

References BMSfreeMemoryArray, FALSE, NULL, tcliqueEnsureSizeEdges(), and TRUE.

TCLIQUE_Bool tcliqueLoadFile ( TCLIQUE_GRAPH **  tcliquegraph,
const char *  filename,
double  scaleval,
char *  probname,
int  sizeofprobname 
)

loads graph data structure from file

Parameters
tcliquegraphpointer to store graph data structure
filenamename of file with graph data
scalevalvalue to scale weights (only integral part of scaled weights is considered)
probnamebuffer to store the name of the problem
sizeofprobnamesize of buffer to store the name of the problem

Definition at line 541 of file tclique_graph.c.

References BMSallocMemoryArray, BMScopyMemoryArray, BMSfreeMemoryArray, FALSE, infoMessage, NULL, tcliqueCreate(), and TRUE.

TCLIQUE_Bool tcliqueSaveFile ( TCLIQUE_GRAPH tcliquegraph,
const char *  filename,
double  scaleval,
const char *  probname 
)

saves graph data structure to file

Parameters
tcliquegraphgraph data structure
filenamename of file to create
scalevalvalue to unscale weights with
probnamename of the problem

Definition at line 719 of file tclique_graph.c.

References FALSE, infoMessage, NULL, and TRUE.

int tcliqueGetNEdges ( TCLIQUE_GRAPH tcliquegraph)

gets number of edges in the graph

Parameters
tcliquegraphpointer to graph data structure

Definition at line 763 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().

int* tcliqueGetDegrees ( TCLIQUE_GRAPH tcliquegraph)

gets degree of nodes in graph

Parameters
tcliquegraphpointer to graph data structure

Definition at line 773 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetLastAdjedge(), and tcliquePrintGraph().

int* tcliqueGetAdjnodes ( TCLIQUE_GRAPH tcliquegraph)

gets adjacent nodes of edges in graph

Parameters
tcliquegraphpointer to graph data structure

Definition at line 784 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

int* tcliqueGetFirstAdjedge ( TCLIQUE_GRAPH tcliquegraph,
int  node 
)

gets pointer to first adjacent edge of given node in graph

Parameters
tcliquegraphpointer to graph data structure
nodegiven node

Definition at line 795 of file tclique_graph.c.

References NULL, tcliqueGetAdjnodes(), and tcliqueGetNEdges().

Referenced by TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().

int* tcliqueGetLastAdjedge ( TCLIQUE_GRAPH tcliquegraph,
int  node 
)

gets pointer to last adjacent edge of given node in graph

Parameters
tcliquegraphpointer to graph data structure
nodegiven node

Definition at line 819 of file tclique_graph.c.

References NULL, tcliqueGetAdjnodes(), tcliqueGetDegrees(), and tcliqueGetNEdges().

Referenced by TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().

void tcliquePrintGraph ( TCLIQUE_GRAPH tcliquegraph)
Parameters
tcliquegraphpointer to graph data structure

Definition at line 851 of file tclique_graph.c.

References 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

Parameters
tcliquegraphpointer to graph data structure that is passed to graph callbacks
tcliquedatauser data to pass to new solution callback function
maxcliquenodespointer to store nodes of the maximum weight clique
nmaxcliquenodespointer to store number of nodes in the maximum weight clique
maxcliqueweightpointer to store weight of the maximum weight clique
maxfirstnodeweightmaximum weight of branching nodes in level 0; 0 if not used for cliques with at least one fractional node)
minweightlower bound for weight of generated cliques
maxntreenodesmaximal number of nodes of b&b tree
backtrackfreqfrequency to backtrack to first level of tree (0: no premature backtracking)
maxnzeroextensionsmaximal number of zero-valued variables extending the clique
fixednodenode that is forced to be in the clique, or -1; must have positive weight
ntreenodespointer to store the number of used tree nodes (or NULL)
statuspointer to store the status of the solving call

Definition at line 998 of file tclique_branch.c.

References ALLOC_ABORT, BMSallocMemoryArray, BMScreateChunkMemory, BMSdestroyChunkMemory, BMSfreeMemoryArray, branch(), CHUNK_SIZE, CLIQUEHASH_INITSIZE, createCliquehash(), debugMessage, freeCliquehash(), NULL, TCLIQUE_Bool, TCLIQUE_OPTIMAL, and TCLIQUE_USERABORT.

Referenced by computeMinDistance(), findCumulativeConss(), and separateCuts().