tclique_coloring.c File Reference

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

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

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

mem	block memory
pgsd	pointer to neighbor color information of node to update
pnc	pointer 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

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 230 of file tclique_coloring.c.

References ALLOC_ABORT, BMSallocChunkMemory, BMSallocMemoryArray, BMSclearChunkMemory, BMSclearMemoryArray, BMScopyMemoryArray, BMSfreeChunkMemory, BMSfreeMemoryArray, debugMessage, debugPrintf, FALSE, getMaxSatdegIndex(), getMaxWeightIndex(), scip::min(), NULL, TCLIQUE_Bool, TRUE, and updateNeighbor().

Referenced by boundSubgraph().