problem data for vertex coloring algorithm
This file implements the problem data for the coloring algorithm.
The problem data contains the original graph, preprocessing information, the preprocessed graph, the array with the node-constraints, and an array with all stable sets and corresponding variables.
The preprocessing deletes nodes that have a lower degree than the size of a maximum clique. Additionally, it also deletes nodes that have a dominated neighborhood. For further information, look at the documentation for the method preprocessGraph().
The deleted nodes and the relation between the nodes of the original graph and the nodes of the preprocessed graph are stored in order to convert a solution of the preprocessed problem to a solution for the original graph and vice versa.
Each variable has a pointer of type SCIP_VARDATA* that is used in this case to store an integer representing the number of the stable set. With the aid of this, the corresponding stable set can be found in the array returned by COLORprobGetStableSets(). This array contains all stable sets and is also used to check whether a stable set found by the pricer is really new. This can be done by calling COLORprobStableSetIsNew(). All sets are sorted decreasingly with respect to the indices of the nodes. New candidates should also be sorted that way.
Definition in file probdata_coloring.h.
#include <assert.h>
#include "scip/scip.h"
#include "tclique/tclique.h"
#include "scip/cons_setppc.h"
#include "reader_col.h"
Go to the source code of this file.
int COLORprobGetNStableSets | ( | SCIP * | scip | ) |
returns the number of stable sets / variables
scip | SCIP data structure |
Definition at line 762 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by COLORprobStableSetIsNew(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERINITSOL(), and SCIP_DECL_PRICERREDCOST().
void COLORprobGetStableSet | ( | SCIP * | scip, |
int | setindex, | ||
int ** | stableset, | ||
int * | nelements ) |
returns the stable set with the given index
scip | SCIP data structure |
setindex | index of the stable set |
stableset | return value: pointer to the stable set |
nelements | return value: number of elements in the stable set |
Definition at line 1032 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by computeBranchingPriorities(), and SCIP_DECL_BRANCHEXECLP().
void COLORprobGetStableSets | ( | SCIP * | scip, |
int *** | stablesets, | ||
int ** | nelements, | ||
int * | nstablesets ) |
returns all stable sets
scip | SCIP data structure |
stablesets | return value: pointer to the stable sets |
nelements | return value: number of elements in the stable sets |
nstablesets | return value: number of sets |
Definition at line 1051 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_CONSPROP(), SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_READERWRITE().
SCIP_RETCODE COLORprobAddNewStableSet | ( | SCIP * | scip, |
int * | stablesetnodes, | ||
int | nstablesetnodes, | ||
int * | setindex ) |
adds a new stable set, the set must be sorted descendingly, attention: you need to check whether it is new before adding it
adds a new stable set, the set must be sorted in descending order;
scip | SCIP data structure |
stablesetnodes | array of nodes in the stable set |
nstablesetnodes | number of nodes in the stable set |
setindex | return value: index of the stable set |
Definition at line 978 of file probdata_coloring.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPdebugMessage, SCIPgetProbData(), and SCIPreallocBlockMemoryArray.
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERREDCOST(), and SCIP_DECL_READERREAD().
SCIP_RETCODE COLORprobAddVarForStableSet | ( | SCIP * | scip, |
int | setindex, | ||
SCIP_VAR * | var ) |
adds a variable that belongs to a given stable set
scip | SCIP data structure |
setindex | index of the stable set |
var | pointer to the variable |
Definition at line 832 of file probdata_coloring.c.
References assert(), EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_VARDELETED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPfindEventhdlr(), SCIPgetProbData(), and var.
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERREDCOST(), and SCIP_DECL_READERREAD().
gets the variable belonging to a given stable set
scip | SCIP data structure |
setindex | index of the stable set |
Definition at line 856 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_READERWRITE().
checks whether the given stable set is new, returns TRUE if the stable is new and FALSE if it is part of or equal to an already existing stable set
checks whether the given stable set is new returns TRUE if the stable is new, FALSE if it is equal to an already existing stable set
scip | SCIP data structure |
stablesetnodes | array of nodes in the stable set |
nstablesetnodes | number of nodes in the stable set |
Definition at line 945 of file probdata_coloring.c.
References assert(), COLORprobGetNStableSets(), COLORprobStableSetsAreEqual(), FALSE, i, NULL, SCIP_Bool, SCIPgetProbData(), SCIPsortDownInt(), and TRUE.
Referenced by SCIP_DECL_PRICERREDCOST(), and TCLIQUE_NEWSOL().
SCIP_Bool COLORprobStableSetsAreEqual | ( | SCIP * | scip, |
int * | set1, | ||
int | nset1nodes, | ||
int * | set2, | ||
int | nset2nodes ) |
checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way
scip | SCIP data structure |
set1 | array of nodes in the first set |
nset1nodes | number of nodes in the first set |
set2 | array of nodes in the second set |
nset2nodes | number of nodes in the second set |
Definition at line 911 of file probdata_coloring.c.
References assert(), FALSE, i, NULL, SCIP_Bool, and TRUE.
Referenced by COLORprobStableSetIsNew().
void COLORprobPrintStableSets | ( | SCIP * | scip | ) |
prints all stable sets to standart output
prints all stable sets to standard output
scip | SCIP data structure |
Definition at line 777 of file probdata_coloring.c.
References assert(), i, NULL, SCIPgetProbData(), SCIPvarGetUbLocal(), and SCIPvarIsInLP().
void COLORprobPrintStableSet | ( | SCIP * | scip, |
int | setnumber ) |
prints the requested stable set to standart output
prints the requested stable set to standard output
scip | SCIP data structure |
setnumber | the number of the requested set |
Definition at line 804 of file probdata_coloring.c.
References assert(), i, NULL, SCIPgetProbData(), and SCIPvarGetUbLocal().
checks whether a node is in a given stable set, returns true iff it is
scip | SCIP data structure |
setindex | index of the stable set |
node | number of the node |
Definition at line 873 of file probdata_coloring.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIPgetProbData(), and TRUE.
Referenced by computeBranchingPriorities(), and SCIP_DECL_CONSPROP().
SCIP_RETCODE COLORprobSetUpArrayOfCons | ( | SCIP * | scip | ) |
creates all node-constraints and saves them in an array
scip | SCIP data structure |
Definition at line 1305 of file probdata_coloring.c.
References assert(), COLORprobGetConstraints(), COLORprobGetNNodes(), FALSE, i, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSetcover(), SCIPsnprintf(), and TRUE.
Referenced by readCol().
returns all node-constraints
scip | SCIP data structure |
Definition at line 1190 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by COLORprobSetUpArrayOfCons(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERREDCOST(), and SCIP_DECL_READERREAD().
returns the node-constraint belonging to a given node
scip | SCIP data structure |
node | number of the node, for which this constraint assures coloring |
Definition at line 1205 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_CONSACTIVE().
TCLIQUE_GRAPH * COLORprobGetGraph | ( | SCIP * | scip | ) |
returns the (preprocessed) graph
scip | SCIP data structure |
Definition at line 1101 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_CONSINITSOL(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_READERREAD().
TCLIQUE_GRAPH * COLORprobGetOriginalGraph | ( | SCIP * | scip | ) |
returns the original graph
scip | SCIP data structure |
Definition at line 1117 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_READERWRITE().
SCIP_RETCODE COLORprobGetComplementaryGraph | ( | SCIP * | scip, |
TCLIQUE_GRAPH * | graph, | ||
TCLIQUE_GRAPH * | cgraph ) |
computes the complementary graph for a given graph and stores it in the given pointer
scip | SCIP data structure |
graph | the given graph |
cgraph | the complementary graph is saved in here |
Definition at line 1222 of file probdata_coloring.c.
References assert(), COLORprobGetNNodes(), i, nnodes, NULL, SCIP_ERROR, SCIP_OKAY, SCIPerrorMessage, tcliqueAddEdge(), tcliqueAddNode(), tcliqueFlush(), tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().
Referenced by createConsStoreGraphAtRoot(), and SCIP_DECL_CONSACTIVE().
int COLORprobGetNNodes | ( | SCIP * | scip | ) |
returns the number of nodes in the (preprocessed) graph
scip | SCIP data structure |
Definition at line 1071 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by COLORprobGetComplementaryGraph(), COLORprobSetUpArrayOfCons(), computeBranchingPriorities(), greedyInitialColoring(), index2nodes(), nodes2index(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), SCIP_DECL_BRANCHINIT(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PARAMCHGD(), SCIP_DECL_PRICEREXITSOL(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERINITSOL(), and SCIP_DECL_READERREAD().
int COLORprobGetOriginalNNodes | ( | SCIP * | scip | ) |
returns the number of nodes in the original graph
scip | SCIP data structure |
Definition at line 1086 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by COLORprobGetNewNodeForOriginalNode(), preprocessGraph(), SCIP_DECL_READERREAD(), and SCIP_DECL_READERWRITE().
int * COLORprobGetDeletedNodes | ( | SCIP * | scip | ) |
returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(), filled with -1 at the end
scip | SCIP data structure |
Definition at line 1132 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_READERWRITE().
int * COLORprobGetOriginalNodesForNewNodes | ( | SCIP * | scip | ) |
returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved
scip | SCIP data structure |
Definition at line 1147 of file probdata_coloring.c.
References assert(), NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_READERWRITE().
int COLORprobGetNewNodeForOriginalNode | ( | SCIP * | scip, |
int | node ) |
returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted
scip | SCIP data structure |
node | a node in the original graph |
Definition at line 1163 of file probdata_coloring.c.
References assert(), COLORprobGetOriginalNNodes(), i, NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_READERREAD().
SCIP_Bool COLORprobIsNodeInArray | ( | int | node, |
int * | arraynodes, | ||
int | narraynodes ) |
checks whether the given node is in the given array
node | the number of the node |
arraynodes | the nodes of the maximum stableset |
narraynodes | number of nodes in the maximum stableset |
Definition at line 1334 of file probdata_coloring.c.
References assert(), FALSE, i, NULL, SCIP_Bool, and TRUE.
Referenced by preprocessGraph().
SCIP_Bool COLORprobEqualSortedArrays | ( | int * | array1nodes, |
int | narray1nodes, | ||
int * | array2nodes, | ||
int | narray2nodes ) |
checks whether the given two given arrays are equal
array1nodes | the nodes of the first set |
narray1nodes | number of nodes in the first set |
array2nodes | the nodes of the second set |
narray2nodes | number of nodes in the second set |
Definition at line 1355 of file probdata_coloring.c.
SCIP_RETCODE SCIPcreateProbColoring | ( | SCIP * | scip, |
const char * | name, | ||
int | nnodes, | ||
int | nedges, | ||
int ** | edges ) |
sets up the problem data
scip | SCIP data structure |
name | problem name |
nnodes | number of nodes |
nedges | number of edges |
edges | array with start- and endpoints of the edges |
Definition at line 680 of file probdata_coloring.c.
References assert(), EVENTHDLR_DESC, EVENTHDLR_NAME, i, nnodes, NULL, preprocessGraph(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcreateProb(), SCIPerrorMessage, SCIPincludeEventhdlrBasic(), tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), and tcliqueFlush().
Referenced by readCol().