steiner.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * 00006 * Copyright: 00007 * Guido Tack, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-06-02 09:57:41 +0200 (Wed, 02 Jun 2010) $ by $Author: tack $ 00011 * $Revision: 11002 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <gecode/driver.hh> 00039 #include <gecode/int.hh> 00040 #include <gecode/set.hh> 00041 00042 using namespace Gecode; 00043 00052 class Steiner : public Script { 00053 public: 00055 enum { 00056 MODEL_NONE, 00057 MODEL_MATCHING, 00058 MODEL_SEQ 00059 }; 00061 int n; 00063 int noOfTriples; 00064 00066 SetVarArray triples; 00067 00069 Steiner(const SizeOptions& opt) 00070 : n(opt.size()), noOfTriples((n*(n-1))/6), 00071 triples(*this, noOfTriples, IntSet::empty, 1, n, 3, 3) { 00072 00073 for (int i=0; i<noOfTriples; i++) { 00074 for (int j=i+1; j<noOfTriples; j++) { 00075 SetVar x = triples[i]; 00076 SetVar y = triples[j]; 00077 00078 SetVar atmostOne(*this,IntSet::empty,1,n,0,1); 00079 rel(*this, (x & y) == atmostOne); 00080 00081 IntVar x1(*this,1,n); 00082 IntVar x2(*this,1,n); 00083 IntVar x3(*this,1,n); 00084 IntVar y1(*this,1,n); 00085 IntVar y2(*this,1,n); 00086 IntVar y3(*this,1,n); 00087 00088 if (opt.model() == MODEL_NONE) { 00089 /* Naive alternative: 00090 * just including the ints in the set 00091 */ 00092 rel(*this, singleton(x1) <= x); 00093 rel(*this, singleton(x2) <= x); 00094 rel(*this, singleton(x3) <= x); 00095 rel(*this, singleton(y1) <= y); 00096 rel(*this, singleton(y2) <= y); 00097 rel(*this, singleton(y3) <= y); 00098 00099 } else if (opt.model() == MODEL_MATCHING) { 00100 /* Smart alternative: 00101 * Using matching constraints 00102 */ 00103 00104 channel(*this, IntVarArgs()<<x1<<x2<<x3, x); 00105 channel(*this, IntVarArgs()<<y1<<y2<<y3, y); 00106 } else if (opt.model() == MODEL_SEQ) { 00107 SetVar sx1 = expr(*this, singleton(x1)); 00108 SetVar sx2 = expr(*this, singleton(x2)); 00109 SetVar sx3 = expr(*this, singleton(x3)); 00110 SetVar sy1 = expr(*this, singleton(y1)); 00111 SetVar sy2 = expr(*this, singleton(y2)); 00112 SetVar sy3 = expr(*this, singleton(y3)); 00113 sequence(*this,SetVarArgs()<<sx1<<sx2<<sx3,x); 00114 sequence(*this,SetVarArgs()<<sy1<<sy2<<sy3,y); 00115 } 00116 00117 /* Breaking symmetries */ 00118 rel(*this, x1 < x2); 00119 rel(*this, x2 < x3); 00120 rel(*this, x1 < x3); 00121 00122 rel(*this, y1 < y2); 00123 rel(*this, y2 < y3); 00124 rel(*this, y1 < y3); 00125 00126 linear(*this, IntArgs(6,(n+1)*(n+1),n+1,1,-(n+1)*(n+1),-(n+1),-1), 00127 IntVarArgs()<<x1<<x2<<x3<<y1<<y2<<y3, IRT_LE, 0); 00128 } 00129 } 00130 00131 branch(*this, triples, SET_VAR_NONE, SET_VAL_MIN_INC); 00132 } 00134 virtual void 00135 print(std::ostream& os) const { 00136 for (int i=0; i<noOfTriples; i++) { 00137 os << "\t[" << i << "] = " << triples[i] << std::endl; 00138 } 00139 } 00141 Steiner(bool share, Steiner& s) : Script(share,s), n(s.n), noOfTriples(s.noOfTriples) { 00142 triples.update(*this, share, s.triples); 00143 } 00145 virtual Space* 00146 copy(bool share) { 00147 return new Steiner(share,*this); 00148 } 00149 }; 00150 00154 int 00155 main(int argc, char* argv[]) { 00156 SizeOptions opt("Steiner"); 00157 opt.model(Steiner::MODEL_NONE); 00158 opt.model(Steiner::MODEL_NONE, "rel", "Use simple relation constraints"); 00159 opt.model(Steiner::MODEL_MATCHING, "matching", "Use matching constraints"); 00160 opt.model(Steiner::MODEL_SEQ, "sequence", "Use sequence constraints"); 00161 opt.size(9); 00162 opt.iterations(20); 00163 opt.parse(argc,argv); 00164 Script::run<Steiner,DFS,SizeOptions>(opt); 00165 return 0; 00166 } 00167 00168 00169 // STATISTICS: example-any 00170