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-2014 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  int inf;
38  int sup;
39 } ITV;
40 
41 typedef struct _LIST_ITV{
42  ITV itv;
43  struct _LIST_ITV *next;
44 } LIST_ITV;
45 
46 typedef struct _NBC{
47  int satdeg;
48  LIST_ITV *lcitv;
49 } NBC;
50 
51 
52 
53 
54 /** colors the positive weighted nodes of a given set of nodes V with the lowest possible number of colors and
55  * finds a clique in the graph induced by V, an upper bound and an apriori bound for further branching steps
56  */
57 extern
58 TCLIQUE_WEIGHT tcliqueColoring(
59  TCLIQUE_GETNNODES((*getnnodes)), /**< user function to get the number of nodes */
60  TCLIQUE_GETWEIGHTS((*getweights)), /**< user function to get the node weights */
61  TCLIQUE_SELECTADJNODES((*selectadjnodes)), /**< user function to select adjacent edges */
62  TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure */
63  BMS_CHKMEM* mem, /**< block memory */
64  int* buffer, /**< buffer of size nnodes */
65  int* V, /**< non-zero weighted nodes for branching */
66  int nV, /**< number of non-zero weighted nodes for branching */
67  NBC* gsd, /**< neighbour color information of all nodes */
68  TCLIQUE_Bool* iscolored, /**< coloring status of all nodes */
69  TCLIQUE_WEIGHT* apbound, /**< pointer to store apriori bound of nodes for branching */
70  int* clique, /**< buffer for storing the clique */
71  int* nclique, /**< pointer to store number of nodes in the clique */
72  TCLIQUE_WEIGHT* weightclique /**< pointer to store the weight of the clique */
73  );
74 
75 #ifdef __cplusplus
76 }
77 #endif
78 
79 #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