-
Notifications
You must be signed in to change notification settings - Fork 6
/
mwis.h
133 lines (107 loc) · 5.85 KB
/
mwis.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#ifndef __MWIS_H
#define __MWIS_H
/**
This file is part of exactcolors.
exactcolors is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
exactcolors is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with exactcolors. If not, see <http://www.gnu.org/licenses/>.
*/
#include "graph.h"
#include "color.h"
typedef struct _MWISenv MWISenv;
typedef struct _MWISgrb_env MWISgrb_env;
typedef struct _MWISls_env MWISls_env;
int COLORstable_initenv(MWISenv** env, const char* pname,
int write_mwis);
/* Fill newsets with independent sets of node weight larger than
cutoff, or leave it empty, if no such independent set exists.
@param env: the stable set environment that needs to be initialized with COLORstable_initenv beforehand.
@param newsets: The collection of stable sets with weight > cutoff computed by the algorithm.
@param nnewsets: The number of stable sets in the collection
@param ncount: number of vertices of the input graph
@param ecount: number of edges of the input graph
@param nweights: vertex weights of the input graph
@param cutoff: cutoff value for stable set weights. Only stable sets of weight > cutoff computed if exist.
Stable sets with weight below the cutoff are irrelevant. E.g. in the context of column generation
for graph coloring the cutoff is 1.0, because only such sets can improve the LP relaxation.
@param greedy_only: Run only fast greedy functions without guaranteeing to actually find a set of weight > cutoff.
@param force_rounding: round down all weights as much as possible without lowering the estimated lower bound,
to make it more likely that the result will be below the cutoff.
@param rounding_strategy: Chose rounding strategy to be applied. The strategy is used to round down weights
after one solution has been found to force detecting structurally different solutions while the
algorithm continues. In particular the found solution is forced to have weight <=1.0 after rounding.
*/
int COLORstable_wrapper(MWISenv** env,
COLORset** newsets, int* nnewsets,
int ncount, int ecount, const int elist[], COLORNWT nweights[],
COLORNWT cutoff, int greedy_only, int force_rounding, int rounding_strategy);
int COLORstable_LS(MWISls_env** env,
COLORset** newsets, int* nnewsets, int ncount,
int ecount, const int elist[],
const COLORNWT nweights[],COLORNWT cutoff);
int COLORstable_init_LS(MWISls_env** env,
int ncount,
int ecount, const int elist[],
const COLORNWT nweights[], COLORNWT cutoff);
int COLORstable_gurobi(MWISgrb_env** env,
COLORset** newsets, int* nnewsets,
int ncount, int ecount, const int elist[], COLORNWT nweights[],
COLORNWT cutoff);
int COLORstable_write_mps(const char* filename,
int ncount, int ecount, const int elist[],
const COLORNWT nweights[],
COLORNWT cutoff);
int COLORstable_read_stable_sets(COLORset** newsets, int* nnewsets,
int ncount,
const char* fname,
const char* proplem_name);
int COLORstable_write_stable_sets(const COLORset* sets, int nsets,
int ncount,
const char* fname,
const char* problem_name);
int COLORstable_round_down_weights(MWISls_env* env,
COLORNWT nweights[],
COLORNWT cutoff);
/*
Passes the node weights of type double from dbl_nweights to weights
of type COLORNWT in nweights while scaling them by a the value
scalef, which is determined on the fly and written to *scalef.
*/
int COLOR_double2COLORNWT(COLORNWT nweights[],
COLORNWT* scalef,
const double dbl_nweights[],
int ncount);
/*
Passes the node weights of type COLORNWT from nweights to weights
of type double in dbl_nweights while dividing them by a the value
divider.
*/
int COLOR_COLORNWT2double(double dbl_nweights[],
const COLORNWT nweights[],
COLORNWT divider,
int ncount);
/** Write the stable set problem in dimacs format, adding the value of
cutoff in the comment.
*/
int COLORstable_write_dimacs(const char* filename,
int ncount, int ecount, const int elist[],
const COLORNWT nweights[],
COLORNWT cutoff);
/** Write the stable set problem as a clique problem in the complement
graph in dimacs format, adding the value of cutoff in the comment.
*/
int COLORstable_write_dimacs_clique(const char* filename,
int ncount, int ecount, const int elist[],
const COLORNWT nweights[],
COLORNWT cutoff);
int COLORstable_freeenv(MWISenv** env);
int COLORstable_free_ls_env(MWISls_env** env);
int COLORstable_free_grb_env(MWISgrb_env** env);
#endif