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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with TCLIQUE; see the file LICENSE. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file tclique_coloring.h
26  * @brief coloring part of algorithm for maximum cliques
27  * @author Tobias Achterberg
28  * @author Ralf Borndoerfer
29  * @author Zoltan Kormos
30  * @author Kati Wolter
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #ifndef __TCLIQUE_COLORING_H__
36 #define __TCLIQUE_COLORING_H__
37 
38 #include "blockmemshell/memory.h"
39 #include "tclique/tclique.h"
40 
41 #ifdef __cplusplus
42 extern "C" {
43 #endif
44 
45 typedef struct _ITV
46 {
47  int inf;
48  int sup;
49 } ITV;
50 
51 typedef struct _LIST_ITV
52 {
53  ITV itv;
54  struct _LIST_ITV *next;
55 } LIST_ITV;
56 
57 typedef struct _NBC
58 {
59  int satdeg;
60  LIST_ITV *lcitv;
61 } NBC;
62 
63 
64 
65 
66 /** colors the positive weighted nodes of a given set of nodes V with the lowest possible number of colors and
67  * finds a clique in the graph induced by V, an upper bound and an apriori bound for further branching steps */
69  TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
70  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
71  TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
72  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
73  BMS_CHKMEM* mem, /**< block memory */
74  int* buffer, /**< buffer of size nnodes */
75  int* V, /**< non-zero weighted nodes for branching */
76  int nV, /**< number of non-zero weighted nodes for branching */
77  NBC* gsd, /**< neighbour color information of all nodes */
78  TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
79  TCLIQUE_WEIGHT* apbound, /**< pointer to store apriori bound of nodes for branching */
80  int* clique, /**< buffer for storing the clique */
81  int* nclique, /**< pointer to store number of nodes in the clique */
82  TCLIQUE_WEIGHT* weightclique /**< pointer to store the weight of the clique */
83  );
84 
85 #ifdef __cplusplus
86 }
87 #endif
88 
89 #endif
#define TCLIQUE_GETWEIGHTS(x)
Definition: tclique.h:105
struct BMS_ChkMem BMS_CHKMEM
Definition: memory.h:302
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
#define TCLIQUE_SELECTADJNODES(x)
Definition: tclique.h:130
struct _ITV ITV
tclique user interface
#define TCLIQUE_Bool
Definition: tclique.h:53
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:97
int TCLIQUE_WEIGHT
Definition: tclique.h:48
struct _LIST_ITV LIST_ITV
memory allocation routines