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
39#include "tclique/tclique.h"
40
41#ifdef __cplusplus
42extern "C" {
43#endif
44
45typedef struct _ITV
46{
47 int inf;
48 int sup;
50
51typedef struct _LIST_ITV
52{
53 ITV itv;
54 struct _LIST_ITV *next;
56
57typedef struct _NBC
58{
59 int satdeg;
60 LIST_ITV *lcitv;
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
memory allocation routines
struct BMS_ChkMem BMS_CHKMEM
Definition: memory.h:302
tclique user interface
#define TCLIQUE_GETWEIGHTS(x)
Definition: tclique.h:105
#define TCLIQUE_GETNNODES(x)
Definition: tclique.h:97
#define TCLIQUE_SELECTADJNODES(x)
Definition: tclique.h:130
int TCLIQUE_WEIGHT
Definition: tclique.h:48
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
#define TCLIQUE_Bool
Definition: tclique.h:53
struct _LIST_ITV LIST_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 _ITV ITV
struct _NBC NBC