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 };
00038
00039 static const int e_20_10[] = {
00040 0, 4, 2,12, 12,14, 18,19, 7,10,
00041 9,12, 5,11, 6,15, 3,18, 7,16
00042 };
00043
00044 static const Graph g_20_10 = { 20, 10, e_20_10 };
00045
00046 static const int e_40_20[] = {
00047 21,30, 11,30, 19,38, 20,25, 11,24,
00048 20,33, 8,39, 4, 5, 6,16, 5,32,
00049 0, 9, 5,24, 25,28, 36,38, 14,20,
00050 19,25, 11,22, 13,30, 7,36, 15,33
00051 };
00052
00053 static const Graph g_40_20 = { 40, 20, e_40_20 };
00055
00056
00063 class IndSet : public Example {
00064 protected:
00066 const Graph& g;
00068 BoolVarArray v;
00070 IntVar k;
00071 public:
00073 IndSet(const Options& opt)
00074 : g(opt.size == 0 ? g_20_10 : g_40_20),
00075 v(this,g.n_v,0,1), k(this,0,g.n_e) {
00076 const int* e = g.e;
00077 const int* e1 = e++; const int* e2 = e++;
00078 for (int i = g.n_e; i--; )
00079 post(this, v[*e1]+v[*e2] <= 1);
00080 linear(this, v, IRT_EQ, k);
00081 branch(this, v, BVAR_NONE, BVAL_MIN);
00082 }
00083
00085 IndSet(bool share, IndSet& s) : Example(share,s), g(s.g) {
00086 v.update(this, share, s.v);
00087 k.update(this, share, s.k);
00088 }
00090 virtual Space*
00091 copy(bool share) {
00092 return new IndSet(share,*this);
00093 }
00094
00096 virtual void
00097 print(void) {
00098 std::cout << "\tk = " << k << std::endl
00099 << "\tv[] = {";
00100 for (int i = 0; i < v.size(); i++)
00101 std::cout << v[i] << ", ";
00102 std::cout << "};" << std::endl;
00103 }
00104
00106 void
00107 constrain(Space* s) {
00108 rel(this, k, IRT_GR, static_cast<IndSet*>(s)->k.val());
00109 }
00110 };
00111
00112
00116 int
00117 main(int argc, char** argv) {
00118 Options opt("IndSet");
00119 opt.solutions = 0;
00120 opt.size = 1;
00121 opt.iterations = 1000;
00122 opt.parse(argc,argv);
00123 Example::run<IndSet,BAB>(opt);
00124 return 0;
00125 }
00126
00127
00128