Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

coloring part of algorithm for maximum cliques

Author
Tobias Achterberg
Ralf Borndoerfer
Zoltan Kormos
Kati Wolter

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)
 

Function Documentation

◆ getMaxSatdegIndex()

static int getMaxSatdegIndex ( int *  V,
int  nV,
NBC gsd,
TCLIQUE_Bool iscolored,
const TCLIQUE_WEIGHT weights 
)
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

Parameters
Vnon-zero weighted nodes for branching
nVnumber of non-zero weighted nodes for branching
gsdneighbor color information of all nodes
iscoloredcoloring status of all nodes
weightsweight of nodes in grpah

Definition at line 52 of file tclique_coloring.c.

References NULL.

Referenced by tcliqueColoring().

◆ getMaxWeightIndex()

static int getMaxWeightIndex ( TCLIQUE_GETNNODES((*getnnodes))  ,
TCLIQUE_GETWEIGHTS((*getweights))  ,
TCLIQUE_GRAPH tcliquegraph,
int *  V,
int  nV 
)
static

gets index of the node in a given set of nodes with maximum weight

Parameters
tcliquegraphpointer to graph data structure
Vnon-zero weighted nodes for branching
nVnumber of non-zero weighted nodes for branching

Definition at line 98 of file tclique_coloring.c.

References NULL.

Referenced by tcliqueColoring().

◆ updateNeighbor()

static void updateNeighbor ( BMS_CHKMEM mem,
NBC pgsd,
LIST_ITV pnc 
)
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

Parameters
memblock memory
pgsdpointer to neighbor color information of node to update
pncpointer to given list of color intervals

Definition at line 142 of file tclique_coloring.c.

References ALLOC_ABORT, BMSallocChunkMemory, BMSfreeChunkMemory, and NULL.

Referenced by tcliqueColoring().

◆ 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

Parameters
tcliquegraphpointer to graph data structure
memblock memory
bufferbuffer of size nnodes
Vnon-zero weighted nodes for branching
nVnumber of non-zero weighted nodes for branching
gsdneighbor color information of all nodes
iscoloredcoloring status of all nodes
apboundpointer to store apriori bound of nodes for branching
cliquebuffer for storing the clique
ncliquepointer to store number of nodes in the clique
weightcliquepointer to store the weight of the clique

Definition at line 230 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().