Detailed Description
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.
Function Documentation
◆ COLORprobGetNStableSets()
int COLORprobGetNStableSets | ( | SCIP * | scip | ) |
returns the number of stable sets / variables
- Parameters
-
scip SCIP data structure
Definition at line 762 of file probdata_coloring.c.
References NULL, and SCIPgetProbData().
Referenced by COLORprobStableSetIsNew(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERINITSOL(), and SCIP_DECL_PRICERREDCOST().
◆ COLORprobGetStableSet()
void COLORprobGetStableSet | ( | SCIP * | scip, |
int | setindex, | ||
int ** | stableset, | ||
int * | nelements | ||
) |
returns the stable set with the given index
- Parameters
-
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 NULL, and SCIPgetProbData().
Referenced by computeBranchingPriorities(), and SCIP_DECL_BRANCHEXECLP().
◆ COLORprobGetStableSets()
void COLORprobGetStableSets | ( | SCIP * | scip, |
int *** | stablesets, | ||
int ** | nelements, | ||
int * | nstablesets | ||
) |
returns all stable sets
- Parameters
-
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 NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_CONSPROP(), SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_READERWRITE().
◆ COLORprobAddNewStableSet()
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;
- Note
- you need to check whether it is new before adding it
- Parameters
-
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 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().
◆ COLORprobAddVarForStableSet()
SCIP_RETCODE COLORprobAddVarForStableSet | ( | SCIP * | scip, |
int | setindex, | ||
SCIP_VAR * | var | ||
) |
adds a variable that belongs to a given stable set
- Parameters
-
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 EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_VARDELETED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPfindEventhdlr(), and SCIPgetProbData().
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERREDCOST(), and SCIP_DECL_READERREAD().
◆ COLORprobGetVarForStableSet()
gets the variable belonging to a given stable set
- Parameters
-
scip SCIP data structure setindex index of the stable set
Definition at line 856 of file probdata_coloring.c.
References NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_READERWRITE().
◆ COLORprobStableSetIsNew()
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
- Parameters
-
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 COLORprobGetNStableSets(), COLORprobStableSetsAreEqual(), FALSE, NULL, SCIPgetProbData(), SCIPsortDownInt(), and TRUE.
Referenced by SCIP_DECL_PRICERREDCOST(), and TCLIQUE_NEWSOL().
◆ COLORprobStableSetsAreEqual()
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
- Parameters
-
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 FALSE, NULL, and TRUE.
Referenced by COLORprobStableSetIsNew().
◆ COLORprobPrintStableSets()
void COLORprobPrintStableSets | ( | SCIP * | scip | ) |
prints all stable sets to standart output
prints all stable sets to standard output
- Parameters
-
scip SCIP data structure
Definition at line 777 of file probdata_coloring.c.
References NULL, SCIPgetProbData(), SCIPvarGetUbLocal(), and SCIPvarIsInLP().
◆ COLORprobPrintStableSet()
void COLORprobPrintStableSet | ( | SCIP * | scip, |
int | setnumber | ||
) |
prints the requested stable set to standart output
prints the requested stable set to standard output
- Parameters
-
scip SCIP data structure setnumber the number of the requested set
Definition at line 804 of file probdata_coloring.c.
References NULL, SCIPgetProbData(), and SCIPvarGetUbLocal().
◆ COLORprobIsNodeInStableSet()
checks whether a node is in a given stable set, returns true iff it is
- Parameters
-
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 FALSE, NULL, SCIPgetProbData(), and TRUE.
Referenced by computeBranchingPriorities(), and SCIP_DECL_CONSPROP().
◆ COLORprobSetUpArrayOfCons()
SCIP_RETCODE COLORprobSetUpArrayOfCons | ( | SCIP * | scip | ) |
creates all node-constraints and saves them in an array
- Parameters
-
scip SCIP data structure
Definition at line 1305 of file probdata_coloring.c.
References COLORprobGetConstraints(), COLORprobGetNNodes(), FALSE, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSetcover(), SCIPsnprintf(), and TRUE.
Referenced by readCol().
◆ COLORprobGetConstraints()
returns all node-constraints
- Parameters
-
scip SCIP data structure
Definition at line 1190 of file probdata_coloring.c.
References NULL, and SCIPgetProbData().
Referenced by COLORprobSetUpArrayOfCons(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERREDCOST(), and SCIP_DECL_READERREAD().
◆ COLORprobGetConstraint()
returns the node-constraint belonging to a given node
- Parameters
-
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 NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_CONSACTIVE().
◆ COLORprobGetGraph()
TCLIQUE_GRAPH* COLORprobGetGraph | ( | SCIP * | scip | ) |
returns the (preprocessed) graph
- Parameters
-
scip SCIP data structure
Definition at line 1101 of file probdata_coloring.c.
References NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_CONSINITSOL(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_READERREAD().
◆ COLORprobGetOriginalGraph()
TCLIQUE_GRAPH* COLORprobGetOriginalGraph | ( | SCIP * | scip | ) |
returns the original graph
- Parameters
-
scip SCIP data structure
Definition at line 1117 of file probdata_coloring.c.
References NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_READERWRITE().
◆ COLORprobGetComplementaryGraph()
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
- Parameters
-
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 COLORprobGetNNodes(), nnodes, NULL, SCIP_ERROR, SCIP_OKAY, SCIPerrorMessage, tcliqueAddEdge(), tcliqueAddNode(), tcliqueFlush(), tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().
Referenced by createConsStoreGraphAtRoot(), and SCIP_DECL_CONSACTIVE().
◆ COLORprobGetNNodes()
int COLORprobGetNNodes | ( | SCIP * | scip | ) |
returns the number of nodes in the (preprocessed) graph
- Parameters
-
scip SCIP data structure
Definition at line 1071 of file probdata_coloring.c.
References 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().
◆ COLORprobGetOriginalNNodes()
int COLORprobGetOriginalNNodes | ( | SCIP * | scip | ) |
returns the number of nodes in the original graph
- Parameters
-
scip SCIP data structure
Definition at line 1086 of file probdata_coloring.c.
References NULL, and SCIPgetProbData().
Referenced by COLORprobGetNewNodeForOriginalNode(), preprocessGraph(), SCIP_DECL_READERREAD(), and SCIP_DECL_READERWRITE().
◆ COLORprobGetDeletedNodes()
int* COLORprobGetDeletedNodes | ( | SCIP * | scip | ) |
returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(), filled with -1 at the end
- Parameters
-
scip SCIP data structure
Definition at line 1132 of file probdata_coloring.c.
References NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_READERWRITE().
◆ COLORprobGetOriginalNodesForNewNodes()
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
- Parameters
-
scip SCIP data structure
Definition at line 1147 of file probdata_coloring.c.
References NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_READERWRITE().
◆ COLORprobGetNewNodeForOriginalNode()
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
- Parameters
-
scip SCIP data structure node a node in the original graph
Definition at line 1163 of file probdata_coloring.c.
References COLORprobGetOriginalNNodes(), NULL, and SCIPgetProbData().
Referenced by SCIP_DECL_READERREAD().
◆ COLORprobIsNodeInArray()
SCIP_Bool COLORprobIsNodeInArray | ( | int | node, |
int * | arraynodes, | ||
int | narraynodes | ||
) |
checks whether the given node is in the given array
- Parameters
-
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 FALSE, NULL, and TRUE.
Referenced by preprocessGraph().
◆ COLORprobEqualSortedArrays()
SCIP_Bool COLORprobEqualSortedArrays | ( | int * | array1nodes, |
int | narray1nodes, | ||
int * | array2nodes, | ||
int | narray2nodes | ||
) |
checks whether the given two given arrays are equal
- Parameters
-
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.
◆ SCIPcreateProbColoring()
SCIP_RETCODE SCIPcreateProbColoring | ( | SCIP * | scip, |
const char * | name, | ||
int | nnodes, | ||
int | nedges, | ||
int ** | edges | ||
) |
sets up the problem data
- Parameters
-
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 EVENTHDLR_DESC, EVENTHDLR_NAME, nnodes, NULL, preprocessGraph(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcreateProb(), SCIPerrorMessage, SCIPincludeEventhdlrBasic(), tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), and tcliqueFlush().
Referenced by readCol().