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.

typedef enum TCLIQUE_Status TCLIQUE_STATUS

Definition at line 57 of file tclique.h.

Enumeration Type Documentation

enum TCLIQUE_Status

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

tcliquegraph

pointer 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

tcliquegraph

pointer 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

tcliquegraph	graph data structure
node	node number to add
weight	weight 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

tcliquegraph	graph data structure
node	node to set new weight
weight	new 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

tcliquegraph	graph data structure
node1	start node of edge to add
node2	end 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

tcliquegraph

graph 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

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

tcliquegraph	graph data structure
filename	name of file to create
scaleval	value to unscale weights with
probname	name 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

tcliquegraph

pointer 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

tcliquegraph

pointer 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

tcliquegraph

pointer 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

tcliquegraph	pointer to graph data structure
node	given 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

tcliquegraph	pointer to graph data structure
node	given 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

tcliquegraph

pointer 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

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 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().