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-2015 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 */
59 extern
60 TCLIQUE_WEIGHT tcliqueColoring(
61  TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
62  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
63  TCLIQUE_SELECTADJNODES((*selectadjnodes)),/**< user function to select adjacent edges */
64  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
65  BMS_CHKMEM* mem, /**< block memory */
66  int* buffer, /**< buffer of size nnodes */
67  int* V, /**< non-zero weighted nodes for branching */
68  int nV, /**< number of non-zero weighted nodes for branching */
69  NBC* gsd, /**< neighbour color information of all nodes */
70  TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
71  TCLIQUE_WEIGHT* apbound, /**< pointer to store apriori bound of nodes for branching */
72  int* clique, /**< buffer for storing the clique */
73  int* nclique, /**< pointer to store number of nodes in the clique */
74  TCLIQUE_WEIGHT* weightclique /**< pointer to store the weight of the clique */
75  );
76 
77 #ifdef __cplusplus
78 }
79 #endif
80 
81 #endif
struct _ITV ITV
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
struct _LIST_ITV LIST_ITV