probdata_coloring.c
Go to the documentation of this file.
31 * The problem data contains the original graph, preprocessing information, the preprocessed graph,
36 * Additionally, it also deletes nodes that have a dominated neighborhood. For further information,
39 * The deleted nodes and the relation between the nodes of the original graph and the nodes of the
43 * Each variable has a pointer of type SCIP_VARDATA* that is used in this case to store an integer
44 * representing the number of the stable set. With the aid of this, the corresponding stable set can
45 * be found in the array returned by COLORprobGetStableSets(). This array contains all stable sets
47 * done by calling COLORprobStableSetIsNew(). All sets are sorted decreasingly with respect to the
51/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
73 int* new2oldnode; /* new2oldnode[i] = j iff node i in the (preprocessed) graph corresponds to node j in the old graph*/
103 SCIP_Bool dominates; /* is the neighbourhood of one node dominated by the neigbourhood of another one?*/
115 int nnodesdeleteddegreethisround; /* the number of nodes deleted due to low degree in the current round */
116 int nnodesdeletedneighbourthisround; /* the number of nodes deleted due to neighborhood in the current round */
222 /* node will be in the new graph, because degree is not low enough for deletion or it is in the maxClique */
230 /* at least one node was deleted, create new graph (tclique doesn't support deletion of nodes) */
290 /* set the corresponding old node to -1 for all nodes not in the current graph (only for bug-finding) */
308 assert(!COLORprobIsNodeInArray(probdata->new2oldnode[i], probdata->deletednodes, ndeletednodes));
365 /* at least one node was deleted, create new graph (tclique doesn't support deletion of nodes) */
427 /* set the corresponding old node to -1 for all nodes not in the current graph (only for bug-finding) */
486 (*targetdata)->nstablesets = sourcedata->nstablesets; /* copy number of sets saved in array sets */
490 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesets), sourcedata->maxstablesets) );
491 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesetlengths), sourcedata->maxstablesets) );
492 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesetvars), sourcedata->maxstablesets) );
493 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->deletednodes), tcliqueGetNNodes(sourcedata->oldgraph)) );
494 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->new2oldnode), tcliqueGetNNodes(sourcedata->oldgraph)) );
507 SCIP_CALL( SCIPtransformVar(scip, sourcedata->stablesetvars[i], &((*targetdata)->stablesetvars[i])) );
508 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesets[i]), sourcedata->stablesetlengths[i]) ); /*lint !e866*/
517 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*targetdata)->constraints, (*targetdata)->constraintssize) );
519 SCIP_CALL( SCIPtransformConss(scip, tcliqueGetNNodes(sourcedata->graph), sourcedata->constraints,
576 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets[i]), (*probdata)->stablesetlengths[i]); /*lint !e866*/
580 SCIPfreeBlockMemoryArray(scip, &((*probdata)->new2oldnode), tcliqueGetNNodes((*probdata)->oldgraph));
581 SCIPfreeBlockMemoryArray(scip, &((*probdata)->deletednodes), tcliqueGetNNodes((*probdata)->oldgraph));
599 SCIPfreeBlockMemoryArray(scip, &((*probdata)->new2oldnode), tcliqueGetNNodes((*probdata)->oldgraph));
600 SCIPfreeBlockMemoryArray(scip, &((*probdata)->deletednodes), tcliqueGetNNodes((*probdata)->oldgraph));
604 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets[i]), (*probdata)->stablesetlengths[i]); /*lint !e866*/
651 SCIPdebugMessage("remove variable %s [%d] from list of stable sets\n", SCIPvarGetName(var), idx);
656 SCIPfreeBlockMemoryArray(scip, &(probdata->stablesets[idx]), probdata->stablesetlengths[idx]); /*lint !e866*/
735 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->constraints), probdata->constraintssize) );
750 SCIP_CALL( SCIPcreateProb(scip, name, probdelorigColoring, probtransColoring, probdeltransColoring,
845 /* catch variable deleted event on the variable to update the stablesetvars array in the problem data */
846 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_VARDELETED, SCIPfindEventhdlr(scip, EVENTHDLR_NAME),
910/** checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way */
942/** checks whether the given stable set is new returns TRUE if the stable is new, FALSE if it is equal to an already
1007 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesets), probdata->maxstablesets, newsize) );
1008 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesetlengths), probdata->maxstablesets, newsize) );
1009 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesetvars), probdata->maxstablesets, newsize) );
1015 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesets[probdata->nstablesets]), nstablesetnodes) ); /*lint !e866*/
1131/** returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(), filled with -1 at the end */
1146/** returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved */
1162/** returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted */
1325 SCIP_CALL( SCIPcreateConsSetcover(scip, &constraints[i], consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE) );
SCIP_RETCODE SCIPcreateConsSetcover(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9467
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:117
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
Definition: scip_cons.c:1626
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:234
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1349
void SCIPsortDownInt(int *intarray, int len)
Definition: objbenders.h:44
SCIP_RETCODE SCIPcreateProbColoring(SCIP *scip, const char *name, int nnodes, int nedges, int **edges)
Definition: probdata_coloring.c:680
void COLORprobPrintStableSets(SCIP *scip)
Definition: probdata_coloring.c:777
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
Definition: probdata_coloring.c:1032
SCIP_Bool COLORprobIsNodeInArray(int node, int *arraynodes, int narraynodes)
Definition: probdata_coloring.c:1334
int COLORprobGetNewNodeForOriginalNode(SCIP *scip, int node)
Definition: probdata_coloring.c:1163
TCLIQUE_GRAPH * COLORprobGetOriginalGraph(SCIP *scip)
Definition: probdata_coloring.c:1117
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
Definition: probdata_coloring.c:1190
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
Definition: probdata_coloring.c:978
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
Definition: probdata_coloring.c:1147
SCIP_RETCODE COLORprobSetUpArrayOfCons(SCIP *scip)
Definition: probdata_coloring.c:1305
int COLORprobGetOriginalNNodes(SCIP *scip)
Definition: probdata_coloring.c:1086
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
Definition: probdata_coloring.c:856
static SCIP_DECL_EVENTEXEC(eventExecProbdatavardeleted)
Definition: probdata_coloring.c:635
static SCIP_DECL_PROBDELTRANS(probdeltransColoring)
Definition: probdata_coloring.c:559
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
Definition: probdata_coloring.c:1051
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
Definition: probdata_coloring.c:1205
void COLORprobPrintStableSet(SCIP *scip, int setnumber)
Definition: probdata_coloring.c:804
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
Definition: probdata_coloring.c:945
SCIP_Bool COLORprobStableSetsAreEqual(SCIP *scip, int *set1, int nset1nodes, int *set2, int nset2nodes)
Definition: probdata_coloring.c:911
SCIP_Bool COLORprobEqualSortedArrays(int *array1nodes, int narray1nodes, int *array2nodes, int narray2nodes)
Definition: probdata_coloring.c:1355
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
Definition: probdata_coloring.c:1222
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
Definition: probdata_coloring.c:873
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
Definition: probdata_coloring.c:832
static SCIP_DECL_PROBDELORIG(probdelorigColoring)
Definition: probdata_coloring.c:592
int * COLORprobGetDeletedNodes(SCIP *scip)
Definition: probdata_coloring.c:1132
problem data for vertex coloring algorithm
Definition: struct_cons.h:47
Definition: struct_var.h:208
Definition: struct_scip.h:70
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:829
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:362
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
Definition: tclique_graph.c:783
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:805
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
Definition: tclique_branch.c:1010
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
Definition: tclique_graph.c:185
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:340
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
Definition: tclique_graph.c:380