Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

ind-set.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2002
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-11-04 15:30:42 +0100 (Fri, 04 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2499 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "examples/support.hh"
00023 #include "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 // STATISTICS: example-any
00128