Detailed Description
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) |
Function Documentation
◆ getMaxSatdegIndex()
|
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 |
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 |
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(), NULL, TCLIQUE_Bool, TRUE, and updateNeighbor().
Referenced by boundSubgraph().