SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
coloring part of algorithm for maximum cliques
Definition in file tclique_coloring.c.
#include <stdio.h>#include <assert.h>#include <stdlib.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.
Functions | |
| static int | getMaxSatdegIndex (int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, const TCLIQUE_WEIGHT *weights) |
| static int | getMaxWeightIndex (TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_GRAPH *tcliquegraph, int *V, int nV) |
| static void | updateNeighbor (BMS_CHKMEM *mem, NBC *pgsd, LIST_ITV *pnc) |
| TCLIQUE_WEIGHT | tcliqueColoring (TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, BMS_CHKMEM *mem, int *buffer, int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, TCLIQUE_WEIGHT *apbound, int *clique, int *nclique, TCLIQUE_WEIGHT *weightclique) |
|
static |
gets index of the uncolored node in a given array of nodes in V with maximum satdeg; in case of a tie choose node with maximum weight; if no uncolored node is found, -1 is returned
| V | non-zero weighted nodes for branching |
| nV | number of non-zero weighted nodes for branching |
| gsd | neighbor color information of all nodes |
| iscolored | coloring status of all nodes |
| weights | weight of nodes in grpah |
Definition at line 42 of file tclique_coloring.c.
References NULL.
Referenced by tcliqueColoring().
|
static |
gets index of the node in a given set of nodes with maximum weight
| tcliquegraph | pointer to graph data structure |
| V | non-zero weighted nodes for branching |
| nV | number of non-zero weighted nodes for branching |
Definition at line 88 of file tclique_coloring.c.
References NULL.
Referenced by tcliqueColoring().
|
static |
updates the neighbor colors information of a node: updates the list of neighbor color intervals by making the union of the existing list and the given list of color intervals, and updates the saturation degree
| mem | block memory |
| pgsd | pointer to neighbor color information of node to update |
| pnc | pointer to given list of color intervals |
Definition at line 132 of file tclique_coloring.c.
References ALLOC_ABORT, BMSallocChunkMemory, BMSfreeChunkMemory, and NULL.
Referenced by tcliqueColoring().
| TCLIQUE_WEIGHT tcliqueColoring | ( | TCLIQUE_GETNNODES((*getnnodes)) | , |
| TCLIQUE_GETWEIGHTS((*getweights)) | , | ||
| TCLIQUE_SELECTADJNODES((*selectadjnodes)) | , | ||
| TCLIQUE_GRAPH * | tcliquegraph, | ||
| BMS_CHKMEM * | mem, | ||
| int * | buffer, | ||
| int * | V, | ||
| int | nV, | ||
| NBC * | gsd, | ||
| TCLIQUE_Bool * | iscolored, | ||
| TCLIQUE_WEIGHT * | apbound, | ||
| int * | clique, | ||
| int * | nclique, | ||
| TCLIQUE_WEIGHT * | weightclique | ||
| ) |
colors the positive weighted nodes of a given set of nodes V with the lowest possible number of colors and finds a clique in the graph induced by V, an upper bound and an apriori bound for further branching steps
| 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 | neighbor color information of all nodes |
| iscolored | coloring status of all nodes |
| apbound | pointer to store apriori bound of nodes for branching |
| clique | buffer for storing the clique |
| nclique | pointer to store number of nodes in the clique |
| weightclique | pointer to store the weight of the clique |
Definition at line 219 of file tclique_coloring.c.
References ALLOC_ABORT, BMSallocChunkMemory, BMSallocMemoryArray, BMSclearChunkMemory, BMSclearMemoryArray, BMScopyMemoryArray, BMSfreeChunkMemory, BMSfreeMemoryArray, debugMessage, debugPrintf, FALSE, getMaxSatdegIndex(), getMaxWeightIndex(), NULL, TCLIQUE_Bool, TRUE, and updateNeighbor().
Referenced by boundSubgraph().