Scippy

SCIP

Solving Constraint Integer Programs

tclique_coloring.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* TCLIQUE --- Algorithm for Maximum Cliques */
5 /* */
6 /* Copyright (C) 1996-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* TCLIQUE is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with TCLIQUE; see the file COPYING. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file tclique_coloring.h
17  * @brief coloring part of algorithm for maximum cliques
18  * @author Tobias Achterberg
19  * @author Ralf Borndoerfer
20  * @author Zoltan Kormos
21  * @author Kati Wolter
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #ifndef __TCLIQUE_COLORING_H__
27 #define __TCLIQUE_COLORING_H__
28 
29 #include "blockmemshell/memory.h"
30 #include "tclique/tclique.h"
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 typedef struct _ITV
37 {
38  int inf;
39  int sup;
40 } ITV;
41 
42 typedef struct _LIST_ITV
43 {
44  ITV itv;
45  struct _LIST_ITV *next;
46 } LIST_ITV;
47 
48 typedef struct _NBC
49 {
50  int satdeg;
51  LIST_ITV *lcitv;
52 } NBC;
53 
54 
55 
56 
57 /** colors the positive weighted nodes of a given set of nodes V with the lowest possible number of colors and
58  * finds a clique in the graph induced by V, an upper bound and an apriori bound for further branching steps */
60  TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
61  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
62  TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
63  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
64  BMS_CHKMEM* mem, /**< block memory */
65  int* buffer, /**< buffer of size nnodes */
66  int* V, /**< non-zero weighted nodes for branching */
67  int nV, /**< number of non-zero weighted nodes for branching */
68  NBC* gsd, /**< neighbour color information of all nodes */
69  TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
70  TCLIQUE_WEIGHT* apbound, /**< pointer to store apriori bound of nodes for branching */
71  int* clique, /**< buffer for storing the clique */
72  int* nclique, /**< pointer to store number of nodes in the clique */
73  TCLIQUE_WEIGHT* weightclique /**< pointer to store the weight of the clique */
74  );
75 
76 #ifdef __cplusplus
77 }
78 #endif
79 
80 #endif
#define TCLIQUE_GETWEIGHTS(x)
Definition: tclique.h:96
struct BMS_ChkMem BMS_CHKMEM
Definition: memory.h:294
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
#define TCLIQUE_SELECTADJNODES(x)
Definition: tclique.h:121
struct _ITV ITV
tclique user interface
#define TCLIQUE_Bool
Definition: tclique.h:44
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)
struct _NBC NBC
#define TCLIQUE_GETNNODES(x)
Definition: tclique.h:88
int TCLIQUE_WEIGHT
Definition: tclique.h:39
struct _LIST_ITV LIST_ITV
memory allocation routines