38 using namespace Gecode;
52 Graph(
const int n_v0,
const int n_e0,
const int* e0)
53 : n_v(n_v0), n_e(n_e0), e(e0) {}
56 const int e_20_10[] = {
57 0, 4, 2,12, 12,14, 18,19, 7,10,
58 9,12, 5,11, 6,15, 3,18, 7,16
63 const int e_40_20[] = {
64 21,30, 11,30, 19,38, 20,25, 11,24,
65 20,33, 8,39, 4, 5, 6,16, 5,32,
66 0, 9, 5,24, 25,28, 36,38, 14,20,
67 19,25, 11,22, 13,30, 7,36, 15,33
92 g(
opt.
size() == 0 ? g_20_10 : g_40_20),
93 v(*this,g.n_v,0,1), k(*this,0,g.n_v) {
95 for (
int i = g.
n_e;
i--; ) {
96 const int* e1 = e++;
const int* e2 = e++;
105 v.update(*
this, s.
v);
116 os <<
"\tk = " << k << std::endl
117 <<
"\tv[] = " <<
v << std::endl;
136 IntMaximizeScript::run<IndSet,BAB,SizeOptions>(
opt);
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Parametric base-class for scripts.
void iterations(unsigned int i)
Set default number of iterations.
void solutions(unsigned int n)
Set default number of solutions to search for.
Options for scripts with additional size parameter
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Graph(const int n_v0, const int n_e0, const int *e0)
const int * e
Arrays of edges (as vertex pairs)
const int n_e
Number of edges.
const int n_v
Number of vertices.
Example: Independent sets in a graph
int main(int argc, char *argv[])
Main-function.
IndSet(IndSet &s)
Constructor for cloning s.
const Graph g_20_10(20, 10, e_20_10)
Main-function.
const Graph g_40_20(40, 20, e_40_20)
Main-function.
IntVar k
How many elements has indipendent set.
BoolVarArray v
Whether vertex included in independent set.
virtual Space * copy(void)
Copy during cloning.
virtual void print(std::ostream &os) const
Print solution.
const Graph & g
Graph used
virtual IntVar cost(void) const
Return solution cost.
IndSet(const SizeOptions &opt)
Actual model.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntArgs i({1, 2, 3, 4})