atmostOne.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-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11192 $ 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/set/distinct.hh> 00039 00040 /* 00041 * These propagators implement the scheme discussed in 00042 * 00043 * Andrew Sadler and Carment Gervet: Global Reasoning on Sets. 00044 * FORMUL'01 workshop in conjunction with CP 2001. 00045 * 00046 * Todo: make the propagators incremental. 00047 */ 00048 00049 namespace Gecode { namespace Set { namespace Distinct { 00050 00051 /* 00052 * "AtMostOneIntersection" propagator 00053 * 00054 */ 00055 00056 Actor* 00057 AtmostOne::copy(Space& home, bool share) { 00058 return new (home) AtmostOne(home,share,*this); 00059 } 00060 00061 ExecStatus 00062 AtmostOne::propagate(Space& home, const ModEventDelta&) { 00063 Region r(home); 00064 LubRanges<SetView>* lubs = r.alloc<LubRanges<SetView> >(x.size()); 00065 for (int i = x.size(); i--; ) { 00066 lubs[i].init(x[i]); 00067 } 00068 Iter::Ranges::NaryUnion<LubRanges<SetView> > bigT(lubs, x.size()); 00069 Iter::Ranges::Cache<Iter::Ranges::NaryUnion<LubRanges<SetView> > > 00070 bigTC(bigT); 00071 00072 Iter::Ranges::ToValues<Iter::Ranges::Cache<Iter::Ranges::NaryUnion<LubRanges<SetView> > > > 00073 as(bigTC); 00074 00075 while (as()) { 00076 int a = as.val(); ++as; 00077 00078 // cardSa is the number of sets that contain a in the glb 00079 int cardSa = 0; 00080 for (int i=x.size(); i--;) 00081 if (x[i].contains(a)) 00082 cardSa++; 00083 00084 // bigTa is the union of all lubs that contain a 00085 GLBndSet bigTa(home); 00086 for (int i=x.size(); i--;) { 00087 if (!x[i].notContains(a)) { 00088 LubRanges<SetView> xilub(x[i]); 00089 bigTa.includeI(home, xilub); 00090 } 00091 } 00092 00093 // maxa is the maximum number of sets that can contain a 00094 int maxa = static_cast<int>((bigTa.size() - 1) / (c - 1)); 00095 bigTa.dispose(home); 00096 00097 // Conditional Rule A: 00098 // If more sets already contain a than allowed, fail. 00099 if (maxa < cardSa) 00100 return ES_FAILED; 00101 00102 if (maxa == cardSa) { 00103 // Conditional Rule B: 00104 // All a used up. All other sets (those that don't have a in their 00105 // glb already) cannot contain a. 00106 for (int i=x.size(); i--;) { 00107 if (!x[i].contains(a)) { 00108 GECODE_ME_CHECK(x[i].exclude(home, a)); 00109 } 00110 } 00111 } else { 00112 LubRanges<SetView>* lubs2 = r.alloc<LubRanges<SetView> >(x.size()); 00113 for (int i = x.size(); i--; ) { 00114 lubs2[i].init(x[i]); 00115 } 00116 Iter::Ranges::NaryUnion<LubRanges<SetView> > bigT2(lubs2, x.size()); 00117 00118 GlbRanges<SetView>* glbs = r.alloc<GlbRanges<SetView> >(cardSa); 00119 int count = 0; 00120 for (int i=x.size(); i--; ) { 00121 if (x[i].contains(a)) { 00122 glbs[count].init(x[i]); 00123 count++; 00124 } 00125 } 00126 Iter::Ranges::NaryUnion<GlbRanges<SetView> > glbsa(glbs, cardSa); 00127 Iter::Ranges::Diff<Iter::Ranges::NaryUnion<LubRanges<SetView> >, 00128 Iter::Ranges::NaryUnion<GlbRanges<SetView> > > deltaA(bigT2, glbsa); 00129 Iter::Ranges::Cache< 00130 Iter::Ranges::Diff<Iter::Ranges::NaryUnion<LubRanges<SetView> >, 00131 Iter::Ranges::NaryUnion<GlbRanges<SetView> > > > deltaAC(deltaA); 00132 // deltaAC contains all elements that are not yet known to be 00133 // in a set together with a. 00134 // Formally: \cup_i lub(x_i) - \cup_i {glb(s_i) | a\in glb(s_i)} 00135 00136 00137 if (Iter::Ranges::size(deltaAC) == c - 1) { 00138 // Conditional Rule C: 00139 // If deltaA has exactly c-1 elements, all sets that are not yet 00140 // known to contain a cannot contain a if it is impossible that 00141 // they contain all of deltaA. Or the other way around: 00142 // If a is added to the glb of a set s, deltaA must be a subset of 00143 // s, because otherwise s would share at least one more element 00144 // with another set that has a in its lower bound. 00145 // Weird, eh? 00146 for (int i=x.size(); i--; ) { 00147 if (!x[i].contains(a) && !x[i].notContains(a)) { 00148 deltaAC.reset(); 00149 LubRanges<SetView> xilub(x[i]); 00150 if (!Iter::Ranges::subset(deltaAC, xilub)) { 00151 GECODE_ME_CHECK(x[i].exclude(home, a)); 00152 } 00153 } 00154 } 00155 } 00156 00157 } 00158 00159 } 00160 00161 return ES_NOFIX; 00162 } 00163 00164 }}} 00165 00166 // STATISTICS: set-prop