1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program */ 4 /* TCLIQUE --- Algorithm for Maximum Cliques */ 5 /* */ 6 /* Copyright (c) 1996-2023 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 */ 68 TCLIQUE_WEIGHT tcliqueColoring( 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 90