Detailed Description
branch and bound part of algorithm for maximum cliques
Definition in file tclique_branch.c.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <limits.h>
#include "tclique/tclique.h"
#include "tclique/tclique_def.h"
#include "tclique/tclique_coloring.h"
#include "blockmemshell/memory.h"
Go to the source code of this file.
Macros | |
#define | CHUNK_SIZE (64) |
#define | CLIQUEHASH_INITSIZE (1024) |
Typedefs | |
typedef struct clique | CLIQUE |
typedef struct cliquehash | CLIQUEHASH |
Functions | |
static void | createClique (CLIQUE **clique, int *nodes, int nnodes) |
static void | freeClique (CLIQUE **clique) |
static int | compSubcliques (CLIQUE *clique1, CLIQUE *clique2) |
static void | checkCliquehash (CLIQUEHASH *cliquehash) |
static void | createCliquehash (CLIQUEHASH **cliquehash, int tablesize) |
static void | clearCliquehash (CLIQUEHASH *cliquehash) |
static void | freeCliquehash (CLIQUEHASH **cliquehash) |
static void | ensureCliquehashSize (CLIQUEHASH *cliquehash, int num) |
static TCLIQUE_Bool | inCliquehash (CLIQUEHASH *cliquehash, CLIQUE *clique, int *insertpos) |
static void | insertClique (CLIQUEHASH *cliquehash, CLIQUE *clique, int insertpos) |
static void | extendCliqueZeroWeight (TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int *ncurcliquenodes) |
static void | newSolution (TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, CLIQUEHASH *cliquehash, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int ncurcliquenodes, TCLIQUE_WEIGHT curcliqueweight, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_Bool *stopsolving) |
static void | reduced (TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_GRAPH *tcliquegraph, int *V, int nV, TCLIQUE_WEIGHT *apbound, int *tmpcliquenodes, int *ntmpcliquenodes, TCLIQUE_WEIGHT *tmpcliqueweight) |
static TCLIQUE_WEIGHT | boundSubgraph (TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, BMS_CHKMEM *mem, int *buffer, int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, TCLIQUE_WEIGHT *apbound, int *tmpcliquenodes, int *ntmpcliquenodes, TCLIQUE_WEIGHT *tmpcliqueweight) |
static int | getMaxApBoundIndex (int nV, TCLIQUE_WEIGHT *apbound) |
static int | getMaxApBoundIndexNotMaxWeight (int *V, int nV, const TCLIQUE_WEIGHT *apbound, const TCLIQUE_WEIGHT *weights, TCLIQUE_WEIGHT maxweight) |
static int | branch (TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, BMS_CHKMEM *mem, CLIQUEHASH *cliquehash, int *buffer, int level, int *V, int nV, int *Vzero, int nVzero, NBC *gsd, TCLIQUE_Bool *iscolored, int *K, TCLIQUE_WEIGHT weightK, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, int *curcliquenodes, int *ncurcliquenodes, TCLIQUE_WEIGHT *curcliqueweight, int *tmpcliquenodes, TCLIQUE_WEIGHT maxfirstnodeweight, int *ntreenodes, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, TCLIQUE_STATUS *status) |
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
◆ CHUNK_SIZE
#define CHUNK_SIZE (64) |
Definition at line 38 of file tclique_branch.c.
Referenced by tcliqueMaxClique().
◆ CLIQUEHASH_INITSIZE
#define CLIQUEHASH_INITSIZE (1024) |
Definition at line 39 of file tclique_branch.c.
Referenced by tcliqueMaxClique().
Typedef Documentation
◆ CLIQUE
typedef struct clique CLIQUE |
single element of the clique hash table
Definition at line 48 of file tclique_branch.c.
◆ CLIQUEHASH
typedef struct cliquehash CLIQUEHASH |
hash table for storing cliques
Definition at line 57 of file tclique_branch.c.
Function Documentation
◆ createClique()
|
static |
creates a clique
- Parameters
-
clique pointer to the clique nodes nodes of the clique nnodes number of nodes in the clique
Definition at line 70 of file tclique_branch.c.
References ALLOC_ABORT, BMSallocMemory, BMSallocMemoryArray, nnodes, and NULL.
Referenced by newSolution().
◆ freeClique()
|
static |
frees a clique
- Parameters
-
clique pointer to the clique
Definition at line 99 of file tclique_branch.c.
References BMSfreeMemory, BMSfreeMemoryArray, and NULL.
Referenced by clearCliquehash(), and newSolution().
◆ compSubcliques()
checks, whether clique1 is a subset of clique2 and returns the following value: == 0 if clique1 == clique2, or clique1 is contained in clique2, < 0 if clique1 < clique2, and clique1 is not contained in clique2,
0 if clique1 > clique2, and clique1 is not contained in clique2
- Parameters
-
clique1 first clique to compare clique2 second clique to compare
Definition at line 116 of file tclique_branch.c.
References FALSE, nnodes, NULL, TCLIQUE_Bool, and TRUE.
Referenced by checkCliquehash(), and inCliquehash().
◆ checkCliquehash()
|
static |
performs an integrity check of the clique hash table
- Parameters
-
cliquehash clique hash table
Definition at line 166 of file tclique_branch.c.
References compSubcliques(), and NULL.
Referenced by insertClique().
◆ createCliquehash()
|
static |
creates a table for storing cliques
- Parameters
-
cliquehash pointer to store the clique hash table tablesize initial size of the clique hash table
Definition at line 183 of file tclique_branch.c.
References ALLOC_ABORT, BMSallocMemory, BMSallocMemoryArray, and NULL.
Referenced by tcliqueMaxClique().
◆ clearCliquehash()
|
static |
clears the clique hash table and frees all inserted cliques
- Parameters
-
cliquehash clique hash table
Definition at line 199 of file tclique_branch.c.
References freeClique(), and NULL.
Referenced by freeCliquehash(), and newSolution().
◆ freeCliquehash()
|
static |
frees the table for storing cliques and all inserted cliques
- Parameters
-
cliquehash pointer to the clique hash table
Definition at line 216 of file tclique_branch.c.
References BMSfreeMemory, BMSfreeMemoryArray, clearCliquehash(), and NULL.
Referenced by tcliqueMaxClique().
◆ ensureCliquehashSize()
|
static |
ensures, that the clique hash table is able to store at least the given number of cliques
- Parameters
-
cliquehash clique hash table num minimal number of cliques to store
Definition at line 233 of file tclique_branch.c.
References ALLOC_ABORT, BMSreallocMemoryArray, debugMessage, debugPrintf, and NULL.
Referenced by insertClique().
◆ inCliquehash()
|
static |
searches the given clique in the clique hash table and returns whether it (or a stronger clique) exists
- Parameters
-
cliquehash clique hash table clique clique to search in the table insertpos position where the clique should be inserted in the table
Definition at line 280 of file tclique_branch.c.
References compSubcliques(), FALSE, NULL, and TRUE.
Referenced by newSolution().
◆ insertClique()
|
static |
inserts clique into clique hash table
- Parameters
-
cliquehash clique hash table clique clique to search in the table insertpos position to insert clique into table (returned by inCliquehash())
Definition at line 329 of file tclique_branch.c.
References checkCliquehash(), debug, ensureCliquehashSize(), and NULL.
Referenced by newSolution().
◆ extendCliqueZeroWeight()
|
static |
extends given clique by additional zero-weight nodes of the given node set
- Parameters
-
tcliquegraph pointer to graph data structure buffer buffer of size nnodes Vzero zero weighted nodes nVzero number of zero weighted nodes maxnzeroextensions maximal number of zero-valued variables extending the clique curcliquenodes nodes of the clique ncurcliquenodes pointer to store number of nodes in the clique
Definition at line 365 of file tclique_branch.c.
References BMScopyMemoryArray, debugMessage, and NULL.
Referenced by newSolution().
◆ newSolution()
|
static |
calls user callback after a new solution was found, that is better than the current incumbent
The callback decides, whether this solution should be accepted as new incumbent, and whether the solution process should be stopped.
- Parameters
-
tcliquegraph pointer to graph data structure tcliquedata user data to pass to user callback function cliquehash clique hash table buffer buffer of size nnodes Vzero zero weighted nodes nVzero number of zero weighted nodes maxnzeroextensions maximal number of zero-valued variables extending the clique curcliquenodes nodes of the new clique ncurcliquenodes number of nodes in the new clique curcliqueweight weight of the new clique 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 stopsolving pointer to store whether the solving should be stopped
Definition at line 427 of file tclique_branch.c.
References BMScopyMemoryArray, clearCliquehash(), createClique(), debugMessage, debugPrintf, extendCliqueZeroWeight(), FALSE, freeClique(), inCliquehash(), insertClique(), NULL, TCLIQUE_Bool, and TRUE.
Referenced by branch().
◆ reduced()
|
static |
tries to find a clique, if V has only one or two nodes
- Parameters
-
tcliquegraph pointer to graph data structure V non-zero weighted nodes for branching nV number of non-zero weighted nodes for branching apbound apriori bound of nodes for branching tmpcliquenodes buffer for storing the temporary clique ntmpcliquenodes pointer to store number of nodes of the temporary clique tmpcliqueweight pointer to store weight of the temporary clique
Definition at line 533 of file tclique_branch.c.
References NULL.
Referenced by boundSubgraph().
◆ boundSubgraph()
|
static |
calculates upper bound on remaining subgraph, and heuristically generates a clique
- Parameters
-
tcliquegraph pointer to graph data structure mem block memory buffer buffer of size nnodes V non-zero weighted nodes for branching nV number of non-zero weighted nodes for branching gsd neighbour color information of all nodes iscolored coloring status of all nodes apbound apriori bound of nodes for branching tmpcliquenodes buffer for storing the temporary clique ntmpcliquenodes pointer to store number of nodes of the temporary clique tmpcliqueweight pointer to store weight of the temporary clique
Definition at line 601 of file tclique_branch.c.
References NULL, reduced(), and tcliqueColoring().
Referenced by branch().
◆ getMaxApBoundIndex()
|
static |
gets the index of the node of V with the maximum apriori bound; returns -1, if no node exists
- Parameters
-
nV number of nodes of V apbound apriori bound of nodes of V
Definition at line 639 of file tclique_branch.c.
References NULL.
Referenced by branch().
◆ getMaxApBoundIndexNotMaxWeight()
|
static |
gets the index of the node of V with the maximum apriori bound, but ignores nodes with weights larger than the given maximal weight
Returns -1 if no node with weight smaller or equal than maxweight is found.
- Parameters
-
V non-zero weighted nodes for branching nV number of non-zero weighted nodes for branching apbound apriori bound of nodes of V weights weights of nodes maxweight maximal weight of node to be candidate for selection
Definition at line 672 of file tclique_branch.c.
References NULL.
Referenced by branch().
◆ branch()
|
static |
branches the searching tree, branching nodes are selected in decreasing order of their apriori bound, returns the level to which we should backtrack, or INT_MAX for continuing normally
- Parameters
-
tcliquegraph pointer to graph data structure tcliquedata user data to pass to user callback function mem block memory cliquehash clique hash table buffer buffer of size nnodes level level of b&b tree V non-zero weighted nodes for branching nV number of non-zero weighted nodes for branching Vzero zero weighted nodes nVzero number of zero weighted nodes gsd neighbour color information of all nodes iscolored coloring status of all nodes K nodes from the b&b tree weightK weight of the nodes from b&b tree 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 curcliquenodes pointer to store nodes of currenct clique ncurcliquenodes pointer to store number of nodes in current clique curcliqueweight pointer to store weight of current clique tmpcliquenodes buffer for storing the temporary clique maxfirstnodeweight maximum weight of branching nodes in level 0; 0 if not used (for cliques with at least one fractional node) ntreenodes pointer to store number of nodes of b&b tree 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 status pointer to store the status of the solving call
Definition at line 708 of file tclique_branch.c.
References ALLOC_ABORT, BMSallocMemoryArray, BMSclearMemoryArray, BMSfreeMemoryArray, BMSgetChunkMemoryUsed, BMSgetMemoryUsed, boundSubgraph(), debugMessage, debugPrintf, FALSE, getMaxApBoundIndex(), getMaxApBoundIndexNotMaxWeight(), newSolution(), NULL, SCIP_LONGINT_FORMAT, TCLIQUE_Bool, TCLIQUE_NODELIMIT, and TRUE.
Referenced by tcliqueMaxClique().
◆ 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 1000 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().