00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "examples/support.hh"
00023 #include "gecode/minimodel.hh"
00024
00031
00032 class Graph {
00033 public:
00034 const int n_v;
00035 const int n_e;
00036 const int* e;
00037 Graph(const int n_v0, const int n_e0, const int* e0)
00038 : n_v(n_v0), n_e(n_e0), e(e0) {}
00039 };
00040
00041 static const int e_20_10[] = {
00042 0, 4, 2,12, 12,14, 18,19, 7,10,
00043 9,12, 5,11, 6,15, 3,18, 7,16
00044 };
00045
00046 static const Graph g_20_10(20,10,e_20_10);
00047
00048 static const int e_40_20[] = {
00049 21,30, 11,30, 19,38, 20,25, 11,24,
00050 20,33, 8,39, 4, 5, 6,16, 5,32,
00051 0, 9, 5,24, 25,28, 36,38, 14,20,
00052 19,25, 11,22, 13,30, 7,36, 15,33
00053 };
00054
00055 static const Graph g_40_20(40, 20, e_40_20);
00057
00058
00065 class IndSet : public Example {
00066 protected:
00068 const Graph& g;
00070 BoolVarArray v;
00072 IntVar k;
00073 public:
00075 IndSet(const Options& opt)
00076 : g(opt.size == 0 ? g_20_10 : g_40_20),
00077 v(this,g.n_v,0,1), k(this,0,g.n_e) {
00078 const int* e = g.e;
00079 const int* e1 = e++; const int* e2 = e++;
00080 for (int i = g.n_e; i--; )
00081 bool_and(this, v[*e1],v[*e2],false);
00082 linear(this, v, IRT_EQ, k);
00083 branch(this, v, BVAR_NONE, BVAL_MIN);
00084 }
00085
00087 IndSet(bool share, IndSet& s) : Example(share,s), g(s.g) {
00088 v.update(this, share, s.v);
00089 k.update(this, share, s.k);
00090 }
00092 virtual Space*
00093 copy(bool share) {
00094 return new IndSet(share,*this);
00095 }
00096
00098 virtual void
00099 print(void) {
00100 std::cout << "\tk = " << k << std::endl
00101 << "\tv[] = {";
00102 for (int i = 0; i < v.size(); i++)
00103 std::cout << v[i] << ", ";
00104 std::cout << "};" << std::endl;
00105 }
00106
00108 void
00109 constrain(Space* s) {
00110 rel(this, k, IRT_GR, static_cast<IndSet*>(s)->k.val());
00111 }
00112 };
00113
00114
00118 int
00119 main(int argc, char** argv) {
00120 Options opt("IndSet");
00121 opt.solutions = 0;
00122 opt.size = 1;
00123 opt.iterations = 2000;
00124 opt.parse(argc,argv);
00125 Example::run<IndSet,BAB>(opt);
00126 return 0;
00127 }
00128
00129
00130