ind-set.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2002
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
using namespace Gecode;
class Graph {
public:
const int n_v;
const int n_e;
const int* e;
Graph(const int n_v0, const int n_e0, const int* e0)
: n_v(n_v0), n_e(n_e0), e(e0) {}
};
const int e_20_10[] = {
0, 4, 2,12, 12,14, 18,19, 7,10,
9,12, 5,11, 6,15, 3,18, 7,16
};
const Graph g_20_10(20,10,e_20_10);
const int e_40_20[] = {
21,30, 11,30, 19,38, 20,25, 11,24,
20,33, 8,39, 4, 5, 6,16, 5,32,
0, 9, 5,24, 25,28, 36,38, 14,20,
19,25, 11,22, 13,30, 7,36, 15,33
};
const Graph g_40_20(40, 20, e_40_20);
class IndSet : public IntMaximizeScript {
protected:
const Graph& g;
BoolVarArray v;
IntVar k;
public:
IndSet(const SizeOptions& opt)
: IntMaximizeScript(opt),
g(opt.size() == 0 ? g_20_10 : g_40_20),
v(*this,g.n_v,0,1), k(*this,0,g.n_v) {
const int* e = g.e;
for (int i = g.n_e; i--; ) {
const int* e1 = e++; const int* e2 = e++;
rel(*this, v[*e1], BOT_AND, v[*e2], 0);
}
linear(*this, v, IRT_EQ, k);
branch(*this, v, BOOL_VAR_NONE(), BOOL_VAL_MIN());
}
IndSet(IndSet& s) : IntMaximizeScript(s), g(s.g) {
v.update(*this, s.v);
k.update(*this, s.k);
}
virtual Space*
copy(void) {
return new IndSet(*this);
}
virtual void
print(std::ostream& os) const {
os << "\tk = " << k << std::endl
<< "\tv[] = " << v << std::endl;
}
virtual IntVar cost(void) const {
return k;
}
};
int
main(int argc, char* argv[]) {
SizeOptions opt("IndSet");
opt.solutions(0);
opt.size(1);
opt.iterations(2000);
opt.parse(argc,argv);
IntMaximizeScript::run<IndSet,BAB,SizeOptions>(opt);
return 0;
}
// STATISTICS: example-any
Gecode::BoolVarArray
Boolean variable array.
Definition int.hh:808
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Graph
Graph specification
Definition ind-set.cpp:47
Graph::Graph
Graph(const int n_v0, const int n_e0, const int *e0)
Definition ind-set.cpp:52
Graph::e
const int * e
Arrays of edges (as vertex pairs).
Definition ind-set.cpp:51
Graph::n_e
const int n_e
Number of edges.
Definition ind-set.cpp:50
Graph::n_v
const int n_v
Number of vertices.
Definition ind-set.cpp:49
IndSet::main
int main(int argc, char *argv[])
Main-function.
Definition ind-set.cpp:130
IndSet::e_40_20
const int e_40_20[]
Main-function.
Definition ind-set.cpp:63
IndSet::IndSet
IndSet(IndSet &s)
Constructor for cloning s.
Definition ind-set.cpp:104
IndSet::copy
virtual Space * copy(void)
Copy during cloning.
Definition ind-set.cpp:110
IndSet::g_20_10
const Graph g_20_10(20, 10, e_20_10)
Main-function.
IndSet::g_40_20
const Graph g_40_20(40, 20, e_40_20)
Main-function.
IndSet::k
IntVar k
How many elements has indipendent set.
Definition ind-set.cpp:87
IndSet::e_20_10
const int e_20_10[]
Main-function.
Definition ind-set.cpp:56
IndSet::v
BoolVarArray v
Whether vertex included in independent set.
Definition ind-set.cpp:85
IndSet::print
virtual void print(std::ostream &os) const
Print solution.
Definition ind-set.cpp:115
IndSet::g
const Graph & g
Graph used
Definition ind-set.cpp:83
IndSet::cost
virtual IntVar cost(void) const
Return solution cost.
Definition ind-set.cpp:120
IndSet::IndSet
IndSet(const SizeOptions &opt)
Actual model.
Definition ind-set.cpp:90
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
driver.hh
int.hh
Gecode::IntMaximizeScript
Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > > IntMaximizeScript
Base-class for scripts for finding solution of highest integer cost.
Definition driver.hh:814
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
Gecode::linear
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::BOOL_VAL_MIN
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition val.hpp:130
Gecode::BOOL_VAR_NONE
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364